快速排序、归并排序、计数排序

---

---

前言

本文介绍这三种非常强大的排序算法，每种算法都有各自的特点、不同的实现方式和优化。其算法在效率和数据处理等等方面都非常的强大。

---

一、归并排序

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。它是将已经有序的子序列合并，得到完全有序的序列。

算法逻辑

归并排序的算法逻辑其实是很直接的，就是将待排序列不断的二分，二分至只有一个元素的子序列（视为有序），然后使有序的子序列之间有序，不断的把有序的子序列合并为有序的更大子序列，直至整个子序列有序，这就是归并的操作，像这样将两个有序序列合并为一个有序序列，称为二路归并。
归并排序的重点在于需要先二分，然后再归并，而二分之中，需要考虑序列的长度，同时如何先从二分至只剩一个元素的最小序列入手，这里我想我们应该能想到用递归去实现，当然，也有非递归的方法，只不过会用到更复杂一些的思路，并不是那么好想出来的。而归并的操作中，我们将有序序列合并，为了提高效率，可以用空间换时间，用一个新的空间接受子序列里的有效值，然后使得该空间内数据都是有序的，这样能够提高效率。
这里有一张图，可以让大家更直观的了解其原理：

递归实现

递归是最好想的方法，这里我们直接上代码：

void _Mergesort(int* arr,int left,int right,int* tem)//参数分别是两个数组，以及子序列的左右边界
{if(left>=right)//递归的终止条件，二分划分到最小子序列{return;}int mid = (left + right)/2;//找到中间值，完成二分_Mergesort(arr,left,mid,tem);//开始递归_Mergesort(arr,mid+1,right,tem);int begin1 = left,end1 = mid;//合并两个有序序列int begin2 = mid + 1,end2 = right;int index = begin1;while(begin1 <= end1 && begin2 <= end2)//将两个有序序列合并之后，放到对应区间使有序{if(arr[begin1] < arr[begin2])tem[index++] = arr[begin1++];elsetem[index++] = arr[begin2++];}while(begin1 <= end1){tem[index++] = arr[begin1++];}while(begin2 <= end2){tem[index++] = arr[begin2++];}for(int i = left;i < right;i++)//将有序的序列导入到原数组里去{arr[i] = tem[i];}
}void Mergesort(int* arr,int n)
{int* tem = (int*)malloc(sizeof(int)*n)//开辟一个新空间，用于接收有序的合并序列_Mergesort(arr,0,n-1,tem);再用一个函数，方便完成递归free(tem);//释放动态开辟的空间tem = NULL;
}

• 时间复杂度分析
  归并排序算法里出现了递归，我们首先来计算一下单次递归的时间复杂度，由于归并排序是将数组不断地二分，单次递归会对每一个子序列排序，单次的时间复杂度为O(N)，而对于整个递归，我们要log2N次，转化为时间复杂度就是logN，所以整体的时间复杂度就是O(N*logN)。这也是一个相当强大的排序，当然，它的空间复杂度为O(N)，这是它效率的代价，要消耗一模一样大的空间来辅助排序。

非递归实现

对于归并的二路划分，递归是一个非常好想的思路，而对于非递归的版本，我们一样是有方法的，只是这个思路比较难想到，也比较的妙。下面我就来介绍一下。

• 实现逻辑
  上文有讲述过归并排序这个算法的根本逻辑，也就是二分为一个个的子序列，使得子序列有序，再合并子序列。那么上面的递归版算法使用递归也就是为了找到这一个个的子序列一一的排序合并使得序列最终有序。那么我们只需要用另一种方式找到这些子序列，从最小的开始一一排序合并即可取代递归。
  既然是找序列，其实也就是找区间，我们对于子序列的排序等等操作其实都是一样的。那么可以用一个gap值代表区间的长度，然后对每一个被“划分“出来的子序列区间都进行同样排序合并操作，然后在让gap这个区间长度值每一次都乘2，得到更大一些的子序列，再合并……直到最终有序。也就是逆向的倍增区间大小，略过了二分的过程。

• 话不多说，直接上代码：

