`

数据信息中的逆序对

阅读更多

逆序对

逆序对是指在一个元素序列中,按照一定的大小比较方法,序列中任两个元素大小顺序颠倒的组合。

A[1..n] 是一个包含 n 个不同数的数组 . 如果在 i<j 的情况下 , A[i]>A[j], (i,j) 就称为 A 中的一个逆序对 .

对于一个给定待排序序列 , 其中的逆序对的发现与还原正是排序所要解决的事情 . 排序过程中一般是先发现逆序对再将其还原 , 由于这些让我们联想到了排序性能提高的一些方法 .

1. 一次还原操作 , 使得多组逆序对还原 .

eg: 共有 21 对 共有 10

7,6,5,4,3,2,1--(1 7 互换 )-->1,6,5,4,3,2,7

一次还原处理了 11

2. 一次对换操作后 , 尽量不要或者少产生额外的逆序对

eg: 共有 16 对 共有 11

7,6,5,1,3,2,4--(4 7 互换 )-->4,6,5,1,3,2,7

一次还原处理了 5 , 另外又多产生了 (4,1) 一对

在我观察的比较类排序中 , 快速排序体现了 1 却缺失了 2; 合并排序恰恰相反体现了 2 却缺失了 1.

关于逆序对的相关统计算法代码参见

/* Copyright (C) 2000-2007 Wang Pengcheng <wpc0000@163.com>
 * Licensed to the Wang Pengcheng under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The LGPL licenses this file to You under the GNU Lesser General Public
 * Licence, Version 2.0  (the "License"); you may not use this file except in
 * compliance with the License.  You may obtain a copy of the License at
 *
 *     http://www.gnu.org/licenses/lgpl.txt
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package mypackage.algorithm.unit02;

public class Inversion ...{
    
    private static int tot;
    
    /** *//**
     *InsertionSort
     *The time limit of this sort is O(n^2)
     *<strong>O(n^2)</strong>
     *@param  element will be sorted
     */
    private static <Type extends Comparable> void insertionSort(Type element[])...{
        for(int j=1;j<element.length;j++)...{
            Type    key    =    element[j];
            int i    =    j-1;
            
            while( (i>=0)&&(element[i].compareTo(key)>0))...{
                element[i+1]    =    element[i];
                tot++;
                i--;
            }
            element[i+1]    =    key;
        }
    }
    /** *//**
     *Merge used in the mergeSort
     *<strong>O(n)</strong>
     *@param element Type[] the elements to be merged
     *@param p int the begin of the  first elements
     *@param q int the end of the first elements
     *@param r int the end of the second elements
     */
    private static <Type extends Comparable> void merge(Type element[],int p,int q,int r)...{
        int nl    =    q-p+1;
        int nr    =    r-q;
        
        Type[] lElement,rElement;
        lElement    =    (Type[])java.lang.reflect.Array.newInstance(element.getClass().getComponentType(),nl);
        rElement    =    (Type[])java.lang.reflect.Array.newInstance(element.getClass().getComponentType(),nr);
                
        for(int i=0;i<nl;i++)...{
            lElement[i]    =    element[p+i];
        }
        for(int i=0;i<nr;i++)...{
            rElement[i]    =    element[q+i+1];
        }
        
        int i=0,j=0;
        int k    =    p;
        while((i<nl)&&(j<nr))...{
            if(lElement[i].compareTo(rElement[j])<=0)...{
                element[k]    =    lElement[i];
                i++;
            }else...{
                element[k]    =    rElement[j];
                j++;
                tot+=nl-i;
            }
            k++;
        }
        
        while(i<nl)...{
            element[k]    =    lElement[i];
            i++;
            k++;
        }
        while(j<nr)...{
            element[k]    =    rElement[j];
            j++;
            k++;
        }
    }
    
    /** *//**
     *mergeSort
     *Sort the elements by the compareTo method
     *<strong>O(nlgn)</strong>
     *@param  element Type[] that will be sorted
     *@param p the begin of the list will be sorted
     *@param r the end of the list will be sorted
     */
    private static <Type extends Comparable> void mergeSort(Type element[],int p,int r)...{
        if(p<r)...{
            int q    =    (p+r)/2;
            mergeSort(element,p,q);
            mergeSort(element,q+1,r);
            merge(element,p,q,r);
        }
    }
    private static <Type extends Comparable> void mergeSort(Type element[])...{
        mergeSort(element,0,element.length-1);
    }
    
    /** *//**
     * Count the inversion number by O(nlgn)
     * @param <Type> inversion number type
     * @param element inversion number list
     * @return count number of inversion
     */
    public static <Type extends Comparable>  int countMerge(Type element[])...{
        tot=0;
        mergeSort(element.clone());
        return tot;
    }

    /** *//**
     * Count the inversion number by O(n^2)
     * @param <Type> inversion number type
     * @param element inversion number list
     * @return count number of inversion
     */
    public static <Type extends Comparable> int countInsertion(Type element[])...{
        tot=0;
        insertionSort(element.clone());
        return tot;
    }
    /** *//**
     * @param args
     */
    public static void main(String[] args) ...{
        Integer[] a = ...{4,6,5,1,3,2,7};
        System.out.println(Inversion.countMerge(a));
    }

}
 

最后让我们牢记 :

摘《李开复:算法的力量算法并不局限于计算机和网络

举一个计算机领域外的例子:在高能物理研究方面,很多实验每秒钟都能几个 TB 的 数据量。但因为处理能力和存储能力的不足,科学家不得不把绝大部分未经处理 的数据丢弃掉。可大家要知道,新元素的信息很有可能就藏在我们来不及处理的数据里面。同样的,在其他任何领域里,算法可以改变人类的生活。例如人类基因的 研究,就可能因为算法而发明新的医疗方式。在国家安全领域,有效的算法可能避免下一个 911 的发生。在气象方面,算法可以更好地预测未来天灾的发生,以拯 救生命。

所以,如果你把计算机的发展放到应用和数据飞速增长的大环境下,你一定会发现;算法的重要性不是在日益减小,而是在日益加强。

谢谢大家。

参考书籍

Inroduction to Algorithms Thomas H.Cormen,Charles E.Leiserson,Ronald L. Rivest,Clifford Stein. 机械工业出版社

《数据结构》殷人昆,陶永雷,谢若阳,盛绚华 清华大学出版社

《算法艺术与信息学竞赛》刘汝佳,黄亮 清华大学出版社

《李开复:算法的力量》 http://www.ieee.org.cn/dispbbs.asp?boardID=60&ID=31651

分享到:
评论

相关推荐

    算法-求逆序对(信息学奥赛一本通-T1311).rar

    逆序对是算法竞赛中常见的概念,特别是在信息学奥赛中常常出现,它与排序、数组和二分查找等基础知识紧密相关。本知识点主要探讨如何有效地计算一个数组中的逆序对数量。 首先,我们来定义逆序对。在数组或序列A[1....

    11087 统计逆序对

    在IT领域,尤其是在计算机科学与数据结构中,逆序对是一个重要的概念,它不仅涉及到排序算法,还与分治策略紧密相连。逆序对的概念来源于数学中的排列理论,具体到编程实现,则通常采用归并排序的思想来高效计算。 ...

    逆序对(树状数组) C语言

    逆序对是排序数组中的一种概念,它是指在数组中,如果两个元素a和b的值满足a &gt; b,但它们的下标i ,则称(a, b)为一个逆序对。逆序对的数量可以反映出数组的有序程度,是许多算法问题的基础,如快速排序、归并排序等...

    Python程序计算逆序对数量,采用双循环结构遍历数组查找逆序对

    使用场景及目标:适用于算法学习与练习,在实践中了解并掌握基础级别的逆序对求解方式,便于后续优化升级。 其他说明:该算法虽便于理解但非性能最佳方案,对于大型数据集的处理推荐寻求如合并排序之类的时间复杂度...

    逆序对实现

    逆序对,也被称为反序对,是计算机科学中一种重要的概念,特别是在处理数组或序列时,尤其是在数据结构和算法的领域。它涉及到对数组中元素的相对顺序的考察。在给定的数组中,如果一对数值 i 和 j 满足 i 但 a[i] &gt;...

    归并求逆序对 分治 递归

    逆序对问题在计算机科学与算法领域中是一个非常典型的应用场景,尤其适用于数据结构与算法的面试题目之中。 #### 逆序对定义 首先,我们需要明确什么是逆序对。在一个数组中,如果对于某两个索引 `i` 和 `j`(`i ...

    归并求逆序对 C语言实现

    2. **逆序对概念**:在一个数组中,如果前面的数字大于后面的数字,则这两个数字组成一个逆序对。例如,在数组 `[7, 5, 6, 4]` 中,有 `(7, 5)`、`(7, 6)`、`(7, 4)` 和 `(5, 4)` 四个逆序对。 3. **分治法的应用**...

    算法分析与设计-实验1-统计逆序对

    实验要求学生能够设计并实现一个基于归并排序的分治算法来统计一个排列中的逆序对数量,并记录具体的逆序对。 #### 逆序对的概念 逆序对是指在一个排列中,对于任意两个元素i和j (i ),如果满足条件ai &gt; aj,则称...

    vb中逆序输出

    通过以上分析,我们可以看到,在VB中实现逆序输出有多种方法,其中`StrReverse`函数提供了一种直接简便的解决方案,而手动拆分重组则加深了对数字处理流程的理解。无论是哪种方法,都能有效锻炼编程思维,提高解决...

    C语言对不限长数据逆序输出

    使用递归对输入不限长度的数据进行逆序输出 尽管代码只有10来行!

    C++源程序测试数组中有多少个逆序对

    测试输入的数组中有多少个逆序对,本程序在归并排序的基础上实现,时间复杂度为O(nlgn)

    逆序对.zip

    【逆序对】是程序设计领域中常见的算法问题,尤其在数据结构与算法竞赛如“蓝桥杯”中,这是一个经常出现的考察点。逆序对,也被称为倒序对,是指在一个序列(通常为数组)中,如果i位置的元素大于j位置的元素,且i ...

    求数组的逆序数

    逆序数(Inversion Count)是指在数组或序列中,如果一个大于其后面的元素,则这样的对称为逆序对。逆序数就是数组中逆序对的数量。这个概念在理解数组的有序性、数据的复杂度分析以及解决特定问题时非常有用。 ...

    算法-求排列的逆序数(信息学奥赛一本通-T1237).rar

    《算法-求排列的逆序数(信息学奥赛一本通-T1237)》这个主题涉及到的是计算机科学中的一个重要概念,逆序对或逆序数,它在算法设计和分析中扮演着关键角色,特别是在解决排序和组合优化问题时。逆序数是衡量一个...

    算法相关-求数列逆序数

    逆序数是排序学中的一个重要概念,特别是在算法分析和数据结构中有着广泛的应用。这个“算法相关-求数列逆序数”的主题涉及到一个经典的计算机科学问题,即如何有效地计算一个数列中的逆序对数量。逆序对是指在已...

    用栈实现队列逆序输出

    在计算机科学中,数据结构是组织和管理数据的重要方式,栈和队列是两种基本的数据结构。本主题探讨的是如何利用栈(Stack)这一后进先出(LIFO)的数据结构来模拟队列(Queue)的先进先出(FIFO)特性,并实现队列的...

    东南大学组合数学实验 逆序

    逆序,或者称为逆序对,在计算机科学中是指在一个排序序列中,如果两个元素的位置颠倒了,即较大的元素出现在较小的元素之前,那么这两个元素就构成了一个逆序对。例如,在升序排列的数组中,任何不相邻且顺序相反的...

    用C++template实现数据列表逆序数量统计教程共23

    在本教程中,我们将深入探讨如何使用C++模板(Template)来实现数据列表的逆序检查以及统计逆序对的数量。C++模板是C++语言中的一个强大特性,它允许我们编写泛型代码,适用于不同类型的对象。逆序对的概念在排序...

    逆序CRC编解码算法及在DS18B20中的应用

    总结来说,逆序CRC编解码算法是一种在通信和控制领域中用于提高数据传输可靠性的方法,尤其是在DS18B20这类对数据完整性要求较高的设备中,其重要性尤为显著。通过理解并正确应用逆序CRC算法,我们可以有效地检测和...

Global site tag (gtag.js) - Google Analytics