数据结构之八大排序算法(C语言实现)

转x33g5p2x  于2021-10-07 转载在 其他  
字(15.7k)|赞(0)|评价(0)|浏览(1043)

排序的概念及其应用

排序的概念

排序的定义

数据结构必学的结构之一，在现实生活中应用多，所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

排序的稳定性

如果在序列中有两个数据元素 r[i] 和 r[j]，它们的关键字 k[i] == k[j]，且在排序之前，对象 r[i] 排在 r[j] 前面；如果在排序之后，对象 r[i] 仍在对象 r[j] 的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的

排序在现实生活中的应用

下图是中国网站排行榜：

我们打开淘宝，在首页搜索你想要买的东西，上面就会有按综合排序，按销量排序，按信用排序，按价格排序，如下图：

常见的排序算法

我们这里主要讲解八个排序算法：直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、计数排序、归并排序。

常见排序算法的实现

直接插入排序

直接插入排序：它的原理是，我们假设前n-1个数是有序的，我们将第n个数与前面的数进行比较，将它插入到合适的位置

直接插入排序与我们平时打扑克牌时是一样的，假设我们手里的牌是有序的，我们新拿到一张牌时，习惯插到适当的位置(后面比它大，前面比它小)，其实插入排序也就是这样的。具体看下面的动图演示，助于理解。

动图演示：

代码如下：

  1. //插入排序
  2. // 2 1 4 3 6
  3. //时间复杂度：O(N^2) 逆序
  4. //最好：O(N) 接近顺序有序
  5. void InsertSort(int*a,int n)
  6. {
  7.     for(int i=0;i<n-1;i++)
  8.     {
  9.         //单趟插入
  10.         int end=i;
  11.         int temp = a[end+1];//新的元素
  12.         while(end>=0)
  13.         {
  14.             if(temp<a[end])//新元素小于前面的数时
  15.             {
  16.                 a[end+1]=a[end];//end后移
  17.                 end--;//更新end，end>=0时继续比较
  18.             }
  19.             else
  20.             {
  21.                 break;
  22.             }
  23.         }
  24.         //循环结束有两种情况：1、end减为-1 放在end的后面一个位置
  25.         //2、temp>a[end] 放在end的后一个位置
  26.         a[end+1]=temp;
  27.      } 
  28. }

时间复杂度：O(n^2)，直接插入排序的最好情况是什么呢？最好情况是数据接近有序的时候，只需比较n-1次，即为O(N)

空间复杂度：O(1)

希尔排序

在直接插入排序中，我们发现它的时间复杂度为O(N^2)，最好情况为O(N)，但是此时是需要数据接近有序，这时一位我们的前辈希尔就提出了希尔排序的思想。

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
  • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。希尔排序实际上是直接插入排序的优化版本。

希尔的思路：

1、预排序(接近升序)

2、直接插入排序

那么怎么预排序呢？

比如我们有这样的一组序列：9 8 7 6 5 4 3 2 1 0

我们按照希尔的思路走，首先我们进行预排序：对间隔为gap，分成一组，分好组之后每组进行插入排序，假设gap=3

第一组：9 6 3 0 第二组：8 5 2 第三组：7 4 1

按分组，对这gap组数据插入排序：

最后我们再将预排序的结果进行一次直接插入排序，就变成了升序。

希尔排序的整体过程：

由上图可知一个数据一次挪动，不是走一步，而是走gap步，这样数据挪动更快，gap越小，越接近有序，gap越大，越不接近有序，但是gap越小挪动樾慢，gap越大挪动越快，gap==1时，其实就是直接插入排序

代码如下：

  1. void ShellSort(int* a,int n)
  2. {
  3.     //gap>1 预排序--接近有序
  4.     //gap==1 直接插入排序
  5.     int gap = n;
  6.     while(gap>1)//while循环的时间复杂度：log以3为底N的对数
  7.     {
  8.         gap=gap/3+1;//最后一次一定是1
  9.         //gap = gap/2;//预排会多一些
  10.         
  11.         //间隔为gap的多组并排
  12.         for(int i=0;i<n-gap;i++)//同时走这个gap组数据的间隔为gap插入排序
  13.         {//对于时间复杂度，我们考虑边界的情况：如果gap很大时，基本无序，挪动数据快，for循环里面的代 码几乎可以忽略不记 O(N)
  14.          //gap很小时，接近有序，gap是1时，看起来是O(N^2)，但是这里gap是1时，接近有序，故为O(N)
  15.             int end = i;
  16.             int temp=a[end+gap];//保存后一个数
  17.             while(end>=0)
  18.             {
  19.                 if(temp<a[end])
  20.                 {
  21.                     a[end+gap]=a[end];
  22.                     end-=gap;
  23.                 }
  24.                 else
  25.                 {
  26.                     break;
  27.                 }
  29.             }
  30.             //出来要么end=-gap，要么a[end]<temp(前一个数小于后一个数)
  31.             a[end+gap]=temp;//当end=-gap时要把temp赋给第一个元素位置，是另一种情况时，将 temp(较大者)赋给后一个数也是没问题的
  32.         }
  33.     }
  34. }

