数据结构-排序

排序的基本概念。

• 排序

排序就是将原本无序的序列重新排列成有序序列的过程。另外可以参照sort这个单词的意思，即排序的过程中其实还做了分类这件事情。

• 稳定性

所谓稳定性就是指当待排序序列中有两个或以上相同的关键字的时候，排序前和排序后这些关键字的相对位置，如果没有发生变化就是稳定的，否则就是不稳定的。

如果关键字不能重复，则排序结果就是唯一的，那么选择的排序算法稳定与否就无关紧要；如果关键字可以重复，则在选择排序算法时，就要根据具体的需求考虑选择稳定的还是不稳定的排序算法。

• 排序的算法分类

|直接插入排序、折半插入排序、希尔排序|冒泡排序、快速排序|简单选择排序、堆排序|二路归并排序|基数排序

插入排序

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

直接插入排序

遍历数组，将每个元素逐个插入到已排序的数组中。 这是人类最直观的排序方法，现实中我们就是这么排扑克牌的😶😶😶😶。

①算法描述

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置后；
6. 重复步骤2~5。

②算法思想

每趟将一个待排序的关键字按照其值的大小插入到已经排好的部分有序序列的适当位置上，直到所有待排关键字都被插入到有序序列为止。

void InsertSort(int R[],int n)
{
    int i,j;
    int temp;
    for(i = 1;i < n; ++i)
    {
        temp = R[i];
        j = i-1;
        while(j >= 0 && temp < R[j])
        {
            R[j+1] = R[j];
            --j;
        }
        R[j+1]  = temp;
    }
}

③算法性能分析

• 时间复杂度分析

  • 最好：$O(n)$；当且仅当原数组为已排序状态；
  • 最坏：$O(n2)$；当且仅当原数组为倒序状态；
  • 平均：$O(n2)$；每遍历一个元素需要扫描一次已排序数组。

• 空间复杂度分析

  • 算法所需的辅助存储空间不随待排序列的规模变化而变换，是个常量，仅在遍历时用到下标指针，因此空间复杂度为$O(1)$。

• 稳定性：稳定；按顺序遍历，由右往左插入，不会改变相同元素的前后位置。

• 缺陷：每一轮排序将未排序数组首元素插入已排序数组准确位置当中，由于数组的插入时间复杂度为 $O(n)$，而每一轮仅排序一个元素，因此算法复杂度为 $O(n^2)$。对于每一轮排序最好情况为发生 0 次交换，最坏为发生 k 次交换（即插入到已排序数组最前面），平均完成排序工作，需要发生 $\frac{n(n-1)}{4}$ 次交换。交换次数非常多，非常低效。

• 适用性分析：一般人类不用动脑筋的方法，都是最慢的那一个。

折半插入排序

①算法描述
二分（折半）插入（Binary insert sort)排序是一种在直接插入排序算法上进行小改动的排序算法。其与直接排序算法最大的区别在于查找插入位置时使用的是二分查找的方式，在速度上有一定提升。

②算法分析

• 时间复杂度分析
  • 最好情况：$O(log_2n)$
  • 最差情况：$O(n^2)$
  • 平均情况：$O(n^2)$
• 空间复杂度分析
  • 与直接插入排序一样为$O(1)$
• 优缺点：在速度上有一定提升。但是，在查找二分点的时间上的时间损耗，导致了这个算法并不能比直接插入排序优秀多少，除非你有十分确切的数据大小和随机访问迭代器。
• 适用性分析：适合关键字数较多的场景。

希尔排序

为什么引入希尔排序？
根据插入排序所存在的缺陷，我们可以设计一种方法，在插入排序开始之前，将较小元素移至数组首部，较大元素移至数组尾部，让数组的无序程度变小。同时，为了让元素跳着移动而非每次仅移动一位，我们可以将数组拆分成多组，组与组交相间隔，这样一组里面的元素间隔就会非常大，移动效率大大提高。

①算法描述
希尔排序又叫做缩小增量排序，其本质还是插入排序，只不过是将待排列序列按某种规则分成几个子序列，分别对这几个子序列进行直接插入排序。这个规则的体现就是增量的选取。

②算法思想
以上面的动图为例子，一开始以增量5来分割序列（这里也可以说是步长），得到几个子序列，然后分别对这5个子序列进行直接插入排序，这样就为一趟希尔排序结束；然后再以增量2来分割序列，得到几个子序列，分别对这几个子序列进行直接插入排序；最后，以增量为1来分割序列，即对上面结果的全体关键字进行一趟直接插入排序，从而完成整个希尔排序。

