数据结构常考题 —— 八种经典内部排序算法

朱雀 2022-05-18 06:36 114阅读 0赞

## 经典排序算法 ##

我们经典的排序有**内部排序**和**外部排序**，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。  
![这里写图片描述][70]  
算法复杂度如下图：  
![算法复杂度][70 1]  
下面我们一一来总结这每一种算法：

## 一、插入排序 ##

插入排序的基本方法是：每步将一个待排序的记录，按其排序码大小，插到前面已经排序的文件中的适当位置，直到全部插入完为止。

**1.直接插入排序**  
原理：从待排序的n个记录中的第二个记录开始，依次与前面的记录比较并寻找插入的位置，每次外循环结束后，将当前的数插入到合适的位置。

稳定性：稳定排序。  
时间复杂度： O(n)至，平均时间复杂度是。  
最好情况：当待排序记录已经有序，这时需要比较的次数最少。  
最坏情况：如果待排序记录为逆序，则比较次数最多。

代码：

//A：输入数组，len:数组长度
    void insertSort(int A[],int len)
    {
        int temp;
        for(int i=1;i<len;i++)
        {
          int j=i-1;
          temp=A[i]; 
          //查找到要插入的位置
          while(j>=0&&A[j]>temp)
          {
              A[j+1]=A[j];
              j--;
          }
          if(j!=i-1)
            A[j+1]=temp;
        }
    }

**2.Shell排序**  
Shell 排序又称缩小增量排序, 是对直接插入排序的改进。这是第一个突破O(n2)的排序算法，是简单插入排序的改进版。  
**它与插入排序的不同之处在于，它会优先比较距离较远的元素。**

原理： Shell排序法是对相邻指定距离(称为增量)的元素进行比较，并不断把增量缩小至1，完成排序。

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

*  选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
 *  按增量序列个数k，对序列进行k 趟排序；
 *  每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
 *  在直接插入排序的基础上，将直接插入排序中的1全部改变成增量d即可，因为Shell排序最后一轮的增量d就为1。

稳定性：不稳定排序。  
时间复杂度：O(n\*n)。Shell排序算法的时间复杂度分析比较复杂，实际所需的时间取决于各次排序时增量的个数和增量的取值。研究证明，若增量的取值比较合理，Shell排序算法的时间复杂度约为O(n)。

对于增量的选择，Shell 最初建议增量选择为n/2，并且对增量取半直到 1。