时间复杂度：

*while循环的时间复杂度：log以3为底N的对数，对于while循环里面的for循环的时间复杂度，我们考虑边界的情况：如果gap很大时，基本无序，挪动数据快，for循环里面的代码几乎可以忽略不记 O(N)，当gap很小时，接近有序，gap是1时，看起来是O(N^2)，但是这里gap是1时，接近有序，故为O(N)，故时间复杂度为O(N/log以3为底N的对数)，官方给的时间复杂度为O(N^1.3)。

空间复杂度：

O(1)

选择排序

第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。 以此类推，直到全部待排序的数据元素的个数为零。

动图演示：

代码如下：

  1. void Swap(int *p1,int *p2)
  2. {
  3.     int temp=*p1;
  4.     *p1=*p2;
  5.     *p2=temp;
  6. }
  7. void SelectSort(int *a,int n)
  8. {
  9.     int i=0;
  10.     int j=0;
  11.     for(j=0;j<n-1;j++)
  12.     {
  13.         //单趟
  14.         int min=j;//每趟先将第一个假定为最小的
  15.         for(i=j;i<n;i++)
  16.     	{
  17.             if(a[i]<a[min])
  18.             {
  19.                 min=i;//更新min
  20.             }
  21.     	}
  22.         Swap(&a[j],&a[min]);//交换
  23.     }  
  24. }

这时一次选出一个最大的或者最小的，时间复杂度为O(N^2)，那么可不可以优化一下呢？答案是可以的。

选择排序的优化版本：

我们可以定义一个begin变量，一个end变量，用来记录数据首和尾的下标，我们一个可以找出两个值，一个最大值，一个最小值，最小值放在a[begin]中，最大值放在a[end]中，这样我们就比上面的快多了

  1. //时间复杂度O(N^2)
  2. //直接选择排序
  3. void Swap(int *p1,int *p2)
  4. {
  5.     int temp=*p1;
  6.     *p1=*p2;
  7.     *p2=temp;
  8. }
  9. void SelectSort(int *a,int n)
  10. {
  11.     int begin = 0;
  12.     int end = n-1;
  13.     while(begin<end)
  14.     {
  15.         int mini=begin;
  16.         int maxi=end;
  17.         int i=0;
  18.         for(i=begin;i<=end;i++)
  19.         {
  20.             //选出[begin,end]中最大和最小的
  21.             if(a[i]<a[mini])
  22.             {
  23.                 mini=i;
  24.             }
  25.             if(a[i]>a[maxi])
  26.             {
  27.                 maxi=i;
  28.             }
  29.         }
  30.         Swap(&a[begin],&a[mini]);
  31.         //这里需要考虑第一个值放最大值的情况，如果第一个值为最大值,此时最大值位置被移动
  32.         if(begin==maxi)
  33.         {
  34.             maxi=mini;//最大的值被换到了mini的位置，更新最大值的位置
  35.         }
  36.         Swap(&a[end]，&a[maxi]);
  37.         begin++;
  38.         end--;
  39.     }
  40. }

时间复杂度：O(n^2)
空间复杂度：O(1)

堆排序

堆排序分两个步骤：

1、建堆

2、排序

那么我们排升序建大堆还是建小堆呢？答案是建大堆。

升序为什么不能建小堆呢？
建堆选出最小的数，花了O(N)的时间复杂度，紧接着如何选次小的数呢？剩下的数父子关系全乱了，向下调整需要满足左右子树都是堆，但是关系都乱了，左右子树可能都不满足向下调整的条件了，故剩下的N-1个数只能重新建堆，效率太低了

升序建大堆

1、选出了最大的数，把最大的数与最后的数交换

2、紧接着选出次大的数，与倒数第二个位置的数交换…

因为堆结构没有破坏，最后一个数不看作堆里面，左右子树依旧是大堆，向下调整即可，选出第二大

建大堆完成后，排序的步骤如图：

