《数据结构》八大排序算法 必读！
版权声明：版权所有，未经许可，不得转载，转载或者引用本文内容请注明来源及原作者
前言
本文将介绍常见八大排序，包括直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序以及计数排序（计数排序和桶排序面试基本不涉及，本文将简要介绍），本内容是重点中的重点，请务必全部掌握！
01
插入排序
1.1
直接插入排序
基本思想
把一个数插入到有序区间，保持这个区间有序，当前第n+1个数插入到前面，前面的arr[0]到arr[n-1]已经排好序，此时用arr[n]与前面的arr[n-1], arr[n-2]…的值。进行比较找到合适的位置将arr[n]进行插入，原来位置上的元素顺序后移实现了插入
代码实现
void ShellSort1(int* a, int n)
{
int gap = n;
while (gap>1)//别傻乎乎的加等号啊，死循环
{
gap = gap / 3 + 1;end的范围是[0,n-gap)
for (int i = 0; i < n - gap; i++)//并排走
{
int end = i;
int temp = a[end + gap];
while (end>=0)
{
//当前的end的值比tmp大就要往end+gap位置挪
//所以要提前保存end+gap的值
if (temp < a[end])
{
a[end + gap] = a[end];
end = end-gap;
}
else
{
break;
}
}
a[end + gap] = temp;
}
}
}
时间复杂度
插入排序的时间复杂度也是O（N^2）,在接近有序的情况下他的时间复杂度是O（N），因为遍历一遍就可以出结果了，空间复杂度O（1）。
1.2
希尔排序
希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。
基本思想
希尔排序就是在处理一些极端情况比较高效，比如在上面的插入排序时如果我们在原数组降序的情况下去排升序，那么我们交换的次数是十分多的，也可以说是插入排序的最坏的情况，这个时候聪明的先辈想到了希尔排序，将数组分成了gap组，然后可以理解为分别处理每一个小组，gap从5 – 2 – 1的过程在降序的情况下，排在后面的数值小的数能步子更大排到前面，当gap为1的时候实际上就是进行了一次插入排序。设置gap的过程我们也称之为预排序。 gap越小，越接近有序，gap越大，越不接近有序； 但是gap越小挪动越慢，gap越大挪动越快；
代码实现
void ShellSort1(int* a, int n)
{
int gap = n;
while (gap>1)//别傻乎乎的加等号啊，死循环
{
gap = gap / 3 + 1;end的范围是[0,n-gap)
for (int i = 0; i < n - gap; i++)//并排走
{
int end = i;
int temp = a[end + gap];
while (end>=0)
{
//当前的end的值比tmp大就要往end+gap位置挪
//所以要提前保存end+gap的值
if (temp < a[end])
{
a[end + gap] = a[end];
end = end-gap;
}
else
{
break;
}
}
a[end + gap] = temp;
}
}
}
时间复杂度
O(N^1.3)，一般gap建议以gap/3+1的步骤走。
02
选择排序
简单选择排序思路如下动图所示，就是只针对头部的一个数进行对比，代码实现大家可以自己敲敲！
2.1
选择排序（二元改进版）
基本思想
优化的选择排序，每次可以选择一个最大的和一个最小的，然后把他们放在合适的位置，即最小的放在第一个位置，最大的放在最后一个位置。 然后再去选择次小的和次大的，依次这样进行，直到区间只剩一个值或没有。
代码实现
void SelectSort(int* a, int n)
{
assert(a);
int begin = 0, end = n - 1;
while (begin < end)
{
int min = begin, max = begin;
for (int i = begin; i <= end; i++)//注意起点是begin
{
if (a[i] >= a[max])
max = i;
if (a[i] < a[min])
min = i;
}
//最小的放在
Swap(&a[begin], &a[min]);
//如果最大的位置在begin位置
//说明min是和最大的交换位置
//这个时候max的位置就发生了变换
//max变到了min的位置
//所以要更新max的位置
if (begin == max)
max = min;
Swap(&a[end], &a[max]);
++begin;
--end;
}
}
时间复杂度
O(N^2)，最坏的排序
2.2
堆排序
基本思想
现在就强调一点：排升序要建大堆，排降序建小堆。 这里以升序为例：先建堆，排升序建大堆，选出最大的数将其放到最后面，然后满足大小堆后即可做向下调整动作。
代码实现
//堆排序
void AdjustDown(int* a, int n, int parent){
int child = parent*2 + 1;
while(child < n){
if(child+1<n && a[child+1] > a[child]){
++child;
}
if(a[child]>a[parent]){
Swap(&a[child], &a[parent]);
parent = child;
child = parent*2+1;
}else{
break;
}
}
}
void HeapSort(int* a, int n){
//排升序建大堆 O(N)
for(int i=(n-1-1)/2; i>=0; i--){
AdjustDown(a, n, i);
}
//O(N*logN)
int end = n - 1;
while(end > 0){
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0); //是不是妙不可言hhh！
end--;
}
}
时间复杂度
时间复杂度是O（N*logN），空间复杂度O（1）
03
交换排序
3.1
冒泡排序
基本思想
以升序为例，每一趟的冒泡排序都是把一个最大的数放到最后面，如果 a[i-1]>a[i],我们将i-1,i的值进行交换，依次循环反复。
代码实现
void BubbleSort(int* a, int n){
for(int j=0; j<n; j++){
int flag = 0;
for(int i=1; i<n-j; ++i){
if(a[i] < a[i-1] ){
Swap(&a[i], &a[i-1]);
flag = 1;
}
}
if(flag == 0){
break;
}
}
}时间复杂度
O(N^2)
3.2
快速排序
3.2.1
Hoare
基本思想
选一个关键key，一般都是选择头。 单趟：key放在他正确的位置上，key的左边值比key小，key右边值比key大（这是key一趟下来排完后最终要放的位置） 单趟拍完，再想办法让左边区间有序，key的右边区间有序。 那么还有优化解决方案： 第一种是取随机值做下标。 第二种是获取这三个数中不是最大，也不是最小的那个值的下标，这种情况下不会有最坏情况，因为有三数取中。
代码实现
//三数取中（为了优化）
int MidIndex(int* a, int left, int right)
{
int mid = left + (right - left) / 2;
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return right;
}
else
{
return left;
}
}
else //a[left] > a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//不妨思考一下我们进行“三数取中”的意义是什么？单趟排序
//一个单趟进行的排序操作的时间复杂度是多少？思考下一次完整的快排需要进行多少趟这样的单趟排序？
int PartSort1(int* a, int left, int right)
{
int midi = MidIndex(a, left, right);
Swap(&a[left], &a[midi]);
//最左边的做key为例
int key = left;
while (left<right)
{
//因为我们是最左边的取key，所以必须是右边先走找比key小的，思考下为什么？
//右边先走
while (left < right && a[right] >= a[key])
{
--right;
}
//然后左边走
while (left < right && a[left] < a[key])
{
++left;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[key]);//此时left已经和right相遇，一样的
return left;
}
全趟排序（递归）
void QuickSort(int* a, int left, int right)
{
//当区间分割到只剩一个或者没有的时候就返回
if (left >= right)
return;
//确定一个位置，划分区间递归
//分为[left,key-1] key [key+1，right]
//int key = PartSort1(a, left, right);
int key = PartSort2(a, left, right);
QuickSort(a, left, key - 1);
QuickSort(a, key + 1, right);
}第一个问题：不妨思考一下我们进行“三数取中”的意义是什么？
如果我们不进行“三数取中”，快排如果遇见最坏的情况——有序，时间复杂度将会变成O（N^2），如果加了“三数取中”，这一最坏情况将会不复存在（后边俩种单趟排序同理）。当然了，实际面试过程当中时间不够没必要再来写一个“三数取中”，面试争分夺秒啦！
第二个问题：一个单趟进行的排序操作的时间复杂度是多少？思考下一次完整的快排需要进行多少趟这样的单趟排序？
一个单趟的时间复杂度是O（N），一个完整的快排需要O（logN）趟这样的单趟排序。
第三个问题：为什么key选择最左边的值，就要先让右边的数先走先去找小？
为了确保最后相遇时的a[left]<a[key]，只要让右边的数先走，最后停下来时无论是“左边遇到右边”还是“右边遇到左边”，都满足a[left]<a[key]。
时间复杂度
一整个快排：O（N*logN）
3.2.2
前后指针法
基本思想
1.cur往前走，找到比key小的数据 2.找到比key小的数据以后，停下来，++prev 3.交换prev和cur指向位置的值 直到cur到达最右边的位置结束！ cur还没遇到比key大的数据之前，prev紧跟着cur，cur遇到比key大的值以后，prev和cur之间间隔着一段比key大的数据。
代码实现
int PartSort2(int* a, int left, int right)
{
int midi = MidIndex(a, left, right);
Swap(&a[midi], &a[left]);
//这里key选取最左边的元素为例
int key = left;
int prev = left, cur = prev + 1;
while (cur<=right)
{
if (a[cur] < a[key] && ++prev != cur)//防止自己与自己交换
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
//cur走到末尾啦，交换一下。
Swap(&a[prev], &a[key]);//这里可以保证交换之前a[prev]一定小于a[key],思考下为啥？
return prev;
}
答案：跳出while循环的a[prev]，在跳出循环之前刚与a[cur]交换过，而a[prev]与a[cur]交换的条件就是a[cur]小于a[key],所以可以保证交换跳出while循环后发生最后一次交换之前a[prev]一定小于a[key]。
全趟排序（递归）
void QuickSort(int* a, int left, int right)
{
//当区间分割到只剩一个或者没有的时候就返回
if (left >= right)
return;
//确定一个位置，划分区间递归
//分为[left,key-1] key [key+1，right]
//int key = PartSort1(a, left, right);
int key = PartSort2(a, left, right);
QuickSort(a, left, key - 1);
QuickSort(a, key + 1, right);
}
时间复杂度
一整个快排：O（N*logN）
3.2.3
挖坑法
基本思想
挖坑法可以选择在0索引处挖坑（即把数拿走保存），然后从右边找一个小的填坑，再从左边找一个大的埋住右边的坑，以此反复循环，直到left与right相遇，最后把key放入相遇点（最后一个坑位）即可。
代码实现
int PartSort3(int* a, int left, int right)
{
int midi = MidIndex(a, left, right);
Swap(&a[midi], &a[left]);
//这里key取最左边的数，让右边的先开始走找小
int hole = left;
int key = a[left];
while (left < right)
{
//先找右边比key小的，填到左边的坑里面去
while (left < right && a[right] >= key)
{
right--;
}
a[hole] = a[right];
hole = right;
//再找左边比key大的，找到就交换坑位
while (left<right&&a[left]<key)
{
left++;
}
a[hole] = a[left];
hole = left;
}
a[left] = key;//最后把key放到相遇点
return left;
}全趟排序（递归）
void QuickSort(int* a, int left, int right)
{
//当区间分割到只剩一个或者没有的时候就返回
if (left >= right)
return;
//确定一个位置，划分区间递归
//分为[left,key-1] key [key+1，right]
//int key = PartSort1(a, left, right);
int key = PartSort3(a, left, right);
QuickSort(a, left, key - 1);
QuickSort(a, key + 1, right);
}时间复杂度
一整个快排：O（N*logN）
3.3
快速排序（非递归）
我们前面实现快排是采用递归的方式，但是递归本身是有“原罪”的，这个“原罪”在于如下：
1.当递归深度过大的时候，递归程序本身可能没用错误，但是编译之后会报错——栈溢出（stack overflow）。 2.性能问题（某些书上提到的，但是现在编译优化得很好，这个问题不大）。
任何一个递归程序，我们要把他改成非递归程序有如下俩种方式：
1.循环(但是有的东西是不好改成循环的，比如二叉树的遍历、快排等) 2.“栈”模拟（这个“栈”是数据结构中的“栈”，不是系统内部那个“栈”，一般用到栈难度都是略大的） 这里的快排改非递归用的就是“栈”模拟。
基本思想
非递归的在这里借助栈，依次把我们需要单趟排的区间入栈，依次取栈里面的区间出来单趟排，再把需要处理的子区间入栈，以此循环，直到栈为空的时候即处理完毕。
代码实现(非递归)
void QuickSortNonR(int* a, int left, int right)
{
//非递归，我们可以处理当前的区间，再处理分区间
//先入右，后入左，就先拿到左
Stack s;
StackInit(&s);
StackPush(&s,right);
StackPush(&s,left);
while (!StackEmpty(&s))
{
left = StackTop(&s);
StackPop(&s);
right = StackTop(&s);
StackPop(&s);
//处理当前区间 [left,right]
int key = PartSort3(a, left, right);
//划分左右区间，分别入栈
//[left,key-1] key [key+1,right]
//先入右区间,区间有两个值才需要处理
if (key + 1 < right)
{
StackPush(&s, right);
StackPush(&s, key + 1);
}
//再入左区间
if (left < key - 1)
{
StackPush(&s, key - 1);
StackPush(&s, left);
}
}
}
时间复杂度
最优的时间复杂度是O(nlogn)，最差的空间O(n^2) ，因为进行了三数取中，不存在最差情况。
04
归并排序
4.1
递归实现归并排序
基本思想
我们可以把一个数组分成两半，对于每一个数组当他们是有序的就可以进行一次合并操作。对于他们的两个区间进行递归，一直递归下去划分区间，当区间只有一个值的时候我们就可以进行合并返回上一层，让上一层合并再返回。
代码实现
void _MergeSort(int* a, int left, int right,int* newArr)
{
if (left >= right)
return;
int mid = left + (right - left) / 2;
//[left,mid][mid+1,right]
_MergeSort(a, left, mid,newArr);
_MergeSort(a, mid + 1, right,newArr);
//走到这里已经是左右区间有序
//将两个区间合并成一个区间
//拷贝到newArr当中，排完再放回
int index = left;
int begin1 = left, end1 = mid;
int begin2 = mid+1,end2 = right;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
newArr[index++] = a[begin1++];
}
else
{
newArr[index++] = a[begin2++];
}
}
//走到这里一定有一边没有走完
while (begin1 <= end1)
{
newArr[index++] = a[begin1++];
}
while (begin2 <= end2)
{
newArr[index++] = a[begin2++];
}
//拷贝回元素组 letf -- right 的位置
for (int i = left; i <= right; ++i)
{
a[i] = newArr[i];
}
}
void MergeSort(int* a, int n)
{
//归并排序就是在左右区间有序重新组合起来
//所以保证左右区间都是有序，遍历到叶子就可以
int* newArr = (int*)malloc(sizeof(int) * n);
int left = 0;
int right = n - 1;
_MergeSort(a, left, right,newArr);
}时间复杂度
O（NlogN)，可以看出他的递归过程中每次都将一组平均分，分完后高度大概是logN，空间复杂度O（N）
4.2
迭代实现归并排序
跟快排类似，递归会带给快排的问题同样会给归并排序带来，所以尝试用非递归方式！
任何一个递归程序，我们要把他改成非递归程序有如下俩种方式：
1.循环(但是有的东西是不好改成循环的，比如二叉树的遍历、快排等) 2.“栈”模拟（这个“栈”是数据结构中的“栈”，不是系统内部那个“栈”，一般用到栈难度都是略大的） 这里归并排序非递归实现就是采用“循环”。
基本思想
迭代实现可以用循环来实现，这里我们根据递归思想其实很容易知道，我们控制迭代从最小的子问题出发，保存最小子问题的值，然后提供给后面用，这其实就是一个动态规划的思想，我们可以从利用子问题的解，解决 “大BOSS” 。
代码实现
void MergeSortNonR(int* a, int n)
{
//int a[] = { 8,4,5,7,1,3,6,2,7,8 };
int* newArr=(int*)malloc(sizeof(int)*n) ;
int groupNum = 1;
int left;
int right;
//动态规划的思想，当我们把最小的问题切割
while(groupNum<n/2+1)
{
for (int i = 0; i < n; i += (2*groupNum))
{
//分成两组[begin1,end1][begin2,end2]
int begin1 = i;
int end1 = i + groupNum - 1;
int begin2 = i + groupNum;
int end2 = i + 2 * groupNum - 1;
//处理两种情况，当end1已经越界，说明处理end1的边界
if (end1 >= n)
{
end1 = n - 1;
}
//当end1越界，理所当然的begin2和end2都越界了
//这里可能的[begin1,end1]区间，也需要拷贝到临时数组，再拷回原数组
if (begin2 >= n)
{
//表示右区间不存在
begin2 = n;
end2 = n-1;
}
else if (begin2 < n && end2 >= n)
{
end2 = n - 1;
}
left = begin1;
right = end2;
//index用于放到临时数组newArr当中的
int index = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
newArr[index++] = a[begin1++];
}
else
{
newArr[index++] = a[begin2++];
}
}
//走到这里一定有一边没有走完
while (begin1 <= end1)
{
newArr[index++] = a[begin1++];
}
while (begin2 <= end2)
{
newArr[index++] = a[begin2++];
}
//拷贝回元素组 letf -- right 的位置
for (int x = left; x <= right; ++x)
{
a[x] = newArr[x];
}
}
groupNum*=2;
}
free(newArr);
newArr = NULL;
}
时间复杂度
O（NlogN)
05
计数排序
基本思想
1.统计原数组中每个值出现的次数 2.排序：遍历Count数组，对应位置的值出现多少次就往原数组写几个这个值 当然，在对于数据比较大的时候我们可以通过相对映射，让（该值-min）后的数组加一，最后还原回去即可。
代码实现
void CountSort(int* a, int n)
{
//int a[] = { 31,24,25,16,1,0,79 };
//遍历一遍找到最大和最小，然后开大一的数组
int max = a[0];
int min = a[0];
for (int i = 1; i < n; ++i)
{
if (max < a[i])
{
max = a[i];
}
if (min > a[i])
{
min = a[i];
}
}
int size = max - min + 1;
int* tmp = (int*)calloc(size,sizeof(int));
//将a遍历映射到tmp当中,a的长度是n，tmp的长度只有size
for (int i = 0; i < n; ++i)
{
tmp[a[i] - min]++;//tmp[i]存放的是这个值出现的次数
}
//在按照tmp当中的存放放回去
int index = 0;
for (int i = 0; i < size; ++i)
{
while (tmp[i] > 0)
{
//这里应该是下标+映射的
a[index++] = i + min;
--tmp[i];
}
}
}
时间复杂度
计数排序的时间复杂度是O（N），空间复杂度是O(max-min),就是我们开的数组是这个区间的范围差。
06
八大排序对比
6.1
八大排序的性能测试评估
// 测试排序的性能对比
void TestOP()
{
srand(time(0));
const int N = 10000;
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);
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];
}
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(a4, 0, N-1);
int end5 = clock();
int begin6 = clock();
MergeSort(a6, N);
int end6 = clock();
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("SelectSort:%d\n", end3 - begin3);
printf("HeapSort:%d\n", end4 - begin4);
printf("QuickSort:%d\n", end5 - begin5);
printf("MergeSort:%d\n", end6 - begin6);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
}
结果如下
6.2
各个排序的稳定性如何判断？
直接看排完序后是否能保证相同的值的相对位置不会发生变化，若能保证，就是稳定，反之即不稳定。 不要死记，一定要理解分析！ 冒泡排序：俩俩对比，前一个大于后一个才发生交换（升序），不会出现相等值互换顺序的情况，能保证不改变相同值的相对顺序，稳定。 选择排序：在进行俩数交换位置的过程当中，可能数组当中有一个数跟发生交换的俩数数值是一样的，这样就改变的相同数之间的相对顺序，不稳定。 插入排序：从前到后一个个元素拿出来跟前面的对比，若插入的数值比被对比的数值小，被对比的数值往后挪动；若插入的数值比被对比的数值大，直接插入到被对比数值的后面，并没有改变俩个相同值得相对顺序，稳定。 希尔排序：在预排序时，相同的数据可能在不同的组里面，没办法控制，所以不稳定。 堆排序：比如俩个一样大的数值，一个在“树顶”，一个在“树中”，树顶元素跟最后一个元素发生交换立马影响相同数值的相对顺序，不稳定。 归并排序：能保证相同值得相对顺序不变，稳定。 快速排序：比如数组中存在跟key数值一样的值，而key是肯定会移动的，这样相对顺序就改变了，所以不稳定。 计数排序：计数是在统计每个数出现的次数，但是相同的数哪个在前哪个在后，并没有区分，所以不稳定。
补充：稳定性有什么意义？
比如我们做了一个考试系统，考生当中先交卷的，成绩在数组的前面，后交卷的，成绩在数组后面。当我们对前几名进行排名的时候，就可能会遇见俩个分值相同的考生，这时候为了公平性考试用时较短者应当在前面。
6.3
八大排序时间/空间复杂度一览
腾讯云开发者