void shellSort (int arr[ ]，int n)
{
    int temp;
    for (int gap=n/2; gap>0; gap/=2)
    {
        for (int i=gap; i<n; ++i)
        {
            temp=arr[i] ;
            int j;
            for(j=i; j>=gap && arr[j-gap]>temp; j-=gap)
                arr[j]=arr[j-gap] ;
            arr[j]=temp;
        }
    }
}

③算法分析

• 时间复杂度分析：与增量选取有关。希尔排序的增量选取规则有很多，而考研中数据结构常见的增量选取规则有一下两个
  • 希尔（Shell）自己提出的：⌊n/2⌋、⌊n/4⌋、...、⌊n/$2^k$⌋、2、1。即每次将增量除以2并向下取整，其中n为序列长度，此时时间复杂度为$O(n^2)$。
  • 帕佩尔诺夫和斯塔舍维奇提出的：$2^{k+1}$、...、65、33、17、9、5、3、1。其中k为大于等于1的整数，$2^{k+1}$小于待排序列长度，增量序列末尾的1是额外添加的。此时时间复杂度为：$O(n^1.5)$。
• 空间复杂度分析：希尔排序的空间复杂度同直接插入排序一样，为$O(1)$。
• 缺陷：不稳定，其实上面的动图中最后结果的两个49与原来相对位置是不一样了，所以是不稳定的。
• 适用性分析：适用于数据量小、无序程度较高且无需稳定排序的数组排序。
• 另外关于希尔排序增量选取考点：
  • 增量序列的最后一个值一定取1
  • 增量序列中的值尽量没有除1之外的公因子

选择排序

简单选择排序

①算法描述

每次从无序序列中挑选出一个最小的关键字，放在有序序列的最右边，这样等无序序列中的关键字全部划归到有序序列中的时候，整个序列就变为有序了。

思路：遍历未排序的数组，选择其中的最小值，与已排序数组的后面一位元素交换。

②算法思想
如上图，整个序列原本为无序序列，从左往右扫描，找到最小的关键字，让他与无序序列中第一个关键字（刚开始无序序列第一个即为所有关键字中的第一个）交换 ，并把它归为有序序列（即图中红色的为有序序列），然后继续扫描无序序列，挑出当前无序序列（是蓝色的部分！不是红色的，红色的已经是有序序列了）中关键字最小的那个，交换无序序列中的第一个关键字，并把它归入有序序列，此时可以发现有序序列在不断变长，并且从左往右是升序的。然后继续重复上面的过程。

void selectSort (int arr[] , int n)
{
    int i,j,k;
    int temp;
    for (i=0; i<n; ++i)
    {
        k=i;
        for (j=i+1; j<n; ++j)
            if (arr[k] > arr[j] )
                k = j;
        temp = arr [i] ;
        arr[i] = arr[k];
        arr[k] = temp;
    }
}

③算法分析

• 时间复杂度分析
  • 两层循环的执行次数和初始序列没有关系，外层循环执行n次，内层循环执行n-1次，将最内层循环操作中的比较操作视为关键操作，其执行次数为$\frac{(n-1+1)(n-1)}{2}=\frac{n(n-1)}{2}$，即时间复杂度为$O(n^2)$。
  • 最好：$O(n^2)$
  • 最坏：$O(n^2)$
  • 平均：$O(n^2)$
• 空间复杂度分析
  • 算法所需的辅助存储空间不随待排序列规模的变化而变化，是个常量，所以空间复杂度为$O(1)$。
• 稳定性：稳定；稳定；只要保持最小元素遇到相同元素不发生改变即可。
• 缺陷与优点：看起来很慢，虽然实际上的确慢，但是却比插入排序快！它相比插入排序的聪明之处在于：大大地减少了移动元素的次数，每排序一个元素仅发生一次交换，有效减少了写的次数，完成排序仅需要写 n 次。尽管时间复杂度固定比插入排序高，但是它未必会比插入排序慢。
• 适用性分析：没什么适用的地方哈哈哈

堆排序

堆是一种数据结构，可以把堆看成一棵完全二叉树，这棵二叉树满足：任何一个非叶结点的值都不大于（或不小于）其左右孩子结点的值。若父亲大孩子小，则这样的堆叫做大顶堆；若父亲小孩子大，则这样的堆叫做小顶堆。

