作者：whisper

链接：http://proprogrammar.com:443/article/137

声明：请尊重原作者的劳动，如需转载请注明出处

    说明：本章主要说了排序的基本概念，插入类排序，交换类排序法，选择类排序法，归并排序，分配类排序，各种排序方法的综合比较，外排序

    本章知识结构图

    排序的基本概念

    排序：有n 个记录的序列{R1，R2，…，Rn}，其相应关键字的序列是{K1，K2，…，Kn}，相应的下标序列为1，2，…，n。通过排序，要求找出当前下标序列1，2，…，n 的一种排列p1，p2， …，pn，使得相应关键字满足如下的非递减（或非递增）关系，即：Kp1≤Kp2≤…≤Kpn，这样就得到一个按关键字有序的记录序列{Rp1，Rp2，…，Rpn}。

    假设Ki=Kj(1≤i≤n，1≤j≤n，i≠j)， 若在排序前的序列中Ri 领先于Rj(即i<j)，经过排序后得到的序列中Ri 仍领先于Rj， 则称所用的排序方法是稳定的；反之，当相同关键字的领先关系在排序过程中发生变化，则称所用的排序方法是不稳定的。

    无论是稳定的还是不稳定的排序方法，均能排好序。在应用排序的某些场合，如选举和比赛等，对排序的稳定性是有特殊要求的。

    证明一种排序方法是稳定的，要从算法本身的步骤中加以证明。证明排序方法是不稳定的，只需给出一个反例说明。

    在排序过程中，一般进行两种基本操作：

    （1） 比较两个关键字的大小；
    （2） 将记录从一个位置移动到另一个位置。

    其中操作（1）对于大多数排序方法来说是必要的，而操作（2）则可以通过采用适当的存储方式予以避免。

    为了讨论方便，假设待排记录的关键字均为整数，均从数组中下标为1 的位置开始存储，下标为0 的位置存储监视哨，或空闲不用。

    插入类排序

    插入排序的基本思想是：在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序地插入到已排好序的记录子集中，直到将所有待排记录全部插入为止。

    打扑克牌时的抓牌就是插入排序一个很好的例子，每抓一张牌，插入到合适位置，直到抓完牌为止，即可得到一个有序序列。

    直接插入排序

    假设待排序记录存放在r［1..n］之中，为了提高效率，我们附设一个监视哨r［0］，使得r［0］始终存放待插入的记录。

    监视哨的作用有两个：一是备份待插入的记录，以便前面关键字较大的记录后移；二是防止越界。

void InsSort(RecordType r［］, int length) {
    //对记录数组r 做直接插入排序， length 为数组的长度
    for ( i=2 ; i<= length ; i++ ) 
    {
        r［0］=r［i］; j=i-1;
        //将待插入记录存放到变量x 中
        while (r［0］.key< r［j］.key ) 
        {//寻找插入位置
            r［j+1］= r［j］; j=j-1;
        }
        r［j+1］=r［0］;
        //将待插入记录插入到已排序的序列中
    }
}

    该算法的要点是：① 使用监视哨r［0］临时保存待插入的记录； ② 从后往前查找应插入的位置；③ 查找与移动在同一循环中完成。

    直接插入排序算法分析： 从空间角度来看，它只需要一个辅助空间r［0］。从时间耗费角度来看， 主要时间耗费在关键字比较和移动元素上。

    对于一趟插入排序，算法中的while 循环的次数主要取决于待插记录与前i-1 个记录的关键字的关系上。

    最好情况为（顺序）：r［i］.key> r［i-1］.key，while 循环只执行1 次，且不移动记录；
    最坏情况为（逆序）： r［i］.key< r［1］.key， 则while 循环中关键字比较次数和移动记录的次数为i-1。

    对整个排序过程而言，最好情况是待排序记录本身已按关键字有序排列， 此时总的比较次数为n-1 次，移动记录的次数也达到最小值2（n-1）(每一次只对待插记录r［i］移动两次)；最坏情况是待排序记录按关键字逆序排列， 此时总的比较次数达到最大值为(n+2)(n-1)/2，记录移动的次数也达到最大值(n+4)(n-1)/2。

    注：最好情况下的时间复杂度为T(n) = O(n)

    执行的时间耗费主要取决于数据的分布情况。若待排序记录是随机的，即待排序记录可能出现的各种排列的概率相同， 则可以取上述最小值和最大值的平均值，约为n²/4。因此，直接插入排序的时间复杂度为T(n)=O(n²)，空间复杂度为S(n)=O(1)。

    说明排序算法的稳定性必须从算法本身加以证明。直接插入排序方法是稳定的排序方法。在直接插入排序算法中，由于待插入元素的比较是从后向前进行的， 循环while (x.key< r［j］.key )的判断条件就保证了后面出现的关键字不可能插入到与前面相同的关键字之前。

    直接插入排序算法简便，比较适用于待排序记录数目较少且基本有序的情况。

    当待排记录数目较大时，直接插入排序的性能就不好， 为此我们可以对直接插入排序做进一步的改进。

    在直接插入排序法的基础上，从减少“比较关键字”和“移动记录”两种操作的次数着手来进行改进。

    折半插入排序

    虽然折半插入排序法与直接插入排序法相比较，改善了算法中比较次数的数量级，但其并未改变移动元素的时间耗费，所以折半插入排序的总的时间复杂度仍然是O(n²)。

    希尔排序

    基本思想：

    先将待排序记录序列分割成若干个“较稀疏的”子序列，分别进行直接插入排序。

    经过上述粗略调整， 整个序列中的记录已经基本有序，最后再对全部记录进行一次直接插入排序。

    具体实现时，首先选定两个记录间的距离d1，在整个待排序记录序列中将所有间隔为d1 的记录分成一组，进行组内直接插入排序，然后再取两个记录间的距离