void Mergesort(int* arr,int n)
{int* tem = (int*)malloc(sizeof(int)*n);if(tem == NULL){perror("malloc fail!");exit(1);}int gap = 1;while(gap<n)//外层循环，控制子序列区间大小，二分找子序列{                                  //一次要完成两个数组的有序合并，一次要跳过两个子序列for(int i = 0;i < n;i += 2*gap)//内层循环，遍历整个序列，把所有的子序列都操作一边{int begin1 = i, end1 = i + gap - 1;//第一个区间int begin2 = i + gap, end2 = i + 2*gap - 1;if(bedin2 >= n)//第二个区间有可能越界：数组大小为奇数时{break;} if(end2 >= n)//第二个区间的末尾会出界，要作调整{end2 = n - 1;}int index = begin1;while(begin1 <= end1 && begin2 <= end2)//还是将两个有序序列合并之后，放到对应区间使有序{if(arr[begin1] < arr[begin2])tem[index++] = arr[begin1++];elsetem[index++] = arr[begin2++];}while(begin1 <= end1){tem[index++] = arr[begin1++];}while(begin2 <= end2){tem[index++] = arr[begin2++];}//for(int i = left;i < right;i++)//将有序的序列导入到原数组里去//{//	arr[i] = tem[i];//}    //这是找正确的位置               //这是区间长度memcpy(arr + i,tem + i,sizeof(int) * (end2 - i + 1));//省个事用拷贝库函数直接拷贝导入}gap *= 2;//调整区间长度，找到上一级子序列。}
}

非递归版本虽然操作不一样，但是时间复杂度还是O(N*logN)，外部循环每次二倍增加，内部循环还是O(N)，所以时间复杂度没变。

二、快速排序

算法介绍

快速排序是一个很有名的排序算法，被C和C++都采用为库函数中标准排序算法的底层代码，快速排序顾名思义它确实很“快”，效率很高。历史上于1962年由Hoare首先提出，是一种基于二叉树结构的交换排序算法，后续有许多大佬对这个算法有过优化，基于其根本思想有多种不同的实现方法。快速排序的根本思想是：任取待排序元素序列的中的某元素作为基准值，按照该基准值将待排序集合分割为两个子序列，每个子序列均大于或小于基准值，然后将每个子序列看作单独的序列重复该操作，直到所有元素都排列在相应位置上为止。这个算法的唯一特殊之处在于如何找基准值，快速排序有多种版本也是区别在于如何更好的取这个基准值，如最开始的Hoare版本和后来更好一些的lomuto前后指针法。但整体这个算法依旧是非常高效的算法。下面我来一一具体阐述。

递归实现

• Hoare版本算法

  • Hoare版的算法逻辑：
    Hoare版的算法中利用递归实现分割子序列，而找基准值的方法是：直接取最左边的数据令为基准值，取剩下的序列的最左右的值作为一个 “指针”（看作指向这个数据的下标）从左右往中心遍历数组，对于排升序的情况：左“指针”找比基准值小的数据，右“指针”找比基准值大的数据，各自找到之后，将左右指针对应的数据作交换，两“指针”按原路线继续往下遍历，当左指针>右指针时，把基准值对应数据和右指针作交换，完成分割。接下来就是递归，重复操作直至完成排序。
  • Hoare代码实现

  int Findkey(int* arr,int left,int right)//额外写一个找基准值的函数，完成找基准值和分割序列的工作
  {int key = left;++left;//左右两侧开始遍历while(left <= right)//开始调整序列分割{if(left<=right && arr[left] < arr[key])//还是排升序，这是在确定左右要交换的数据{left++;}if(left<=right && arr[right] > arr[key]){right--;}if(left<=right){swap(&arr[left++],&arr[right--]);//交换完之后记得继续往下遍历}swap(&arr[right],&arr[key]);//最后交换基准值完成分割}	return right;//right下标才是作分割的位置
  }
  void Quicksort(int* arr,int left,int right)//这里主函数参数不同了，要取序列左右下标值完成分割
  {if(left >=  right){return;}int key = Findkey(arr,left,right);//找基准值的下标Quicksort(arr,left,key - 1);//从key这里开始分割Quicksort(arr,key + 1,right);
  }
  