①算法描述
根据堆的定义知道，代表堆的这棵完全二叉树的根结点的值是最大（或最小）的，因此将一个无序序列调整为一个堆，就可以找出这个序列的最大（或最小）值，然后将找出的这个值交换到序列的最后（或最前），这样有序序列关键字增加一个，无序序列中关键字减少一个，对新的无序序列重复这样的操作，就实现了排序，这就是堆排序的思想。堆排序中最关键的操作时将序列调整为堆。整个排序的过程就是通过不断调整，使得不符合堆定义的完全二叉树变为符合堆定义的完全二叉树。

②算法思想

• 建堆（这里假设建大顶堆）
  • 拿上图作为例子，用一堆数建立一个完全二叉树，把他们放在数组中即可。
  • 然后找出这个完全二叉树中最后一个非叶结点的编号($⌊\frac{n}{2}⌋-1$)，又这棵完全二叉树n=8，所以这个完全二叉树中最后一个非叶结点编号为$⌊\frac{8}{2}⌋-1=3$，即图中p一开始所指的位置。
  • 然后按照下面的规则处理：观察p所指的结点以及其孩子结点的关键字值，如果p所指结点的关键字值比其孩子结点的关键字值最大的那个要小，假设这个关键字值最大的孩子结点叫a，则将p所指结点与a交换。
  • 比如一开始p指向97，其孩子关键字值为49，则没必要交换。
  • 然后p往前移动一个编号的位置，此时p来到了65，比其孩子结点关键字值13、27还要大，也没必要交换。
  • 然后p继续前移一个编号的位置，此时p来到了38，其孩子结点一个是97，另外一个是76，所以38和97交换。
  • 这时候p不要前移位置！我们需要观察被交换到下面的那个结点值，看看他是否小于其当前的孩子结点的关键字值，如果小于则继续交换，则此时被交换到下面的那个结点值为38，其孩子结点为49，38<49，则继续交换。
  • 然后38是叶子结点无孩子结点了，无需要再和任何结点进行交换了。
  • 这时候p继续往前一个编号的位置，此时p来到了根结点49，他的两个孩子的关键字值分别是97和65，让49与较大的孩子结点97交换。
  • 换下去之后继续观察，此时49有两个孩子结点，其值一个是49一个是76，则49与76交换。
  • 换下去之后继续观察，此时已经变成了叶子结点，不需要继续进行交换了。由于这时候p已经来到了第一个结点也就是根结点，则此时建堆结束，此时得到了一个大顶堆。

• 插入结点
  • 假如要在刚才建好的堆中插入新的结点，其关键字值是85，则按照下面的步骤来做：首先把这个结点放在所有的结点的最后面，最后即参照所有结点的编号来说的，即挂在结点49（第一个49）的右孩子那里，挂上。
  • 然后标记出这个新结点到根结点的路径，然后执行一趟类似于冒泡排序的操作。也就是说拿刚插入结点与其父结点关键字的值比较，如果其关键字值比其父结点关键字值还要大，那就与其父结点交换，交换之后重复同样的过程，直到其关键字的值不大于其父结点的关键字的值位置为止。
  • 上图中，则：85的父结点：49，85>49，交换；此时其父结点的关键字值为76，85>76，交换；此时其父结点关键字值为97，85<97，无需交换，插入过程结束。

• 删除结点
  • 假如现在要把堆中的根结点删掉，可以按照下面的步骤进行。
  • 首先把这个结点拿出来，放在一边，然后用此时堆中最后一个结点即49填充空位置。
  • 然后对49这个结点进行一次堆的调整。（之前建堆的时候已经用过了，就是从某一个结点开始按照堆的规则让其与孩子结点交换直到交换后的结果满足堆的规则为止）。
  • 开始对49调整，他的左右孩子结点分别是85、65两个都大于49，则与较大的那个交换，49与85交换，此时49的孩子结点分别是76、49，则与76交换，交换后它的孩子结点是38，49>38，无需交换。此时删除结点结束。
  • 值得一说的是：删除操作，只需要对这个填充的结点进行一次调整即可，而不需要对其他结点进行调整

void sift(int arr[], int 1ow, int high) //调整函数
{
    int i=low,j=2*1+1;
    int temp=arr[i];
    while(j <= high)
    {
        if(j<high && arr[j]<arr[j+1])
            ++j;
        if(temp<arr[j])
        {
            arr [i] = arr[j] ;
            i=j;
            j=2*i+1;
        }
        else
            break;
    }
    arr[i] = temp;
}


void heapSort(int arr[], int n) //堆排序函数
{
    int i;
    int temp;
    for(i=n/2-1; i>=0; --i)
        sift(arr, i, n-1);
    for(i-n-1; i>0; --i)
    {
        temp = arr [0] ;
        arr[0]-arr[1];
        arr(1]=temp;
        sift (arr, 0,i-1) ;
    }
}