//A：输入数组，len:数组长度，d:初始增量(分组数)
    void shellSort(int A[],int len, int d)
    {
        for(int inc=d;inc>0;inc/=2){        //循环的次数为增量缩小至1的次数
            for(int i=inc;i<len;++i){       //循环的次数为第一个分组的第二个元素到数组的结束
                int j=i-inc;
                int temp=A[i];
                while(j>=0&&A[j]>temp)
                {
                    A[j+inc]=A[j];
                    j=j-inc;
                }
                if((j+inc)!=i)//防止自我插入
                    A[j+inc]=temp;//插入记录
            }
        }

## 二、选择排序 ##

选择类排序的基本方法是：每步从待排序记录中选出排序码最小的记录，顺序放在已排序的记录序列的后面，知道全部排完。  
**1.简单选择排序**  
原理：从所有记录中选出最小的一个数据元素与第一个位置的记录交换；然后在剩下的记录当中再找最小的与第二个位置的记录交换，循环到只剩下最后一个数据元素为止。

稳定性：不稳定排序。  
时间复杂度： 最坏、最好和平均复杂度均为O(n\*n)，因此，简单选择排序也是常见排序算法中性能最差的排序算法。简单选择排序的比较次数与文件的初始状态没有关系，在第i趟排序中选出最小排序码的记录，需要做n-i次比较。

void selectSort(int A[],int len)
    {
        int i,j,k;
        for(i=0;i<len;i++){ 
           k=i;
           for(j=i+1;j<len;j++){ 
               if(A[j]<A[k])
                   k=j;
           }
           if(i!=k){
               A[i]=A[i]+A[k]; //不需要多余变量
               A[k]=A[i]-A[k];
               A[i]=A[i]-A[k];
           }
        }
    }

2、堆排序  
直接选择排序中，第一次选择经过了n-1次比较，只是从排序码序列中选出了一个最小的排序码，而没有保存其他中间比较结果。所以后一趟排序时又要重复许多比较操作，降低了效率。J. Willioms和Floyd在1964年提出了堆排序方法，避免这一缺点。

堆的性质：  
（1）性质：完全二叉树或者是近似完全二叉树；  
（2）分类：大顶堆：父节点不小于子节点键值，小顶堆：父节点不大于子节点键值；  
图展示一个最小堆：  
![这里写图片描述][70 2]  
（3）左右孩子：没有大小的顺序。

（4）堆的存储  
一般都用数组来存储堆，i结点的父结点下标就为。它的左右子结点下标分别为 和 。如第0个结点左右子结点下标分别为1和2。  
![这里写图片描述][70 3]  
（5）堆的操作  
建立：  
以最小堆为例，如果以数组存储元素时，一个数组具有对应的树表示形式，但树并不满足堆的条件，需要重新排列元素，可以建立“堆化”的树。  
![这里写图片描述][70 4]  
插入：  
将一个新元素插入到表尾，即数组末尾时，如果新构成的二叉树不满足堆的性质，需要重新排列元素，下图演示了插入15时，堆的调整。  
![这里写图片描述][70 5]  
删除：  
堆排序中，删除一个元素总是发生在堆顶，因为堆顶的元素是最小的（小顶堆中）。表中最后一个元素用来填补空缺位置，结果树被更新以满足堆条件。  
![这里写图片描述][70 6]  
稳定性：不稳定排序。

插入代码实现：  
每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列，现在的任务是将这个新数据插入到这个有序数据中，这就类似于直接插入排序中将一个数据并入到有序区间中，这是节点“上浮”调整。不难写出插入一个新数据时堆的调整代码：

//新加入i结点,其父结点为(i-1)/2
    //参数：a：数组，i：新插入元素在数组中的下标 
    void minHeapFixUp(int a[], int i)  
    {  
        int j, temp;  
        temp = a[i];  
        j = (i-1)/2;      //父结点 
        while (j >= 0 && i != 0)  
        {  
            if (a[j] <= temp)//如果父节点不大于新插入的元素，停止寻找 
                break;  
            a[i]=a[j];     //把较大的子结点往下移动,替换它的子结点 
            i = j;  
            j = (i-1)/2;  
        }  
        a[i] = temp;  
    }

因此，插入数据到最小堆时：

//在最小堆中加入新的数据data 
    //a：数组，index：插入的下标，
    void minHeapAddNumber(int a[], int index, int data)  
    {  
        a[index] = data;  
        minHeapFixUp(a, index);  
    }

删除代码实现：  
按定义，堆中每次都只能删除第0个数据。为了便于重建堆，实际的操作是将数组最后一个数据与根结点，然后再从根结点开始进行一次从上向下的调整。

调整时先在左右儿子结点中找最小的，如果父结点不大于这个最小的子结点说明不需要调整了，反之将最小的子节点换到父结点的位置。此时父节点实际上并不需要换到最小子节点的位置，因为这不是父节点的最终位置。但逻辑上父节点替换了最小的子节点，然后再考虑父节点对后面的结点的影响。相当于从根结点将一个数据的“下沉”过程。下面给出代码：

//a为数组，从index节点开始调整,len为节点总数 从0开始计算index节点的子节点为 2*index+1, 2*index+2,len/2-1为最后一个非叶子节点 
    void minHeapFixDown(int a[],int len,int index){
        if(index>(len/2-1))//index为叶子节点不用调整
            return;
        int tmp=a[index];
        int lastIndex=index;
        while(index<=(len/2-1)){ //当下沉到叶子节点时，就不用调整了
            if(a[2*index+1]<tmp) //如果左子节点大于该节点
                lastIndex = 2*index+1;
            //如果存在右子节点且大于左子节点和该节点
            if(2*index+2<len && a[2*index+2]<a[2*index+1]&& a[2*index+2]<tmp)
                lastIndex = 2*index+2;
            if(lastIndex!=index){  //如果左右子节点有一个小于该节点则设置该节点的下沉位置
                a[index]=a[lastIndex];
                index=lastIndex;
            }else break;  //否则该节点不用下沉调整
        }
        a[lastIndex]=tmp;//将该节点放到最后的位置
    }

根据思想，可以有不同版本的代码实现，以上是和孙凛同学一起讨论出的一个版本，在这里感谢他的参与，读者可另行给出。个人体会，这里建议大家根据对堆调整的过程的理解，写出自己的代码，切勿看示例代码去理解算法，而是理解算法思想写出代码，否则很快就会忘记。

建堆：  
有了堆的插入和删除后，再考虑下如何对一个数据进行堆化操作。要一个一个的从数组中取出数据来建立堆吧，不用！先看一个数组，如下图：  
![这里写图片描述][70 7]

很明显，对叶子结点来说，可以认为它已经是一个合法的堆了即20，60， 65， 4， 49都分别是一个合法的堆。只要从A\[4\]=50开始向下调整就可以了。然后再取A\[3\]=30，A\[2\] = 17，A\[1\] = 12，A\[0\] = 9分别作一次向下调整操作就可以了。下图展示了这些步骤：  
![这里写图片描述][70 8]

写出堆化数组的代码：

//建立最小堆
    //a:数组，n：数组长度
    void makeMinHeap(int a[], int n)  
    {  
        for (int i = n/2-1; i >= 0; i--)  
            minHeapFixDown(a, i, n);  
    }

（6）堆排序的实现  
由于堆也是用数组来存储的，故对数组进行堆化后，第一次将A\[0\]与A\[n - 1\]交换，再对A\[0…n-2\]重新恢复堆。第二次将A\[0\]与A\[n – 2\]交换，再对A\[0…n - 3\]重新恢复堆，重复这样的操作直到A\[0\]与A\[1\]交换。由于每次都是将最小的数据并入到后面的有序区间，故操作完成后整个数组就有序了。有点类似于直接选择排序。

因此，完成堆排序并没有用到前面说明的插入操作，只用到了建堆和节点向下调整的操作，堆排序的操作如下：

//array:待排序数组，len：数组长度
    void heapSort(int array[],int len){
        //建堆
        makeMinHeap(array, len); 
        //根节点和最后一个叶子节点交换，并进行堆调整，交换的次数为len-1次
        for(int i=0;i<len-1;++i){
            //根节点和最后一个叶子节点交换
            array[0] += array[len-i-1];  
            array[len-i-1] = array[0]-array[len-i-1];  
            array[0] = array[0]-array[len-i-1];
    
            //堆调整
            minHeapFixDown(array, 0, len-i-1);  
        }
    }

（7）堆排序的性能分析  
由于每次重新恢复堆的时间复杂度为O(logN)，共N - 1次堆调整操作，再加上前面建立堆时N / 2次向下调整，每次调整时间复杂度也为O(logN)。两次次操作时间相加还是O(N \* logN)。故堆排序的时间复杂度为O(N \* logN)。

最坏情况：如果待排序数组是有序的，仍然需要O(N \* logN)复杂度的比较操作，只是少了移动的操作；

最好情况：如果待排序数组是逆序的，不仅需要O(N \* logN)复杂度的比较操作，而且需要O(N \* logN)复杂度的交换操作。总的时间复杂度还是O(N \* logN)。

因此，堆排序和快速排序在效率上是差不多的，但是堆排序一般优于快速排序的重要一点是，数据的初始分布情况对堆排序的效率没有大的影响。

## 三、交换排序 ##

交换排序的基本方法是：两两比较待排序记录的排序码，交换不满足顺序要求的偶对，直到全部满足位置。常见的冒泡排序和快速排序就属于交换类排序。

**1.冒泡排序**  
算法思想：  
从数组中第一个数开始，依次遍历数组中的每一个数，通过相邻比较交换，每一轮循环下来找出剩余未排序数的中的最大数并”冒泡”至数列的顶端。

算法步骤：  
\- 从数组中第一个数开始，依次与下一个数比较并次交换比自己小的数，直到最后一个数。如果发生交换，则继续下面的步骤，如果未发生交换，则数组有序，排序结束，此时时间复杂度为O(n)；  
\- 每一轮”冒泡”结束后，最大的数将出现在乱序数列的最后一位。重复步骤（1）。

稳定性：稳定排序。  
时间复杂度： O(n)至，平均时间复杂度为。  
最好的情况：如果待排序数据序列为正序，则一趟冒泡就可完成排序，排序码的比较次数为n-1次，且没有移动，时间复杂度为O(n)。  
最坏的情况：如果待排序数据序列为逆序，则冒泡排序需要n-1次趟起泡，每趟进行n-i次排序码的比较和移动，即比较和移动次数均达到最大值：  
比较次数: 移动次数等于比较次数，因此最坏时间复杂度为O(n\*n)。

void bubbleSort(int array[],int len){
        //循环的次数为数组长度减一，剩下的一个数不需要排序
        for(int i=0;i<len-1;++i){
            bool noswap=true;
            //循环次数为待排序数第一位数冒泡至最高位的比较次数
            for(int j=0;j<len-i-1;++j){
                if(array[j]>array[j+1]){
                    array[j]=array[j]+array[j+1];
                    array[j+1]=array[j]-array[j+1];
                    array[j]=array[j]-array[j+1];
                    //交换或者使用如下方式
                    //a=a^b;
                    //b=b^a;
                    //a=a^b;
                    noswap=false;
                }
            }
            if(noswap) break;
        }
    }

**2、快速排序**  
冒泡排序是在相邻的两个记录进行比较和交换，每次交换只能上移或下移一个位置，导致总的比较与移动次数较多。快速排序又称分区交换排序，是对冒泡排序的改进，快速排序采用的思想是分治思想。。

算法原理：

*  从待排序的n个记录中任意选取一个记录（通常选取第一个记录）为分区标准;
 *  把所有小于该排序列的记录移动到左边，把所有大于该排序码的记录移动到右边，中间放所选记录，称之为第一趟排序；
 *  然后对前后两个子序列分别重复上述过程，直到所有记录都排好序。

稳定性：不稳定排序。  
时间复杂度： 至，平均时间复杂度为。  
最好的情况：是每趟排序结束后，每次划分使两个子文件的长度大致相等，时间复杂度为。  
最坏的情况：是待排序记录已经排好序，第一趟经过n-1次比较后第一个记录保持位置不变，并得到一个n-1个元素的子记录；第二趟经过n-2次比较，将第二个记录定位在原来的位置上，并得到一个包括n-2个记录的子文件。

//a：待排序数组，low：最低位的下标，high：最高位的下标
    void quickSort(int a[],int low, int high)
    {
        if(low>=high)
        {
            return;
        }
        int left=low;
        int right=high;
        int key=a[left];    /*用数组的第一个记录作为分区元素*/
        while(left!=right){
            while(left<right&&a[right]>=key)    /*从右向左扫描，找第一个码值小于key的记录，并交换到key*/
                --right;
            a[left]=a[right];
            while(left<right&&a[left]<=key)
                ++left;
            a[right]=a[left];    /*从左向右扫描，找第一个码值大于key的记录，并交换到右边*/
        }
        a[left]=key;    /*分区元素放到正确位置*/
        quickSort(a,low,left-1);
        quickSort(a,left+1,high);
    }

## 四、归并排序 ##

算法思想：  
归并排序属于比较类非线性时间排序，号称比较类排序中性能最佳者，在数据中应用中较广。

归并排序是分治法（Divide and Conquer）的一个典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。  
归并操作的工作原理如下：  
\- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列  
\- 设定两个指针，最初位置分别为两个已经排序序列的起始位置  
\- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 重复步骤3直到某一指针超出序列尾  
\- 将另一序列剩下的所有元素直接复制到合并序列尾

稳定性：稳定排序算法；  
时间复杂度: 最坏，最好和平均时间复杂度都是Θ(nlgn)。

如图所示，很容易理解：  
![这里写图片描述][70 9]

## 五、计数排序 ##

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法描述：

*  找出待排序的数组中最大和最小的元素；
 *  统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
 *  对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
 *  反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

## 总结 ##

1、当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。  
2、在比较类排序中，归并排序号称最快，其次是快速排序和堆排序，两者不相伯仲，但是有一点需要注意，数据初始排序状态对堆排序不会产生太大的影响，而快速排序却恰恰相反。  
3、快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；

[70]: /images/20220518/11d09b163f6f4b94b935bbc8ae8b1a48.png
[70 1]: /images/20220518/30be049105314ad68909d0a3fdf8ac2c.png
[70 2]: /images/20220518/3e1bf9d231124ef9b493f50057436e51.png
[70 3]: /images/20220518/25aaced3552d43a69d9788d43b6687e7.png
[70 4]: /images/20220518/5021751925974017bdde202ae7304b7c.png
[70 5]: /images/20220518/35977fa7781c47fa9ae82beae015b581.png
[70 6]: /images/20220518/c215cf4f0e654e2aacb71829d9d4cf77.png
[70 7]: /images/20220518/d344ec71058d4d63aec347d0220d980d.png
[70 8]: /images/20220518/f0891b9150e24bc9b0270f461adb4d4f.png
[70 9]: /images/20220518/dce352c996d447479a9cebfd614e97d2.png