• lomuto前后指针法

  • 算法逻辑
    lomuto前后指针法基于快速排序的根本思想，提出了一种新的找基准值的方法：创建前后指针，从左往右找比基准值小的进行交换（升序情况），使得比基准值小的都排在基准值的左边。比如我们创建两个“指针”，一个prev，一个cur，先找最左边的作为基准值，prev等于最左端的下标，cur初始时比prev要大一，让cur在前面“探路”找比基准值要小的数据，找到之后，先将prev加1，再将prev和cur指针对应的数据交换，然后让cur继续往前走，没有找到就往前走直到找到为止。最后就得到了分割好的两个子序列，继续递归重复这个操作，快速排序就完成了。

  • lomuto前后指针实现

  void Findkey(int* arr,int left,int right)
  {int key = left;int prev = left + 1,cur = prev + 1；while(cur <= right){if(arr[cur] < arr[key] && ++prev != cur)//相等的话就是自己跟自己调位置，没必要{swap(&arr[prev],&arr[cur]);}cur++;}swap(&arr[key],&arr[prev]);return prev;
  }
  void Quicksort(int* arr,int left,int right)
  {if(left >=  right){return;}int key = Findkey(arr,left,right);Quicksort(arr,left,key - 1);Quicksort(arr,key + 1,right);
  }
  

• 时间复杂度分析
  快速排序的原理是每次找基准值同时遍历对应的序列完成调整，然后是分割递归，其实这跟归并的时间复杂度计算情况有点类似，每次递归的时间复杂度是O(N)，递归还是O(logN)，所以时间复杂度还是O(N*logN)。

非递归实现

快速排序的实现是从最开始的序列开始调整分割，然后从左至右对分割出来的每个序列再次分割调整，具有一定的顺序性才能正确完成排序。递归是存在顺序的，它先递推再回归，那么如果不用递归实现，那么就可以利用栈这个数据结构，每一次将分割出来的两个序列的左右边界入栈，然后取栈顶取到要调整分割的序列边界，不断重复直到调整完成。
现在我们来实现一下这个代码，由于要使用栈这个数据结构，在C语言阶段还需要额外实现栈这个数据结构然后利用栈的各种操作来完成算法，这里作者直接默认包含了一个栈相关操作的头文件，是跟我之前那篇栈文章的实现代码，大家如果不知道可以去看看 ^ V ^

#include"Stack.h"void Quicksort(int* arr,int left,int right)
{ST st;//创建一个栈STinit(&st);STPush(&st,left);STPush(&st,right);while(!STEmpty(&st)){int end = STTop(&st);//取栈顶两次，拿到左右边界，记得先取的是右边界STPop(&st);int begin = STTop(&st);STPop(&st);int key = begin;//在[begin,end]里调整分割int prev = begin,cur = prev + 1;//用一下lomuto前后指针法while(cur <= end){if(arr[cur] < arr[key] && ++prev != cur){swap(&arr[cur],&arr[prev]);}cur++;}swap(&arr[prev],&arr[key]);key = prev;//把左右序列都入栈，注意先右后左入栈，这样就先取到左序列开始调整if(key + 1 < end)//确保有效序列{STPush(&st,key + 1);STPush(&st,end);}	if(begin < key - 1){STPush(&st,begin);STPush(&st,key - 1);}}STDestroy(&st)
}

算法的一种优化—三路划分法

• 快速排序算法性能的探讨
  快速排序效率的关键影响因素就是key这个基准值，每一趟排序之后，key对于序列的分割如果是基本二分居中，那么效率将会最大化，当然实际中的情况并不太可能每次都二分居中，但有偏差性能也都是可控的，基本没什么波动。但如果是每次都取到最大最小值，那么排序就将变成双层循环，性能快速的退化到O(N^2)，这是很可怕的，另一种情况是数据中存在大量的和基准值相等的数据，那么也相当的影响效率，这里用一种优化算法来处理也就是三路划分法。

• 算法思想：
  为了让相同值不再影响，我们把相同值放在中间，然后再次划分左右两边的子序列。也就是这里的快速排序不再是仅仅划分两个子序列，而是将数据划分成三个部分。首先基准值key还是默认取最左侧值，类似lomuto前后指针法，定义left变量指向区间最左边，right变量指向区间最右边，cur初始指向left+1的位置。遇到比基准值小的和left交换，left和cur均++，遇到比基准值大的就与right交换，同时仅需right-1（因为cur值从左往右遍历），遇到和基准值相等的就直接让cur往前走。直至完成排序。

• 代码实现

void Quicksort(int* arr,int n)
{if (left >= right)                       {return;}int begin = left;int end = right;int randi = left + (rand() % (right - left + 1));//随机选值作为基准值，减少取到极值的可能性Swap(&arr[left], &arr[randi]);int key = arr[left];int cur = left + 1;while (cur <= right){if (arr[cur] < key){Swap(&arr[cur], &arr[left]);cur++;left++;}else if (arr[cur] > key){Swap(&arr[cur], &arr[right]);right--;}else{cur++;}}Quicksort(arr, begin, left - 1);Quicksort(arr, right + 1, end);
}

• 三路划分法对于数据重复的情况下效率依旧可以保持，但是对于其他情况还是一般，总体来说还是只是算法的一种优化，能够应对特殊的情况。但是快速排序依旧不能够完全的凭借本身的算法面对所有问题，所以在C++中，库虽然采用了快速排序作为标准排序算法，但当快速排序的递归进程过深（即时间复杂度快速升高，性能退化）的时候会自动的转向堆排序完成排序任务。当然，现实情况中肯定不会时刻都在处理特殊情况，它毋庸置疑还是一个非常强大的排序算法。

四、计数排序

前面文章讲解了归并排序和快速排序以及他们的几种实现代码，包括本文的前一篇文章也讲解了其他四种排序，这七种排序算法其实在更大的范围内可以归为同一类，称为比较排序，因为他们都是通过值的比较来完成排序的。而接下来这种排序算法则不同，它是非比较排序。那么接下来我们就来了解一下计数排序。

算法原理

计数排序又称为鸽巢原理，是哈希直接定址法的变形应用。它只有两步基本操作：

1）统计相同元素出现的个数，
2）根据统计的结果将序列回收到原来的序列中。

当然这是比较官方的话语，我们展开来讲：
首先我们直到，数组有下标，有序。那么我们就来利用这个下标：我们找出待排序序列的最大值，开一段空间，要开到下标有最大值为止，然后将数据化为下标，在数组里统计存储下标（数据）出现的次数，然后将所有数据按照出现的次数从左到右按顺序存入到原序列里，这样就完成了排序。这是典型的以空间换时间的操作（毕竟相比于现在的空间资源，效率还是更宝贵一些）
基本原理讲完了，但是这里有个问题还需要解决：首先，我们以空间换时间是效率的来源，那么我们到底要开多大的空间是一个问题，假如我们就取最大值作为空间大小，然后像内存要一个这么大的空间，万一数据都非常大而且都非常紧凑呢？难道前面那些没有用的空间就这么浪费了吗？我们有丰富的空间资源但是也不是这么浪费的。所以，我们可以同时找最小值，这样我们就确定了数据范围，只需要max - min + 1这么大的空间就足以胜任排序工作，这就使得空间利用率也达到最大，最后导入数据的时候也只需要加上min值就得到了原数据。

代码实现

原理明白了，那么就来实践一下代码：

void Countsort(int* arr,int n)
{int max = arr[0],min = arr[0];//第一次遍历数组，找最值for(int i = 1;i < n;i++){if(arr[i] < min){min = arr[i];}if(arr[i] > max){max = arr[i];}}int size = max - min + 1;//计算数据范围确定空间大小（后续计算时间复杂度也会用到）int* tem = (int*)malloc(sizeof(int)*size);//开辟空间统计数据if(tem == NULL){perror("malloc fail!");exit(1);}memset(tem,0,sizeof(int)*size);//将数组初始化为0，便于统计次数for(int i = 0;i < n;i++)//遍历原数组，统计次数{tem[arr[i] - min]++;//数据作为下标，让次数增长}int index = 0;//导入数据的一个下标表示for(int i = 0;i < size; i++){while(tem[i]--){arr[intdex++] = i + min;//导入原数据}}
}

优劣分析

• 优势
  计数排序用到了一个非常精妙的思想，了解了算法之后可以说完全没有难度，代码的实现相信是非常简单易懂的。从时间复杂度的角度来分析，计数排序的几个循环均为单层循环，最后的双层循环本质就是遍历一边原数组导入排序完毕的数据，所以本质还是单层循环，但次数为size。那么区别仅在于这个size的值，也就是总体的时间复杂度为O(N+size)。那么如果size的值相对较小，则计数排序将获得 非常接近于O(N) 的时间复杂度，这是一个非常恐怖的效率！又超越了前面几个强大算法一个档次！

• 劣势

  • 虽然计数排序的时间复杂度较高，但是确实是空间换时间换来的，不可避免会存在较大一些的空间损耗，这就是其中一个劣势之处，甚至有可能造成很大的空间资源浪费，虽然我们做出过改进尽可能优化了空间利用率，但数据的不同还是会造成这样的结果，比如最大值和最小值相差很大但是数据分布不均匀的情况，这一定会使得大量的空间只能被浪费。
  • 同样的，计数排序的利用数组下标的思想很精妙，但这也成了它的局限性，上文推导过时间复杂度为O(N+size)，我们知道在size 较小时，可以达到O(N)，那么反过头来，size很大呢？ 和空间大小挂钩即和数据本身有关这就带来了不确定和局限性，使得计数排序并不能适用于所有场景。不过在整数、范围相对较小、数据分布较密集时，它依旧拥有极高的效率，而对于浮点数、范围极大、稀疏分布或负数较多的情况应避免使用，可能会出现无法使用或效率下降（不如堆排序等）的情况。

五、排序算法的性能比较

作者在近两篇文章中讲述了七种排序算法，这里作者想额外的呈现一些东西，我来实现一个小的代码直观的比较一下几个算法的效率对比，比较的代码原码我直接放在下面，这里我是利用随机数生成，生成了八个一模一样的随机整形数组，数据量为100000个，范围也在100000以内，我还额外的添加了一个冒泡排序算法（时间复杂度为O(N^2)）来作一个对比。我将八种算法在我的电脑VS2022上运行，结果是每个排序所用时间值，单位是毫秒（ms）

这里是计算时间的代码：
#include<"time.h">
/.../
void TestOP()
{srand(time(NULL));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);int* a7 = (int*)malloc(sizeof(int) * N);int* a8 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];a7[i] = a1[i];a8[i] = a1[i];}int begin1 = clock();Insertsort(a1, N);int end1 = clock();int begin2 = clock();Shellsort(a2, N);int end2 = clock();int begin3 = clock();Selectsort(a3, N);int end3 = clock();int begin4 = clock();Heapsort(a4, N);int end4 = clock();int begin5 = clock();QuickSort(a5, 0, N - 1);int end5 = clock();int begin6 = clock();Mergesort(a6, N);int end6 = clock();int begin7 = clock();BubbleSort(a7, N);int end7 = clock();int begin8 = clock();Countsort(a8, N);int end8 = clock();printf("插入排序:%d\n", end1 - begin1);printf("希尔排序:%d\n", end2 - begin2);printf("选择排序:%d\n", end3 - begin3);printf("堆排序:%d\n", end4 - begin4);printf("快速排序:%d\n", end5 - begin5);printf("归并排序:%d\n", end6 - begin6);printf("冒泡排序:%d\n", end7 - begin7);printf("计数排序:%d\n", end8 - begin8);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);free(a8);
}

我连续运行了三次，结果如下：



这个数据似乎刚好比较符合计数排序的要求，无论怎么样都是小于等于1ms，秒杀全场。而标准的O(N^2)的冒泡排序则稳定20秒左右，效率的差距可见一斑。

---

总结

本文讲解了三个排序算法，也总结了几大排序算法的效率性能，希望能让大家了解什么是一个好的排序算法以及一个好的算法。