③算法分析

• 时间复杂度分析
  • 最好：$O(nlog_2n)$
  • 最坏：$O(nlog_2n)$
  • 平均：$O(nlog_2n)$
• 空间复杂度分析：算法所需的辅助存储空间不随待排序列规模的变化而变化，是个常量，为$O(1)$
• 稳定性：不稳定；在堆中，相同大小元素位置是不定的。
• 缺陷与优点：堆排序有点像是逆序排序，有的人觉得堆顶为最大元素，那么将堆顶往后移，后面重新构建堆就可以一步步排出从大到小的数组；但是从头初始化堆的成本远高于取出最大值再维护堆的成本；因此堆排序略微有些复杂，不容易被初学者接受。
• 适用性分析：堆排序适合的场景是关键字数很多的情况，典型的例子是从10000个关键字中选出前10个最小的，这种情况用堆排序最好。如果关键字较少，则不提倡用堆排序。

交换排序

冒泡排序

①算法描述

冒泡排序又叫起泡排序。他是通过一系列的“交换”动作完成的。首先第一个关键字第二个关键字比较，如果第一个大，则二者交换，否则不交换..。一直按这种方式进行下去，最终最大的那个关键字被交换到了最后，一趟冒泡排序完成。经过多趟这样的排序，最终使整个序列有序，这个过程，大的关键字像石头一样沉底，小的关键字像气泡一样逐渐向上“浮动”，冒泡排序的名字由此而来。

最暴力的、最容易实现的解法了，循环 n 次，每次冒出 1 个最大值。

②算法思想

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3. 针对所有的元素重复以上的步骤，除了最后一个；
4. 重复步骤1~3，直到排序完成。

冒泡排序算法结束的条件是在一趟排序过程中没有发生关键字交换。

void bubleSort (int arr[], int n)
{
    int i,j,flag;
    int temp;
    for(i=n-1 ; i>=1 ; --i)
    {
        flag = 0;
        for (j=1; j<=i; ++j)
        if(arr[j-1] > arr [j])
        {
            temp = arr[j] ;
            arr[j] = arr[j-1] ;
            arr [j-1] =temp ;
            flag = 1;
        }

        if (flag == 0)
            return ;
    }
}

③算法分析

• 时间复杂度分析
  • 最好：$O(n)$，待排序列有序。
  • 最坏：$O(n^2)$，待排序列逆序。
  • 平均：$O(n^2)$
• 空间复杂度分析：由算法代码可以看出，额外辅助空间只有一个temp，因此为$O(1)$。
• 稳定性：稳定，如果两个元素相等，则先将后面的元素推向最后。
• 缺陷与优点：慢得出奇，冒泡排序相邻交换的排序方式，使得它每一轮排序，最多消除 $n-1$ 个逆序对，$0.5$无序程度的数组逆序对的数量为 $\frac{n(n−1)}{4}$，这表明它永远需要 $n$ 轮排序，时间复杂度固定为$O(n^2)$，而每一轮排序平均发生 $\frac{n}{2}$ 次写入，平均完成一次排序需要进行 $\frac{n(n−1)}{2}$ 次写入，比插入排序还要慢，堪比蜗牛。
• 适用性分析：比插入排序还慢，沦为本文最慢的算法，一般是给初学编程者学习循环语法用。

快速排序

①算法描述
快速排序也是“交换”类的排序，它通过多次划分操作实现排序。以升序为例子，其执行流程可以概括为：每一趟选择当前所有子序列中的一个关键字（通常是第一个）作为枢轴，将子序列中比枢轴小的移到枢轴前边，比枢轴大的移到枢轴后边；当本趟所有子序列都被枢轴以上述规则划分完毕后会得到新的一组更短的子序列，他们成为下一趟划分的初始序列集。

②算法思想

以下面例子感受快排思想：

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

• 从数列中挑出一个元素，称为 “基准”（pivot）；
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

void QuickSort(int R[], int low, int high)
{
    int temp;
    int i=low,j=high;
    if (low < high)
    {
        temp = arr[low] ;
        while(i<j)
        {
            while (j > i && arr[j] >= temp) --j ;
            if(i < j)
            {
                arr[i]=arr[j];
                ++i;
            }
            while(i<j && arr[i]<temp) ++i;
            if(i<j)
            {
                arr[j]=arr[i];
                --j;
            }        
        }
        arr[i]=temp;
        QuickSort (arr,low,i-1);
        QuickSort (arr,i+1,high);
    }
}