堆排序代码如下：

  1. #include<stdio.h>
  2. void swap(int *p1,int *p2)
  3. {
  4.     int temp=*p1;
  5.     *p1=*p2;
  6.     *p2=temp;
  7. }
  8. //左右子树都是小堆或者大堆
  9. void AdjustDown(int *a,int n,int parent)
  10. {
  11.    	int child=parent*2+1; //左孩子，左孩子+1即为右孩子
  12.     while(child<n)
  13.     {
  14.         //选择出左右孩子中较小/大的那个
  15.         //小堆
  16.         if(child+1<n && a[child+1]>a[child])//右孩子存在(防止越界)且如果右孩子比左孩子小
  17.         {
  18.             child++;//那就下标来到右孩子
  19.         }
  20.         
  21.         if(a[child]<a[parent])//大的孩子大于父亲就交换，继续调整
  22.         {
  23.             swap(&a[parent],&a[child]);
  24.             parent=child;
  25.             child=parent*2+1;
  26.         }
  27.         else//大的孩子比父亲小或相等，则不处理，调整结束
  28.         {
  29.             break;
  30.         }
  31.     }
  32. }
  33. //排序(升序)，排升序要建大堆，排降序要建小堆
  34. void HeapSort(int *a,int n)
  35. {
  36.     //1、建堆
  37.     int i=0;
  38.     //为了满足向下调整条件，从最后一个非叶子结点开始调整，从下往上调整
  39.     for(i=(n-1-1)/2;i>=0;--i)//最后一个结点的父亲是最后一个非叶子结点
  40.     {
  41.         AdjustDown(a,n,i);//O(N)
  42.     }
  43.     //2、排序
  44.     int end=n-1;
  45.     while(end>0)
  46.     {
  47.         swap(&a[0],&a[end]);
  48.         AdjustDown(a,end,0);//O(nlogn)，一次向下调整为层数次 即logn次，while循环一共调整n次，故是nlogn
  49.         end--;
  50.     }
  51. }

*堆排序时间复杂度O(N/logN)，一次向下调整为层数次 即logn次，while循环一共调整n次，故是nlogn

堆排序空间复杂度O(1)

冒泡排序

算法思想：从左到右，相邻元素进行比较。每次比较一轮，就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。以从小到大排序为例，第一轮比较后，所有数中最大的那个数就会浮到最右边；第二轮比较后，所有数中第二大的那个数就会浮到倒数第二个位置……就这样一轮一轮地比较，最后实现从小到大排序。

冒泡排序动图演示：

  1. void BubbleSort(int* a,int n)
  2. {
  3.     int i=0;
  4.     int j=0;
  5.     for(i=0;i<n-1;i++)
  6.     {
  7.         for(j=0;j<n-1-i;j++)
  8.         {
  9.             if(a[j]>a[j+1])
  10.             {
  11.                 Swap(&a[j],&a[j+1]);
  12.             }
  13.         }
  14.     }
  15. }

时间复杂度：O(N^2)

空间复杂度：O(1)

冒泡排序的优化

冒泡排序有时候在我们已经有序的情况下，内部的循环还是会进去，这样影响了效率，故我们设置一个flag，当有一趟没有发生交换时，flag没有发生变化，此时就是有序了，此时直接结束循环。

  1. void BubbleSort(int* a,int n)
  2. {
  3.     int i=0;
  4.     int j=0;
  5.     for(i=0;i<n-1;i++)
  6.     {
  7.         int flag = 0;
  8.         for(j=0;j<n-1-i;j++)
  9.         {
  10.             if(a[j]>a[j+1])
  11.             {
  12.                 Swap(&a[j],&a[j+1]);
  13.                 flag=1;
  14.             }
  15.         }
  16.         if(flag==0)
  17.         {
  18.             break;
  19.         }
  20.     }
  21. }

时间复杂度最好O(N)，最坏O(N^2)

空间复杂度O(1)

快速排序

快速排序是我们这里的高手，高手要登场了，快速排序其实就是冒泡排序的升级，它们都属于交换排序类，它也是通过不断比较和移动来实现排序的，只不过它的实现，增大了记录的比较和移动的距离，较大的记录从前面直接移动到后面，较小的记录从后面直接移动到前面，减少了比较次数和移动次数。

Hoare法

Hoare法快速排序的思想
我们有一组待排序的数据，在其中选一个关键字key出来，一般是选头或者尾

快速排序的单趟：key放到它正确的位置上(整体排完序后最终放的位置)，key的左边的值比key小，key右边值比它大

单趟排完，再想办法让key左边区间有序，key的右边区间有序，整体就有序了

Hoare法快速排序单趟动图演示：

Hoare法快排单趟代码：

  1. //单趟
  2. int PartSort(int *a,int begin,int end)
  3. {
  4.     int keyi=begin;//选定一个关键字的下标
  5.     while(begin<end)
  6.     {
  7.         //右边先走 右边先找比keyi小的
  8.         while(begin<end && a[end]>a[keyi])
  9.         {
  10.             end--;
  11.         }
  12.         //此时end是比keyi小的那个数的下标
  13.         
  14.         //左边找比keyi大的
  15.         while(begin<end && a[begin]<a[keyi])
  16.         {
  17.             begin++;
  18.         }
  19.         //此时begin是比keyi大的那个数的下标
  20.         Swap(&a[begin],&a[end]);//交换
  21.         //这里的目的是让左边是比关键字小的，右边是比关键字大的
  22.     }
  23.     //此时begin和end相遇了
  24.     Swap(&a[begin],&a[keyi]);//交换相遇的地方和关键字的位置
  25.     return begin;//返回关键字的位置
  26. }

有的人可能会迷惑，万一相遇点比关键字大呢？