d2<d1，在整个待排序记录序列中，将所有间隔为d2 的记录分成一组，进行组内直接插入排序，直至选定两个记录间的距离dt=1 为止，此时只有一个子序列，即整个待排序记录序列。

    希尔排序的分析是一个复杂的问题，因为它的时间耗费是所取的“增量”序列的函数。到目前为止，尚未有人求得一种最好的增量序列。但经过大量研究，也得出了一些局部的结论。

    在排序过程中，相同关键字记录的领先关系发生变化， 则说明该排序方法是不稳定的。例如：待排序序列{2，4，1，2}，采用希尔排序，设d1=2，得到一趟排序结果为{1，2，2，4}， 说明希尔排序法是不稳定的排序方法。

    交换类排序法

    冒泡排序（相邻比序法）

    冒泡排序算法如下：

void BubbleSort(RecordType r［］, int length ) {
/*对记录数组r 做冒泡排序， length 为数组的长度*/
    n=length; change=TRUE;
    for ( i=1 ; i<= n-1 && change ;++i ) {
       change=FALSE；
        for ( j=1 ; j<= n-i ; ++j)
            if (r［j］.key> r［j+1］.key ) {
                x= r［j］; r［j］= r［j+1］; r［j+1］= x;
                change=TRUE；
            }
    }
}

    快速排序

    假设待划分序列为r［left］， r［left+1］， …，r［right］，具体实现上述划分过程时，可以设两个指针i 和j，它们的初值分别为left 和right。首先将基准记录r［left］移至变量x 中，使r［left］，即r［i］相当于空单元， 然后反复进行如下两个扫描过程，直到i 和j 相遇：

    (1) j 从右向左扫描，直到r［j］.key < x.key 时， 将r［j］移至空单元r［i］，此时r［j］相当于空单元。
    (2) i 从左向右扫描， 直到r［i］.key > x.key 时， 将r［i］移至空单元r［j］，此时r［i］相当于空单元。

    当i 和j 相遇时， r［i］（或r［j］）相当于空单元，且r［i］左边所有记录的关键字均不大于基准记录的关键字，而r［i］右边所有记录的关键字均不小于基准记录的关键字。

    最后将基准记录移至r［i］中，就完成了一次划分过程。

    对于r［i］左边的子表和r［i］右边的子表可采用同样的方法进行进一步划分。

    快速排序算法如下：

void QKSort(RecordType r［］, int low, int high ){
    /*对记录数组r［low..high］用快速排序算法进行排序*/
    if(1ow<high) {
        pos=QKPass(r, low, high);
        QKSort(r, low, pos-1);
        QKSort(r, pos+1, high);
    }
}