快速排序中队每一个子序列的一次划分算作一趟排序，每一趟结束之后有一个关键字到达最终位置。

③算法分析

• 时间复杂度分析
  • 最好：$O(nlog_2n)$，待排序列越接近无序，本算法效率越高！
  • 最坏：$O(n^2)$，待排序列越接近有序，本算法效率越低！
  • 平均：$O(n^2)$
• 空间复杂度分析：$O(log2_n)$。快速排序是递归进行的，递归需要栈的辅助，因此他需要的辅助空间比前面几类算法大。
• 稳定性：不稳定，由于远距离交换的缘故，二相同元素的最终顺序是难以预测的。
• 缺陷与优点：快速作为排序算法在远距离交换这一点是做的不错的，但是仍会随着无序度或数组大小的上升而花费更多时间。因为：快速排序的效率取决于中介的选取是否合理，如果中介的取值太大/太小，就会导致数组拆分得很不均匀，甚至是根本没有拆分！因此我们可以优化快速排序算法，通过一系列初始操作，让中介的取值接近于中位数，甚至是设置多个中介，分多个区间！
• 适用性分析：适用于均匀的、规模较小的数组排序。

归并排序

二路归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

①算法描述

• 把长度为n的输入序列分成两个长度为n/2的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

②算法思想
可以参考下面的图作为例子来了解整个归并排序的过程

由以上分析可知，归并排序可以看作一个分而治之的过程：先将整个序列分为两半，对每一半分别进行归并排序，将得到两个有序序列，然后将这两个序列归并成一个序列即可。假设待排序列存在数组A中，用low和high两个整型变量代表需要进行归并排序的关键字范围，由此可以写出如下代码：

void mergeSort(int A[], int low ,int high)
{
    if(low < high)
    {
        int mid=(low + high)/2;
        mergeSort(A,low,mid);
        mergeSort(A,mid+1,high);
        mergeSort(A,low,mid,high);
    }
}

③算法分析

• 时间复杂度分析
  • 最好：$O(nlog_2n)$
  • 最坏：$O(nlog_2n)$
  • 平均：$O(nlog_2n)$
• 空间复杂度分析：$O(n)$。因为归并排序需要转存整个待排序列，因此空间复杂度为$O(n)$。
• 稳定性：稳定，若左部分元素与右部分相同，则先取左部分。
• 缺陷与优点：由于拆分和归并操作对于小数组而言步骤过多，因此归并排序在小规模排序中并不是速度的顶峰。
• 适用性分析：适用于无序程度高，需求稳定、快速的大规模排序。

基数排序

基数排序

基数排序的思想是“多关键字排序”。对所有数据的各个位数使用容器（桶）进行归类，使数据从个位至高位逐渐有序化，低位完成归类后，对高位进行归类时，低位已自动有序化。

①算法描述

• 先初始化十个桶，因为十进制最多从 0 ~ 9；
• 根据个位填满（这个过程叫分配）这些桶，从第 0 个桶开始将所有元素取出（这个过程叫收集），取出顺序由桶底至桶顶。
• 再根据十位、百位、千位… 直至最高位数；最后一次取出即完成排序。

②算法思想
下面通过一个例子来体会基数排序的过程：

③算法分析

• 时间复杂度分析
  • 最好：$O(d(n+r_d))$
  • 最坏：$O(d(n+r_d))$
  • 平均：$O(d(n+r_d))$
• 空间复杂度分析：$O(r_d)$。其中n为序列中的关键字数；d为关键字的关键字位数，如930，由3位组成，d=3；$r_d$为关键字基的个数，这里的基值指的构成关键字的符号，如关键字为数值时，构成关键字的符号就是0~9这些数字，一共有十个，即$r_d=10$。
• 稳定性：稳定，相同元素入桶顺序、出桶顺序与其在原数组中的顺序相同。
• 缺陷与优点：对于极差极大的数组，应用基数排序后果是不可想象的，你会发现到最后所有数都装在 0 号桶中，严重影响性能！
• 适用性分析：无序程度低、最高位位数小的数组，与数组规模无关。

各种内部排序算法的比较

按照方法分

• 使用比较方式进行排序的算法：

插入排序、希尔排序、堆排序、选择排序、冒泡排序、鸡尾酒排序、快速排序、归并排序

• 使用非比较方式进行排序的算法：

基数排序（桶排序）

• 使用分治思想的算法：

快速排序、归并排序

• 借助树进行排序的算法：

堆排序

各速度比较

用途归纳

• 小规模数组：

快速排序、基数排序