我们假设关键字是头，那么是如何保证begin和end相遇的那个位置的数一定比关键字小呢？

当关键字是头时，我们让end先走，这其实就保证了那个位置的数一定比关键字小，为什么呢？

因为相遇有两种情况：begin遇end；end遇begin

  • 当begin遇end情况下
    end先走，end停在了比关键字小的位置上，如果(begin<end是前提)此时begin后面的都比关键字小，那么begin就来到了end的位置停止了，而end就在比关键字小的位置上

  • 当end遇begin情况下
    end先走，end停在了比关键字小的位置上，begin再走，begin停在了比关键字大的位置上，将begin和end处的值交换(注意这个交换很重要)，end再走，假设((begin<end是前提)end前面的都比关键字小，那么end来到了begin的位置就停止了，此时相遇，此时相遇点处的值比关键字小了，为什么呢？因为前面begin处的值与end处的值发生了交换，而end处的值是小于关键字的。

综上所述，相遇的位置处的值一定比关键字小

同理，关键字是尾时，我们让左边先走，那么就会保证相遇的位置处的值一定比关键字大

单趟的时间复杂度是多少呢？最坏情况比较N次，故时间复杂度为O(N)

那么单趟排完，怎么让整体有序呢？再想办法让key左边区间有序，key的右边区间有序，整体就有序了，那么怎么让左边区间有序，右边区间有序呢？

这是不是又是一个子问题了呢？故可以用递归解决

快速排序代码：

  1. //单趟
  2. int PartSort(int *a,int begin,int end)
  3. {
  4.     int keyi=begin;//选定一个关键字的下标
  5.     while(begin<end)
  6.     {
  7.         //右边先走 右边先找比keyi小的
  8.         while(begin<end && a[end]>a[keyi])
  9.         {
  10.             end--;
  11.         }
  12.         //此时end是比keyi小的那个数的下标
  13.         
  14.         //左边找比keyi大的
  15.         while(begin<end && a[begin]<a[keyi])
  16.         {
  17.             begin++;
  18.         }
  19.         //此时begin是比keyi大的那个数的下标
  20.         Swap(&a[begin],&a[end]);//交换
  21.         //这里的目的是让左边是比关键字小的，右边是比关键字大的
  22.     }
  23.     //此时begin和end相遇了
  24.     Swap(&a[begin],&a[keyi]);//交换相遇的地方和关键字的位置
  25.     return begin;//返回关键字的位置
  26. }
  27. //快速排序
  28. void QuickSort(int *a,int begin,int end)
  29. {
  30.     if(begin>=end)//如果区间不存在
  31.     {
  32.         return;
  33.     }
  34.     int keyi = PartSort(a,begin,end);
  35.     QuickSort(a,begin,keyi-1);
  36.     QuickSort(a,keyi+1,end);
  37. }

这样就完成了快速排序，但是时间复杂度是多少呢？

快速排序时间复杂度

*理想情况下(单趟后关键字处于中间)，递归深度为层数次，即log(N)，每一层的递归时间复杂度加起来都是N，故理想情况下时间复杂度为N/logN

但是在有序的情况下，时间复杂度为O(N^2)：

那么有没有什么优化的方法呢？答案是有的

快速排序的优化

优化方法：

  • 随机选key
  • 三数取中选key

这里我们讲解第二种：三数取中。

我们取下标为begin，mid，end的数当中大小处于中间的作为key，这样就解决了上面的最坏的情况

三数取中优化快排代码：

  1. int GetMidIndex(int* a, int begin, int end)
  2. {
  3.     int mid = (begin + end) / 2;
  4.     if (a[begin] < a[mid])
  5.     {
  6.         if (a[mid] < a[end])
  7.         {
  8.             return mid;
  9.         }
  10.         else if (a[begin] < a[end])
  11.         {
  12.             return end;
  13.         }
  14.         else
  15.         {
  16.             return begin;
  17.         }
  18.     }
  19.     else
  20.     {
  21.         if (a[mid] > a[end])
  22.         {
  23.             return mid;
  24.         }
  25.         else if (a[begin] < a[end])
  26.         {
  27.             return begin;
  28.         }
  29.         else
  30.         {
  31.             return end;
  32.         }
  33.     }
  34. }
  35. //时间复杂度O(N)
  36. int PartSort(int* a,int begin,int end)
  37. {
  38.     int midi=GetMidIndex(a,begin,end);//三数取中
  39.    	Swap(&a[midi],&a[begin]);
  40.     int keyi=begin;
  41.     while(begin<end)
  42.     {
  43.         //左边做key，让右边先走找比key小的值
  44.         while(begin<end && a[end]>=a[keyi])
  45.         {
  46.             end--;
  47.         }
  48.         //左边走，找大
  49.         while(begin<end && a[begin]<=a[keyi])
  50.         {
  51.             begin++;
  52.         }
  53.         //交换，把大的换到右边，小的换到左边
  54.         Swap(&a[begin],&a[end]);
  55.     }
  56.     //相遇
  57.     Swap(&a[begin],&a[keyi]);
  58.     return begin;
  59. }
  60. //O(N*logN) 理想情况，递归深度为层数次，即log(N)，每次加起来都是N，故为N*logN
  61. //最坏情况为：O(N^2) 在有序的情况--针对有序的情况
  62. //优化方法
  63. //1、随机选key
  64. //2、三数取中选key begin mid end中不是最大也不是最小
  65. //优化后没有了最坏情况
  67. void QuickSort(int *a,int begin,int end)
  68. {
  69.     //单趟 
  70.     if(begin>=end)
  71.     {
  72.         return;
  73.     }
  74. 	int keyi = PartSort(a,begin,end);
  75.     QuickSort(a,begin,keyi-1);
  76.     QuickSort(a,keyi+1,end);
  77.     
  78. }

*没有了最坏情况，这就是最优了，优化后时间复杂度为O(N/logN)

Hoare法比较容易出错，下面我们介绍下一种方法：挖坑法

挖坑法

挖坑法单趟的思想：
将最左边(右边也可以)的值用key变量保存起来，此时最左边(右边)形成一个坑位，然后end开始走(如果最右边找的key，那么begin先走)，end找比关键字小的，找到后将坑位填充，然后坑位变为end，然后begin开始走，begin找比关键字大的，找到后将坑位填充，然后坑位变为begin，直到begin和end相遇，此时begin和end都是坑位，将之前保存的关键字的值填到坑里面

挖坑法单趟动图演示：

挖坑法代码如下：

  1. int PartSort2(int* a, int begin, int end)
  2. {
  3.     int hole = begin;
  4.    	int key=a[begin];
  5.     while(begin<end)
  6.     {
  7.         //让右边先走找比key小的值，填到坑里
  8.         while(begin<end && a[end]>=key)
  9.         {
  10.             end--;
  11.         }
  12.         //填到坑
  13.         a[hole]=a[end];
  14.         //更新坑
  15.         hole=end;
  16.         //左边走，找比key大的值，填到坑
  17.         while(begin<end && a[begin]<=key)
  18.         {
  19.             begin++;
  20.         }
  21.         //填到坑
  22.         a[hole]=a[left];
  23.         //更新坑
  24.         hole=begin;
  25.     }
  26.     //相遇
  27.     a[hole]=key;
  28.     return hole;
  29. }
前后指针法

前后指针法核心思想：

  1. cur往前走，找比key小的数据
  2. 找到比key小的数据以后，停下来，prev++
  3. 交换prev和cur指向位置的值
  4. 直到cur走到数组的结尾，将key与prev交换

关于key的选取，选取左边和右边都可以，这里以选取左边为例讲解，注意选取右边时，起始位置和选取左边时不一样，下图为选取右边做key时，cur需指向左边第一个位置：

前后指针法动图演示：

cur还没遇到比key大的值前，prev紧跟着cur，cur遇到比key大的值后，prev和cur之间间隔了一段比key大的数据，所以当cur找到小于关键字的值时，prev++，将cur和prev交换，实际上就是将小于关键字的值换到左边，大于关键字的值换到了右边

前后指针法代码如下：

  1. void PartSort3(int *a,int begin,int end)
  2. {
  3.     int keyi = begin;
  4.     int prev = begin;
  5.     int cur = prev+1;
  6.     while(cur<=end)
  7.     {
  8.         if(a[cur]>a[keyi])
  9.         {
  10.             prev++;
  11.             Swap(&a[cur],&a[prev]);
  12.         }
  13.         cur++;//无论啥情况cur都需要++
  14.     }
  15.     //此时cur已经等于end已结束，需要将prev和keyi进行交换
  16.     Swap(&a[prev],&a[keyi]);
  17.     return prev;
  18. }

这段代码可以适当优化一下，当cur找到小于关键字的数时，prev++，此时如果cur==prev时，是不需要交换的，所以我们可以这样写：

  1. void PartSort3(int *a,int begin,int end)
  2. {
  3.     int keyi = begin;
  4.     int prev = begin;
  5.     int cur = prev+1;
  6.     while(cur<=end)
  7.     {
  8.         if(a[cur]>a[keyi] && ++prev!=cur)
  9.         {
  10.             Swap(&a[cur],&a[prev]);
  11.         }
  12.         cur++;//无论啥情况cur都需要++
  13.     }
  14.     //此时cur已经等于end已结束，需要将prev和keyi进行交换
  15.     Swap(&a[prev],&a[keyi]);
  16.     return prev;
  17. }

第二种写法：

  1. void PartSort3(int *a,int begin,int end)
  2. {
  3.     int keyi=begin;
  4.     int prev=begin;
  5.     int cur= prev+1;
  6.     while(cur<=right)
  7.     {
  8.         while(cur<=right && a[cur]>a[keyi])
  9.         {
  10.             cur++;//cur找小
  11.         }
  12.         //此时cur指向小的
  13.         if(cur<=right)
  14.         {
  15.             prev++;
  16.             Swap(&a[prev],&a[cur]);//交换 
  17.         }
  18.     }
  19.     Swap(&a[keyi],&a[prev]);
  20. }

对于上面的三种快速排序方法，我们都是利用递归解决的，当然递归有时也是会有缺陷的：

递归程序，相对循环迭代程序的问题：

  • 递归的深度太深，会导致栈溢出
  • 性能问题(现在编译优化很好，性能问题已经不是很影响了)

任何一个递归程序，把它改成非递归有两种方式：

循环
*
栈+循环

下面我们就来学习一下快速排序的非递归写法：

快速排序非递归

非递归思路：
我们借用数据结构栈来实现快速排序的非递归算法：依次把需要单趟排的区间入栈，依次取栈里面的区间出来单趟排，再把需要处理的子区间入栈

代码如下：

  1. void QuickSortNonR(int *a,int n)
  2. {
  3.     ST st;
  4.     StackInit(&st);
  5.     StackPush(&st,end);
  6.     StackPush(&st,begin);
  7.     while(!StackEmpty(&st))
  8.     {
  9.         int left = StackTop(&st);	
  10.         StackPop(&st);
  11.         
  12.         int right = StackTop(&st);
  13.         StackPop(&st);
  14.         
  15.         int keyi = PartSort1(a,left,right);
  16.         //[left,keyi-1] keyi [keyi+1,right]
  17.         if(keyi+1<right)//如果存在右序列(右序列需要大于1)
  18.         {
  19.             StackPush(&st,right);
  20.             StackPush(&st,keyi+1);
  21.         }
  22.         if(keyi-1>left)//如果存在左序列(左序列需要大于1)
  23.         {
  24.             StackPush(&st,keyi-1);
  25.             StackPush(&st,left);
  26.         }
  27.     }
  28.     StackDestory(&st);
  29. }

归并排序

在讲归并排序之前，我们首先举个例子：

  • 本人在大话数据结构这本书上看到的这个例子，感觉举得很形象，就在这里说一下，如果各高校本科专业在某个省招生1万名，那么将全省参加高考的人的分数倒排序，第一万名的总分就是当年本科生的分数线。也就是说，即使你是你们班级的班级第一、甚至是年级第一，如果你没有超过本科的分数线，你就基本失去了上本科的机会了，所谓的全省排名，其实就是每个市、每个县、每个学校、每个班级的排名合并后再排名得到的。我们要比较两个学生的成绩高低是很容易的，比如甲比乙分数低，丙比丁分数低。那么我们也就可以很容易得到甲乙丙丁合并后的成绩排名，同样的，戊己庚辛的排名也容易得到，由于他们两组有序了，把他们八个学生成绩合并有序也是很容易做到的，继续下去……最终完成全省学生的成绩排名，此时就有高考状元了。
    归并，在数据结构中的意思就是将两个或两个以上的有序表组合成一个新的有序表。归并排序就是利用归并的思想实现的排序方法，它的原理是假设初始序列有n个数据，则可以看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，……这样一直重复，直到得到一个长度为n的有序序列为止。

下图是两组有序的序列进行合并的图解步骤：

归并需要两个子序列的序列有序，那么我们是如何将子序列变成有序的呢？下图为一组序列的分解和归并过程，将一个问题分成子问题去解决：

当分解成都只有一个数的序列时，这时可以将他们看成有序，就可以开始合并了

归并排序动图演示：

代码如下：

首先我们需要开辟一个临时数组来存放归并后的数据，我们还需要重新创建一个函数进行递归，不重新创建的话，每次递归都会创建一个临时数组，这是不合理的，所以我们需要重新创建一个函数，代码如下：

  1. void _MergeSort(int*a,int left,int right,int*temp)
  2. {
  3.     if(left>=right)
  4.         return;//当区间不存在或者只有一个值时，返回
  5.     int mid = (right+left)/2;//mid用来分组，分成[left,mid],[mid+1,right]
  6.     //[left,mid],[mid+1,right]
  7.     _MergeSort(a,left,mid,temp);//递归左边
  8.     _MergeSort(a,mid+1,right,temp);//递归右边
  9.     //归并
  10.     int begin1 = left,end1 = mid;//避免混淆，这里用begin1，end1，begin2，end2来保存 区间
  11.     int begin2 = mid+1,end2 = right;
  12.     int index = left;
  13.     while(begin1<=end1 && begin2<=end2)//两组中的数据有一个结束就结束
  14.     {
  15.         if(a[begin1]<a[begin2])
  16.         {
  17.             temp[index++]=a[begin1++];//将数据拷进去，并++指向下一个位置
  18.         }
  19.         else
  20.         {
  21.             temp[index++]=a[begin2++];//将数据拷进去，并++指向下一个位置
  22.         }
  23.     }
  24.     //出来后有一组数据还没有拷贝进去，如果左边的没结束，则将左边剩下的拷贝进去，右边没结束，则将右边剩下的拷贝进去
  25.     while(begin1<=end1)
  26.     {
  27.     	temp[index++]=a[begin1++];//将剩下的数据全部拷贝进去 
  28.     }
  29.     while(begin2<=end2)
  30.     {
  31.     	temp[index++]=a[begin2++];//将剩下的数据全部拷贝进去 
  32.     }
  33.     for(int i=left,i<=right;i++)
  34.     {
  35.         a[i]=temp[i];//最后还需要将temp中的数据拷贝到原数组
  36.     }
  37.     
  38. }
  39. void MergeSort(int* a,int n)
  40. {
  41.     int *temp =(int*)malloc(sizeof(int)*n);//开辟一个临时数组来存放归并后的数据
  42.     _MergeSort(a,0,n-1,temp);
  43.     
  44.     free(temp);
  45. }

*时间复杂度：O(n/logn)
空间复杂度：O(n)

归并排序非递归实现

归并的非递归是和斐波那契数列是有一些相似的，Fib(N)=Fib(N-1)+Fib(N-2)，斐波那契数列的非递归就是顺着走，依次求后面的斐波那契数，而归并的非递归也是十分相似的，也是顺着走

顺着走：首先一个和一个归并，再两个和两个归并……

我们需要控制每组的个数：groupNum=1，2，4，其次我们还需要控制每组的区间，控制好区间，我们还需要防止越界的情况，归并的非递归的实现麻烦就麻烦在这里，例如：

而我们的归并的个数不一定每次都是成对出现的，所以我们需要考虑几种越界情况：

  • 情况一：begin2越界

怎么解决呢？
我们需要给定第二个区间一个不存在的区间，为什么呢？begin2不存在时，不能让它进去归并了，因为会越界，之后的代码会将[begin1，end1]区间的数拷贝进temp数组

  • 情况二：end1越界

此时只需要将end1调整，end1=n-1

  • 情况三：end2越界

此时只需要将end1调整，end1=n-1

  1. void MergeSortNonR(int* a, int n)
  2. {
  3.     int* temp = (int*)malloc(sizeof(int) * n);//开辟一个临时数组
  4.     if (temp == NULL)
  5.     {
  6.         return;
  7.     }
  8.     int groupNum = 1;
  9.     while (groupNum < n)
  10.     {
  11.         for (int i = 0; i < n; i += 2 * groupNum)
  12.         {
  13.             //[begin1][end1] [begin2,end2]
  14.             //控制组进行归并
  15.             int begin1 = i, end1 = i + groupNum - 1;
  16.             int begin2 = i + groupNum, end2 = i + groupNum * 2 - 1;
  17.             int index = begin1;
  19.             //数组的数据个数，并不一定是按整数倍
  20.             //1、[begin2,end2]不存在，修正为一个不存在的区间
  21.             //让它进不去归并
  22.             if (begin2 >= n)//
  23.             {
  24.                 begin2 = n + 1;
  25.                 end2 = n;
  26.             }
  27.             if (end1 >= n)//end1越界，修正一下
  28.             {
  29.                 end1 = n - 1;
  30.             }
  31.             if (end2 >= n)//end2越界，需要修正后归并
  32.             {
  33.                 end2 = n - 1;
  34.             }
  35.             while (begin1 <= end1 && begin2 <= end2)//两组中的数据有一个结束就结束
  36.             {
  37.                 if (a[begin1] < a[begin2])
  38.                 {
  39.                     temp[index++] = a[begin1++];//将数据拷进去，并++指向下一个位置
  40.                 }
  41.                 else
  42.                 {
  43.                     temp[index++] = a[begin2++];//将数据拷进去，并++指向下一个位置
  44.                 }
  45.             }
  46.             //出来后有一组数据还没有拷贝进去，如果左边的没结束，则将左边剩下的拷贝进去，右边没结束，则将右边剩下的拷贝进去
  47.             while (begin1 <= end1)
  48.             {
  49.                 temp[index++] = a[begin1++];//将剩下的数据全部拷贝进去 
  50.             }
  51.             while (begin2 <= end2)
  52.             {
  53.                 temp[index++] = a[begin2++];//将剩下的数据全部拷贝进去 
  54.             }
  56.         }
  57.         //拷贝回原数组
  58.         for (int i = 0; i < n; i++)
  59.         {
  60.             a[i] = temp[i];//最后还需要将temp中的数据拷贝到原数组
  61.         }
  62.         groupNum *= 2;
  63.     }
  64.     free(temp);
  65. }

下面我们来看计数排序：

计数排序

算法思想：

先统计原数组中每个值出现的次数，存放在count数组
*
排序，遍历count数组，对应位置的值出现几次，就往原数组中写几个这个值
count数组不应该按[0,max]去开辟，否则会很浪费空间，应该用[min,max]，会节省空间

计数排序动图演示：

代码如下：

  1. //计数排序
  2. void CountSort(int*a,int n)
  3. {
  4.     int min=a[0],max=a[0];
  5.     //找最大值，最小值
  6.     for(int i=1;i<n;i++)
  7.     {
  8.         if(a[i]<min)
  9.         {
  10.             min=[i];
  11.         }
  12.         if(a[i]>max)
  13.         {
  14.             max=a[i];
  15.         }
  16.     }
  17.     int range = max-min+1;//区间范围个数，用于开辟count数组
  18.     int* count = (int*)calloc(range,sizeof(int));//开辟一个数组用来存放次数
  19.     
  20.     //统计次数
  21.     for(int i=0;i<n;i++)
  22.     {
  23.         count[a[i]-min]++;//对相对位置进行计数
  24.     }
  25.     //遍历计数数组，对原数组进行排序
  26.     int i=0;
  27.     for(int j=0;j<range;j++)
  28.     {
  29.         while(count[j]--)
  30.         {
  31.             a[i++]=j+min;
  32.         }
  33.     }
  34. }

时间复杂度：O(Max(range,N))
空间复杂度：O(range)

什么情况适合计数排序呢？

当数据比较密集时，计数排序是一个很有效的算法

常见排序算法的性能总结

常见排序算法的时间复杂度、空间复杂度、稳定性

排序方法平均情况最好情况最坏情况辅助空间稳定性
直接插入排序O(n^2)O(n)O(n^2)O(1)稳定
希尔排序O(nlogn)~O(n^2)O(n^1.3)O(n^2)O(1)不稳定
简单选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定
堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定
冒泡排序O(n^2)O(n)O(n^2)O(1)稳定
快速排序O(nlogn)O(nlogn)O(n^2)O(logn)~O(n)不稳定
归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定

效率划分：

O(N^2)
直接插入排序、选择排序、冒泡排序

*O(N/logN)

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

O(N^1.3)

希尔排序

各类排序算法的稳定性分析

稳定性的概念我们已经在前面提过，排序的序列中有多个相同的数，排完序以后可以保证相对顺序不变的就是稳定的，不能保证相对顺序的就是不稳定的

插入排序稳定性

插入排序是稳定的，在插入排序中，我们假设前面的序列是有序的，当前数字如果小于前面的数，就将前面的数字往后挪，如果大于前面的数字就不挪了，就放在它后面，如果等于前面的数字我们也是放在它的后面，故插入排序是稳定的。

希尔排序稳定性

希尔排序是不稳定的，因为希尔排序我们是需要分组进行插入排序，如果这个相同的数在相同的组里面我们可以保证它的相对顺序，但是不是一个组时，我们就无法保证他们的相对顺序了，故希尔排序是不稳定的

例如：

选择排序稳定性

*选择排序是不稳定的，比如5，1，2，1/，从小到大排序，5最大，会和队尾元素交换，变为1/，1，2，5。1和1/的相对位置发生了变化，故它是不稳定的

堆排序稳定性

堆排序是不稳定的，比如在建好一个大堆：

**

**

冒泡排序稳定性

冒泡排序是稳定的，在冒泡的过程中，我们前面的数比后面的大时才交换，不大的就不会交换，故它的相对顺序是不会改变的。

快速排序稳定性

快速排序是不稳定的，为什么呢？ 如果我们选择了一组序列的最左边的数字5作为key，假设右边还有两个5，一个5在小于key的区域，一个5大于key的区域，而最后需要将最左边的key与相遇点交换，此时相对位置发生了改变，故快排是不稳定的。

例如：

归并排序稳定性

归并是稳定的，为什么呢？

**

**

稳定性的意义

在数据结构中我们只是对一个简单元素进行排序，但是在现实生活中我们不可能只是对一个简单元素排序，我们排序的对象可能是结构体，比如在高考中，学生就是一个结构体，结构体成员变量有name、score、num、以及各科的成绩，我们要对高考生进行一个排名，我们希望按照总分去排名，而对于总分相同的同学，我们希望按照语文成绩由高到低排名，要满足这样的需求，我们就需要保证排序算法的稳定性，这样我们就可以先按照语文成绩对学生排名，再利用排序算法的稳定性，对总分进行排序，这样我们就可以保证分数相同的情况下，语文成绩高的在前面

再举一个例子：考试的时候，提交试卷以后，自动判卷拿到成绩，成绩按交卷顺序填到数组中，然后我们对数组排序，进行排名

要求：分数相同，先交卷的排在前面

利用稳定的排序的话，红色的一定是排在蓝色的前面的。

排序的常见算法就讲解到这里，觉得文章对你有帮助的话，建议点赞+收藏哦

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/attemptendeavor/article/details/120400245

内容来源于网络，如有侵权，请联系作者删除！

数据结构c语言算法八大排序

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com