数据结构-排序

考研常考排序算法

Table of Contents

数据结构-排序

排序的基本概念。

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

image.png

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

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

插入类的排序 交换类的排序 选择类的排序 归并类的排序 基数类的排序

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

插入排序

插入排序（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;

    }

}

③算法性能分析

折半插入排序

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

②算法分析

希尔排序

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

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

②算法思想
以上面的动图为例子，一开始以增量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;

        }

    }

}

③算法分析

选择排序

简单选择排序

①算法描述

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

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

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

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;

    }

}

③算法分析

堆排序

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

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

②算法思想

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) ;

    }

}

③算法分析

交换排序

冒泡排序

①算法描述

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

最暴力的、最容易实现的解法了，循环 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 ;

    }

}

③算法分析

快速排序

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

②算法思想

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

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

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);

    }

}

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

③算法分析

归并排序

二路归并排序

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

    }

}

③算法分析

基数排序

基数排序

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

①算法描述

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

③算法分析

各种内部排序算法的比较

按照方法分

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

基数排序（桶排序）

快速排序、归并排序

堆排序

各速度比较

用途归纳

快速排序、基数排序

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

归并排序

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

一些特殊总结

外部排序

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

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

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

多路归并排序

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

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

①算法描述

②算法思想

假定现在有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路归并，具体方法如下述步骤：

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

计算机中处理数据的为中央处理器（CPU），如若需要访问外存中的数据，只能通过将数据从外存导入内存，然后从内存中获取。同时由于内存读写速度快，外存读写速度慢的差异，更加影响了外部排序的效率。

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

image.png
image.png

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

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

其增加 k 值的想法引申出了一种外部排序算法：多路平衡归并算法；增加数量 m 的想法引申出了另一种外部排序算法：置换-选择排序算法。

置换选择排序

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

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

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

image.png

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

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

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

image.png

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

image.png

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

image.png

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

image.png

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

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

最佳归并树

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

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

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

image.png

提示：图 1 中的叶子结点表示初始归并段，各自包含记录的长度用结点的权重来表示；非终端结点表示归并后的临时文件。

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

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

在学习赫夫曼树时，只是涉及到了带权路径长度最短的二叉树为赫夫曼树，其实扩展到一般情况，对于 k 叉树，只要其带权路径长度最短，亦可以称为赫夫曼树。

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

image.png

依照图 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 去继续同上层去比较，一直比较到树的根结点。

image.png

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

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

胜者树和败者树的区别就是：胜者树中的非终端结点中存储的是胜利的一方；而败者树中的非终端结点存储的是失败的一方。而在比较过程中，都是拿胜者去比较。

image.png

如图 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 为胜者。整个过程如下图所示：

image.png

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

参考

tech 408数据结构