• 中规模数组：

随机快速排序、堆排序、归并排序

• 大规模数组：

归并排序

• 思想借鉴：

希尔排序、堆排序、归并排序

一些特殊总结

• 复杂度总结
  1. 时间复杂度
     • 平均情况下：快速排序、希尔排序（复杂度了解即可）、归并排序和堆排序的时间复杂度均为$O(nlog_2n)$，其他都是$O(n^2)$。一个特殊的是基数排序，其时间复杂度为$O(d(n+r_d))$。
     • 最坏情况下：快速排序的时间复杂度为$O(n^2)$，其他和平均情况下相同。
     • 故事助记：如军训时，教官说：“快些以$nlog_2n$的速度归队。”其中，“快”指快速排序，“些”指希尔排序，“归”指归并排序，“队”指“堆排序”，这四种排序的平均复杂度都是$nlog_2n$。
  2. 空间复杂度
     • 记住几个特殊的就好，快速排序为$O(nlog_2n)$，归并排序为$O(n)$，基数排序为$O(r_d)$，其他都是$O(1)$。
  3. 其他
     • 直接插容易插变成$O(n)$，冒泡起的好变成$O(n)$，所谓“容易插”或“冒得好”都是指初始序列都已经有序列。
• 算法稳定性总结
  • 一句话记忆：“考研复习痛苦啊，情绪不稳定，快些选一堆好友来聊天吧”。这里，“快”指快速排序，“些”指希尔排序，“选”指简单排序，“堆”指堆排序，这4种是不稳定得，其他自然是稳定的。
• 其他细节（与排斥原理有关）
  • 经过一趟排序，能够保证一个关键字到达最终位置，这样的排序是交换类的那两种（冒泡、快速）和选择类的那两种（简单选择、堆）。
  • 排序算法的关键字比较次数和原始序列无关-简单选择排序和折半插入排序
  • 排序算法的排序趟数和原始序列有关-交换类的排序
• 再次比较直接插入排序和折半插入排序
  • 二者最大的区别在于查找插入位置的方式不同。直接插入按顺序查找的方式，而折半插入按折半查找的方式。
• 一个有用的结论
  • 借助于“比较”进行排序的算法，在最坏情况下的时间复杂度至少为$O(nlog_2n)$。

外部排序

计算机的存储部分都分为内存和外存。这里所介绍得外部排序算法针对于体积过大以至内存装不下的文件，在对其包含的记录进行排序时所用到的算法。

由于设计到内存和外存之间数据的传输，所以这里围绕提高外部排序的整体效率，详细介绍外部排序的整个过程以及优化的算法。

所谓外部排序，即对外存中得记录进行排序（相对于内部排序而言）。有了内部排序算法，为什么还要外部排序？因为外存中记录规模太大，内存放不下。外部排序可以概括为一句话：将内存作为空间来辅助外存数据的排序。

多路归并排序

外部排序最常用的算法是归并排序。之所以归并排序常用，是因为他不需要将全部记录都读入内存即可完成排序。因此，可以解决由于内存空间不足导致得无法对大规模记录排序的问题。

即外排序通常采用的是一种“排序-归并”的策略。

①算法描述

• 在排序阶段，先读入能放在内存中的数据量，将其排序输出到一个临时文件，依此进行，将待排序数据组织为多个有序的临时文件；
• 尔后在归并阶段将这些临时文件组合为一个大的有序文件，也即排序结果。

②算法思想

假定现在有20个数据的文件A：{5 11 0 18 4 14 9 7 6 8 12 17 16 13 19 10 2 1 3 15}，但一次只能使用仅装4个数据的内容，所以，我们可以每趟对4个数据进行排序，即5路归并，具体方法如下述步骤：

• 我们先把“大”文件A，分割为a1，a2，a3，a4，a5等5个小文件，每个小文件4个数据
  • a1文件为：5 11 0 18
  • a2文件为：4 14 9 7
  • a3文件为：6 8 12 17
  • a4文件为：16 13 19 10
  • a5文件为：2 1 3 15
• 然后依次对5个小文件分别进行排序
  • a1文件完成排序后：0 5 11 18
  • a2文件完成排序后：4 7 9 14
  • a3文件完成排序后：6 8 12 17
  • a4文件完成排序后：10 13 16 19
  • a5文件完成排序后：1 2 3 15
• 最终多路归并，完成整个排序
  • 整个大文件A文件完成排序后：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

对于外部排序算法来说，影响整体排序效率的因素主要取决于读写外存的次数，即访问外存的次数越多，算法花费的时间就越多，效率就越低。