// 一趟快速排序算法如下:
int QKPass(RecordType r［］, int left， int right){
    x= r［left］； // 选择基准记录
    low=left ; high=right；

    while ( low<high ) {
        while (low< high && r［high］.key>=x.key ) high--；
        // high 从右到左找小于x.key 的记录
        if ( low <high ) { r［low］= r［high］； low++;}
        //找到小于x.key 的记录， 则进行交换
        while (low<high && r［low］.key<x.key ) low++;
       //low 从左到右找大于x.key 的记录
       if ( low<high ) { r［high］= r［low］； high--;}
        // 找到大于x.key 的记录，则交换
    }

    r［low］=x； //将基准记录保存到low=high 的位置
    return low; //返回基准记录的位置
}

    分析快速排序的时间耗费,共需进行多少趟排序，取决于递归调用深度。

    (1) 最好情况是每趟将序列一分两半，正好在表中间，将表分成两个大小相等的子表。
    (2) 最坏情况是已经排好序, 第一趟经过n-1 次比较， 第1 个记录定在原位置，左部子表为空表，右部子表为n-1 个记录。第二趟n-1 个记录经过n-2 次比较，第2 个记录定在原位置， 左部子表为空表，右部子表为n-2 个记录， 依此类推， 共需进行n-1 趟排序，将蜕变为冒泡排序， 其时间复杂度为O(n²)。

    快速排序是否是稳定的排序方法？不是！

    选择类排序法

    简单选择排序

    简单选择排序的基本思想：第i 趟简单选择排序是指通过n-i 次关键字的比较，从n-i+1 个记录中选出关键字最小的记录，并与第i 个记录进行交换。共需进行n-1 趟比较，直到所有记录排序完成为止。

    堆排序

    堆分为小根堆和大根堆。对于一个小(大)根堆，它是具有如下特性的一棵完全二叉树。

    1.若树根结点存在左孩子，则根结点的值小(大)于等于左孩子结点的值。
    2.若树根结点存在右孩子，则根结点的值小(大)于等于右孩子结点的值。
    3.以左、右孩子为根的子树又各是一个堆。

    堆排序的过程主要需要解决两个问题：

     按堆定义建初堆；
     去掉最大值之后重建堆，得到次大值。

    问题1: 当堆顶元素改变时，如何重建堆?
    首先将完全二叉树根结点中的记录移出，该记录称为待调整记录。此时根结点相当于空结点。
    从空结点的左、右子中选出一个关键字较小的记录， 如果该记录的关键字小于待调整记录的关键字，则将该记录上移至空结点中。
    此时， 原来那个关键字较小的子结点相当于空结点。
    重复上述移动过程，直到空结点左、右子的关键字均不小于待调整记录的关键字，此时将待调整记录放入空结点即可。
    上述调整方法相当于把待调整记录逐步向下“筛”的过程，所以一般称为“筛选”法。

    问题2：如何由一个任意序列建初堆？
    一个任意序列看成是对应的完全二叉树，由于叶子结点可以视为单元素的堆，因而可以反复利用“筛选”法， 自底向上逐层把所有以非叶子结点为根的子树调整为堆，直到将整个完全二叉树调整为堆。
    可以证明，最后一个非叶子结点位于n/2个元素， n 为二叉树结点数目。因此，“筛选”须从第n/2个元素开始， 逐层向上倒退，直到根结点。

    建堆实例

    例: A = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7}

    问题3： 如何利用堆进行排序?
    进行堆排序的步骤：
    1.将待排序记录按照堆的定义建初堆， 并输出堆顶元素；
    2.调整剩余的记录序列，利用筛选法将前n-i 个元素重新筛选并建成为一个新堆，再输出堆顶元素；
    3.重复执行步骤2， 进行n-1 次筛选。
    新筛选成的堆会越来越小，而新堆后面的有序关键字会越来越多，最后使待排序记录序列成为一个有序的序列，这个过程称之为堆排序。

    堆排序示例：

    排序结果为: 15 18 30 36 36 45 48 53 72 93

    堆排序的算法分析

    堆排序的时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。
    堆排序是一种不稳定的排序方法，它不适用于待排序记录个数n 较少的情况，但对于n 较大的文件还是很有效的。
    堆排序在最坏情况下，其时间复杂度也为O(nlog₂n)，相对于快速排序来说，这是堆排序的最大优点。此外，堆排序仅需一个记录大小供交换用的辅助存储空间。

    归并排序

    与快速排序和堆排序相比，归并排序的最大特点是它为一种稳定的排序方法。一般情况下，由于要求附加与待排记录等数量的辅助空间，因此很少利用2 路归并排序进行内部排序。

    分配类排序

    多关键字排序

    例如： 我们可以将一副扑克牌的排序过程看成由花色和面值两个关键字进行排序的问题。若规定花色和面值的顺序如下：

    花色： 梅花< 方块< 红桃< 黑桃
    面值： A<2<3<…<10<J<Q<K

    并进一步规定花色的优先级高于面值，则一副扑克牌从小到大的顺序为： 梅花A， 梅花2， …，梅花K；方块A，方块2，…， 方块K； 红桃A， 红桃2， …， 红桃K； 黑桃A， 黑桃2， …， 黑桃K。具体进行排序时有两种做法，其中一种是先按花色分成有序的四类，然后再按面值对每一类从小到大排序。该方法称为“高位优先”排序法。

    另一种做法是分配与收集交替进行。首先按面值从小到大把牌摆成13 叠（每叠4张牌）， 然后将每叠牌按面值的次序收集到一起，再对这些牌按花色摆成4 叠， 每叠有13 张牌，最后把这4 叠牌按花色的次序收集到一起，于是就得到了上述有序序列。该方法称为“低位优先”排序法。

    链式基数排序

    基数排序属于上述“低位优先”排序法， 通过反复进行分配与收集操作完成排序。假设记录r［i］的关键字为keyᵢ，keyᵢ 是由d 位十进制数字构成的， 即keyᵢ=Ki¹ Ki²…Kiᵈ， 则每一位可以视为一个子关键字，其中Ki¹ 是最高位，Kiᵈ 是最低位，每一位的值都在0≤Kiʲ≤9 的范围内，此时基数rd=10。

    如果keyᵢ 是由d 个英文字母构成的，即keyᵢ=Ki¹ Ki² …Kiᵈ，其中′a′≤Kiʲ≤′z′， 则基数rd=26。

    基数排序：

    适合于字符串和整数这种有明显结构特征的关键码。

    各种排序方法的综合比较

    综合分析和比较各种排序方法，可得出以下结论：

    简单排序一般只用于n 较小的情况。当序列中的记录“基本有序”时，直接插入排序是最佳的排序方法，常与快速排序、归并排序等其它排序方法结合使用。
    快速排序、堆排序和归并排序的平均时间复杂度均为O(nlogn)， 但实验结果表明，就平均时间性能而言，快速排序是所有排序方法中最好的。遗憾的是，快速排序在最坏情况下的时间性能为O(n²)。堆排序和归并排序的最坏时间复杂度仍为O(nlogn)，当n 较大时，归并排序的时间性能优于堆排序，但它所需的辅助空间最多。
    从排序的稳定性上来看，基数排序是稳定的，除了简单选择排序，其它各种简单排序法也是稳定的。然而，快速排序、堆排序、希尔排序等时间性能较好的排序方法，以及简单选择排序都是不稳定的。多数情况下，排序是按记录的主关键字进行的，此时不用考虑排序方法的稳定性。如果排序是按记录的次关键字进行的， 则应充分考虑排序方法的稳定性。
    综上所述，每一种排序方法各有特点，没有哪一种方法是绝对最优的。我们应根据具体情况选择合适的排序方法，也可以将多种方法结合起来使用。

    各种排序算法的选择

    （1）待排序的记录数目n 较小时，则采用插入排序和简单选择排序；
    （2）若待排序记录按关键字基本有序，则宜采用直接插入排序和起泡排序；
    （3）当n 很大且关键字的位数较少时，采用链式基数排序较好；
    （4）若n 较大，采用时间复杂度为O(nlogn)的排序方法有：快速排序、堆排序或归并排序。

    其中快速排序可能出现最坏情况，且此时的递归深度为n，所需栈空间为O(n)。
    堆排序不会出现像快速排序那样的最坏情况，且所需的辅助空间比快速排序少，但快速排序与堆排序这两种算法都是不稳定的。
    如果要求排序是稳定的，则可以选择归并排序算法。

    外排序

    由于文件很大, 无法把整个文件的所有记录同时调入内存中进行排序, 即无法进行内排序, 从而需要研究外存设备上（文件）的排序技术, 称这种排序为外排序。
    最常用的外排序方法是多路归并法。这种方法基本上要经历两个阶段:
    第一阶段是把文件逐段输入到内存, 用较好的内排序方法对这段文件进行排序。已排序的文件段通常称为归并段。整个文件经过逐段排序后又逐段写回到外存上。这样,在外存上就形成了许多初始归并段。
    第二阶段是对这些初始归并段使用某种归并方法（如两路归并法）, 进行多遍归并。最后在外存上形成一个排序的文件。

    二路外排序

    归并原理：把第一阶段所生成的顺串加以合并(例如通过若干次二路合并)，直至变为一个顺串为止，即形成一个已排序的文件。

    二路归并外排序

    三路归并

    本章学习重点

    对于每个排序掌握

    1、算法的基本思想
    2、手工排序过程
    3、算法描述
    4、性能
    （1）最好、最坏、平均时间复杂度
    （2）空间复杂度
    （3）稳定性

亲爱的读者：有时间可以点赞评论一下