对于同一个文件来说，对其进行外部排序时访问外存的次数同归并的次数成正比，即归并操作的次数越多，访问外存的次数就越多。图 1 中使用的是 2-路平衡归并的方式，举一反三，还可以使用 3-路归并、4-路归并甚至是 10-路归并的方式。

对比 图 1 和图 2可以看出，对于 k-路平衡归并中 k 值得选择，增加 k 可以减少归并的次数，从而减少外存读写的次数，最终达到提高算法效率的目的。除此之外，一般情况下对于具有 m 个初始归并段进行 k-路平衡归并时，归并的次数为：$s=⌊log_km⌋$（其中 s 表示归并次数）。

从公式上可以判断出，想要达到减少归并次数从而提高算法效率的目的，可以从两个角度实现：

• 增加 k-路平衡归并中的 k 值；
• 尽量减少初始归并段的数量 m，即增加每个归并段的容量；

置换选择排序

如果要想减小 m 的值，在外部文件总的记录数 n 值一定的情况下，只能增加每个归并段中所包含的记录数 l。而对于初始归并段的形成，就不能再采用上一章所介绍的内部排序的算法，因为所有的内部排序算法正常运行的前提是所有的记录都存在于内存中，而内存的可使用空间是一定的，如果增加 l 的值，内存是盛不下的。

所以要另想它法，探索一种新的排序方法：置换—选择排序算法。

例如已知初始文件中总共有 24 个记录，假设内存工作区最多可容纳 6 个记录，按照之前的选择排序算法最少也只能分为 4 个初始归并段。而如果使用置换—选择排序，可以实现将 24 个记录分为 3 个初始归并段，如图 1 所示：

置换—选择排序算法的具体操作过程为：

1. 首先从初始文件中输入 6 个记录到内存工作区中；
2. 从内存工作区中选出关键字最小的记录，将其记为 MINIMAX 记录；
3. 然后将 MINIMAX 记录输出到归并段文件中；
4. 此时内存工作区中还剩余 5 个记录，若初始文件不为空，则从初始文件中输入下一个记录到内存工作区中；
5. 从内存工作区中的所有比 MINIMAX 值大的记录中选出值最小的关键字的记录，作为新的 MINIMAX 记录；
6. 重复过程 3—5，直至在内存工作区中选不出新的 MINIMAX 记录为止，由此就得到了一个初始归并段；
7. 重复 2—6，直至内存工作为空，由此就可以得到全部的初始归并段。

拿图 1 中的初始文件为例，首先输入前 6 个记录到内存工作区，其中关键字最小的为 29，所以选其为 MINIMAX 记录，同时将其输出到归并段文件中，如下图所示：

此时初始文件不为空，所以从中输入下一个记录 14 到内存工作区中，然后从内存工作区中的比 29 大的记录中，选择一个最小值作为新的 MINIMAX 值输出到 归并段文件中，如下图所示：

初始文件还不为空，所以继续输入 61 到内存工作区中，从内存工作区中的所有关键字比 38 大的记录中，选择一个最小值作为新的 MINIMAX 值输出到归并段文件中，如下图所示：

如此重复性进行，直至选不出 MINIMAX 值为止，如下图所示:

当选不出 MINIMAX 值时，表示一个归并段已经生成，则开始下一个归并段的创建，创建过程同第一个归并段一样，这里不再赘述。

在上述创建初始段文件的过程中，需要不断地在内存工作区中选择新的 MINIMAX 记录，即选择不小于旧的 MINIMAX 记录的最小值，此过程需要利用“败者树”来实现。

最佳归并树

通过上一节对置换-选择排序算法的学习了解到，通过对初始文件进行置换选择排序能够获得多个长度不等的初始归并段，相比于按照内存容量大小对初始文件进行等分，大大减少了初始归并段的数量，从而提高了外部排序的整体效率。

本节带领大家思考一个问题：无论是通过等分还是置换-选择排序得到的归并段，如何设置它们的归并顺序，可以使得对外存的访问次数降到最低？

例如，现有通过置换选择排序算法所得到的 9 个初始归并段，其长度分别为：9，30，12，18，3，17，2，6，24。在对其采用 3-路平衡归并的方式时可能出现如图 1 所示的情况：

假设在进行平衡归并时，操作每个记录都需要单独进行一次对外存的读写，那么图 1 中的归并过程需要对外存进行读或者写的次数为： （9+30+12+18+3+17+2+6+24）*2*2=484（图 1 中涉及到了两次归并，对外存的读和写各进行 2 次） 从计算结果上看，对于图 1 中的 3 叉树来讲，其操作外存的次数恰好是树的带权路径长度的 2 倍。所以，对于如何减少访问外存的次数的问题，就等同于考虑如何使 k-路归并所构成的 k 叉树的带权路径长度最短。

若想使树的带权路径长度最短，就是构造赫夫曼树。

若对上述 9 个初始归并段构造一棵赫夫曼树作为归并树，如图 2 所示：

依照图 2 所示，其对外存的读写次数为： (2*3+3*3+6*3+9*2+12*2+17*2+18*2+24*2+30)*2=446 通过以构建赫夫曼树的方式构建归并树，使其对读写外存的次数降至最低（k-路平衡归并，需要选取合适的 k 值，构建赫夫曼树作为归并树）。所以称此归并树为最佳归并树。

败者树

对于外部排序算法来说，其直接影响算法效率的因素为读写外存的次数，即次数越多，算法效率越低。若想提高算法的效率，即减少算法运行过程中读写外存的次数，可以增加 k –路平衡归并中的 k 值。

但是经过计算得知，如果毫无限度地增加 k 值，虽然会减少读写外存数据的次数，但会增加内部归并的时间，得不偿失。

例如在上节中，对于 10 个临时文件，当采用 2-路平衡归并时，若每次从 2 个文件中想得到一个最小值时只需比较 1 次；而采用 5-路平衡归并时，若每次从 5 个文件中想得到一个最小值就需要比较 4 次。以上仅仅是得到一个最小值记录，如要得到整个临时文件，其耗费的时间就会相差很大。

为了避免在增加 k 值的过程中影响内部归并的效率，在进行 k-路归并时可以使用“败者树”来实现，该方法在增加 k 值时不会影响其内部归并的效率。

败者树是树形选择排序的一种变形，本身是一棵完全二叉树。

在树形选择排序一节中，对于无序表{49，38，65，97，76，13，27，49}创建的完全二叉树如图 1 所示，构建此树的目的是选出无序表中的最小值。

这棵树与败者树正好相反，是一棵“胜者树”。因为树中每个非终端结点（除叶子结点之外的其它结点）中的值都表示的是左右孩子相比较后的较小值（谁最小即为胜者）。例如叶子结点 49 和 38 相对比，由于 38 更小，所以其双亲结点中的值保留的是胜者 38。然后用 38 去继续同上层去比较，一直比较到树的根结点。

而败者树恰好相反，其双亲结点存储的是左右孩子比较之后的失败者，而胜利者则继续同其它的胜者去比较。

例如还是图 1 中，叶子结点 49 和 38 比较，38 更小，所以 38 是胜利者，49 为失败者，但由于是败者树，所以其双亲结点存储的应该是 49；同样，叶子结点 65 和 97 比较，其双亲结点中存储的是 97 ，而 65 则用来同 38 进行比较，65 会存储到 97 和 49 的双亲结点的位置，38 继续做后续的胜者比较，依次类推。

如图 2 所示为一棵 5-路归并的败者树，其中 b0—b4 为树的叶子结点，分别为 5 个归并段中存储的记录的关键字。 ls 为一维数组，表示的是非终端结点，其中存储的数值表示第几归并段（例如 b0 为第 0 个归并段）。ls[0] 中存储的为最终的胜者，表示当前第 3 归并段中的关键字最小。

当最终胜者判断完成后，只需要更新叶子结点 b3 的值，即导入关键字 15，然后让该结点不断同其双亲结点所表示的关键字进行比较，败者留在双亲结点中，胜者继续向上比较。

例如，叶子结点 15 先同其双亲结点 ls[4] 中表示的 b4 中的 12 进行比较，12 为胜利者，则 ls[4] 改为 15，然后 12 继续同 ls[2] 中表示的 10 做比较，10 为胜者，然后 10 继续同其双亲结点 ls[1] 表示的 b1（关键字 9）作比较，最终 9 为胜者。整个过程如下图所示：

为了防止在归并过程中某个归并段变为空，处理的办法为：可以在每个归并段最后附加一个关键字为最大值的记录。这样当某一时刻选出的冠军为最大值时，表明 5 个归并段已全部归并完成。（因为只要还有记录，最终的胜者就不可能是附加的最大值）

参考

• 各大排序算法的比较、研究与实现 - prettyant
• 十大经典排序算法（动图演示）- 一像素
• 一眨眼的功夫了解什么是外部排序算法 - 解学武
• 编程之法：面试和算法心得-外排序
• 天勤数据结构高分笔记 - 率辉