Hi~！这里是奋斗的小羊，很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~~
💥💥个人主页：奋斗的小羊
💥💥所属专栏：数据结构

🚀本系列文章为个人学习笔记，在这里撰写成文一为巩固知识，二为记录我的学习过程及理解。文笔、排版拙劣，望见谅。

前言

所谓排序，就是将一组数据按照某种顺序进行排列的过程。
排序在很多应用中都非常重要，比如数据分析、搜索算法、数据库管理等。
本篇文章将详细介绍常见的排序算法。

一、常见排序算法

1、插入排序

1.1直接插入排序

插入排序是一种简单直观的排序算法，它的基本思想是将待排序的元素分为已排序和未排序两部分，然后逐步将未排序的元素插入到已排序的部分中，直到所有元素都被排序。

动图演示：

插入排序是比较容易理解的，代码实现也比较简单，唯一需要注意的是下标的取值范围，因为我们是从下标为1的元素开始向前比较的，所以下标最大的取值应该为n-2，这样保证我们刚好取到下标为n-1的最后一个元素。

代码示例：

//插入排序（升序）voidInsertSort(int*arr,intn){ //先单次，再整体for(inti =0;i <n -1;i++){ //假设[0,end]有序，将end+1位置的元素插入intend =i;inttmp =arr[end +1];while(end >=0){ if(tmp <arr[end]){ arr[end +1]=arr[end];end--;}else{ break;}}arr[end +1]=tmp;}}

插入排序时间复杂度是O(N^2)，总体来说效率也是不高的，但在某些场景中还是有发挥空间。

1.2希尔排序

希尔排序是一种插入排序的改进版本，以增量gap（通常是gap = n/3 + 1）来划分元素，使得远离的元素能够交换，从而加快整体排序的速度。它的基本思想是将待排序的序列分成若干个子序列（也称为“增量”），对每个子序列进行直接插入排序，然后逐步减少增量（gap = gap / 3 + 1），最终进行一次普通的插入排序，从而实现整体排序。

• 当gap > 1时都是预排序，目的是让数组更接近于有序
• gap = gap / 3 + 1;后面+1是为了保证最后一次gap的值为1

当gap=1时，相当于直接插入排序，希尔排序是直接插入排序算法上改进而来的，综合来说它的效率肯定是要高于直接插入排序的。

代码示例：
（1）

// 希尔排序voidShellSort(int*a,intn){ intgap =n;while(gap >1){ gap =gap /3+1;for(inti =0;i <gap;i++){ for(intj =i;j <n -gap;j +=gap){ intend =j;inttmp =a[end +gap];while(end >=0){ if(tmp <a[end]){ a[end +gap]=a[end];end -=gap;}else{ break;}}a[end +gap]=tmp;}}}}

（2）

//希尔排序voidShellSort(int*arr,intn){ //多组并着走intgap =n;while(gap >1){ gap =gap /3+1;for(inti =0;i <n -gap;i++){ intend =i;inttmp =arr[end +gap];while(end >=0){ if(tmp <arr[end]){ arr[end +gap]=arr[end];end -=gap;}else{ break;}}arr[end +gap]=tmp;}}}

这两种方式都是可以的，虽然循环层数不一样，但是时间复杂度是一样的。
希尔排序的时间复杂度比较特别，理想情况下希尔排序的时间复杂度为：O(N^1.3)。希尔排序和堆排序是一个量级的。

根据希尔排序的特点，可以总结出下面的折线图：

因此，希尔排序在最初和最后的排序次数都为n，即前一阶段排序次数逐渐上升，当到达某一顶点时，排序次数逐渐下降到n，而该顶点非常难计算。

因为gap的取值很多，导致希尔排序的时间复杂度不好计算，我们只需记住当n在某个特定返回内，时间复杂度约为O(N^1.3)。

2、选择排序

2.1直接选择排序

选择排序的基本思想是每一次从待排序的数组中选出最小（或最大）的一个数，存在起始位置，知道全部数据排完。为了提高效率，我们每次从待排序数组中同时找到最小和最大的两个数，分别将它们放到起始、末尾位置。

动图演示：

代码示例：

//选择排序voidSelectSort(int*arr,intn){ intbegin =0;intend =n -1;while(begin <end){ intmini =begin;intmaxi =begin;for(inti =begin +1;i <=end;i++){ if(arr[i]<arr[mini]){ mini =i;}if(arr[i]>arr[maxi]){ maxi =i;}}Swap(&arr[mini],&arr[begin]);if(begin ==maxi){ maxi =mini;}Swap(&arr[maxi],&arr[end]);begin++;end--;}}

如果选择的第一个元素就是最大的元素，则当最小的元素和这个位置的元素交换后，最大的元素位置就变化到之前最小元素的位置了，这时候就需要改变最大元素位置的下标。

直接选择排序的时间复杂度是O(N^2)，效率很低，甚至还比不过冒泡排序，因此在实际中基本不使用，主要用于教学。

2.2堆排序

堆排序在之前的文章中有详解介绍，这里就不再赘述。

voidHeapSort(int*arr,intn){ //升序，建大堆//降序，建小堆//向下调整建堆//O(N)for(inti =(n-1-1)/2;i >=0;i--){ AdjustDown(arr,i,n);}//O(N*logN)intend =n -1;while(end >0){ Swap(&arr[0],&arr[end]);AdjustDown(arr,0,end);end--;}}

3、交换排序

3.1冒泡排序

冒泡排序是一种简单的排序算法，其基本原理是通过重复遍历待排序的元素，比较相邻的两个元素，如果顺序错误则交换它们，直到没有需要交换的元素为止。

当某一趟并未发生交换说明此时数组已经有序，可以提前退出循环，我们可以设定一个标志来判断某一趟是否未发生交换。

动图演示：

代码示例：

// 冒泡排序voidBubbleSort(int*a,intn){ for(inti =0;i <n -1;i++){ intflag =1;for(intj =0;j <n -1-i;j++){ if(a[j]>a[j +1]){ flag =0;swap(&a[j],&a[j +1]);}}if(1==flag){ break;}}}

冒泡排序的时间复杂度是O(N^2)，效率是比较低的，在实际应用中很少用到，主要用于教学。

3.2快速排序

快排算法的核心就是分割区间。

快速排序是一种二叉树结构的交换排序法，其基本思想是：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两个子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列有序。

快排主框架：

void_QuickSort(int*arr,intleft,intright){ //递归结束条件if(left >=right){ return;}//_QuickSort用于按照基准值将区间[left, right)中的元素进行划分QuickSort(arr,left,keyi -1);QuickSort(arr,keyi +1,right);}

将区间中的元素进行划分的_QuickSort方法主要有以下几种实现方法。

3.2.1 hoare版本

| 算法思路：（默认排升序）

• 创建左右指针，确定基准值
• 从右向左找出比基准值小的数据，从左向右找出比基准值大的数据，左右指针数据交换，进入下次循环
• 如果在最左边找基准值，则右边先走，反之则左边先走

动图演示：

我们可以将最左边的数作为基准值，先从右向左找小于基准值的数记住当前位置end，然后从左向右找大于基准值的数记住当前位置begin，交换两个数的位置；重复上述操作直到begin和end指向同一位置，此时这个位置的值一定小于基准值，最后再将这个位置的值与基准值交换位置，此时作为基准值的数已经排到了它相应的位置。

代码示例：

//快速排序voidQuickSort(int*arr,intleft,intright){ if(left >=right){ return;}intkeyi =left;intbegin =left;intend =right;while(begin <end){ //右边找小while(begin <end &&arr[end]>=arr[keyi]){ end--;}//左边找大while(begin <end &&arr[begin]<=arr[keyi]){ begin++;}Swap(&arr[begin],&arr[end]);}Swap(&arr[begin],&arr[keyi]);keyi =begin;QuickSort(arr,left,keyi -1);QuickSort(arr,keyi +1,right);}

但是此时的快排代码还有一些缺陷，当待排集合已经接近有序时，快排的效率是很低的，如果数据量比较大还会因为函数递归太深而导致栈溢出。
因为我们将最左边的数当做基准值时，如果这个数恰好是最小或比较小的数，此时从右向左的数基本都比这个基准值大，所以会有很多次的递归调用。

| 优化一：
解决这个问题的办法就是我们找基准值时尽量找数据中不大不小的数，可以粗略的从数据头、数据中、数据尾三个位置的值中选中间值作为基准值，这样就可以很大的降低递归太深而导致栈溢出的风险。

//三数取中intGetMidi(int*arr,intleft,intright){ intmidi =(left +right)/2;if(arr[left]<arr[right]){ if(arr[right]<arr[midi ]){ returnright;}elseif(arr[left]<arr[midi ])//arr[left]//arr[midi ]{ returnmidi ;}else{ returnleft;}}else{ if(arr[right]>arr[midi ]){ returnright;}elseif(arr[left]>arr[midi ]){ returnmidi ;}else{ returnleft;}}}

拿到理想的基准值后，为了保证我们之前写的按最左边数作为基准值，可以将这个基准值和最左边的数交换位置。

//快速排序voidQuickSort(int*arr,intleft,intright){ if(left >=right){ return;}intmidi =GetMidi(arr,left,right);Swap(&arr[left],&arr[midi ]);intkeyi =left;intbegin =left;intend =right;while(begin <end){ //右边找小while(begin <end &&arr[end]>=arr[keyi]){ end--;}//左边找大while(begin <end &&arr[begin]<=arr[keyi]){ begin++;}Swap(&arr[begin],&arr[end]);}Swap(&arr[begin],&arr[keyi]);keyi =begin;QuickSort(arr,left,keyi -1);QuickSort(arr,keyi +1,right);}

| 优化二：
我们知道快速排序是二叉树结构的排序算法，当二叉树的层数较高时，此时分割的区间数据量比较小，而递归次数又占总体的大部分，可以考虑小区间优化，不再递归分割排序，减少递归的次数。
当数据量比较小时，排序算法的效率基本一致，我们优先考虑简单且较为高效的插入排序。

//快速排序voidQuickSort(int*arr,intleft,intright){ if(left >=right){ return;}//小区间优化，不再递归分割排序，减少递归次数if((right -left)+1<10){ InsertSort(arr +left,(right -left)+1);}else{ //三数取中intmidi =GetMidi(arr,left,right);Swap(&arr[left],&arr[midi ]);intkeyi =left;intbegin =left;intend =right;while(begin <end){ //右边找小while(begin <end &&arr[end]>=arr[keyi]){ end--;}//左边找大while(begin <end &&arr[begin]<=arr[keyi]){ begin++;}Swap(&arr[begin],&arr[end]);}Swap(&arr[begin],&arr[keyi]);keyi =begin;QuickSort(arr,left,keyi -1);QuickSort(arr,keyi +1,right);}}

有了这两个优化，快排的效率就能得到很大的提升。

3.2.2 挖坑法

| 算法思路：（默认排升序）

首先将最左边的数据作为基准值拿出来，则原位置形成一个空位，创建左右指针，从右向左找出比基准值小的数据，找到后立即放入左边坑中，当前位置变为新的“坑”，重复上述操作直到左右指针相遇，最后再将基准值放入左右指针共同指向的“坑”中。

动图演示：

代码示例：

//挖坑法voidQuickSort(int*arr,intleft,intright){ //递归结束条件if(left >=right){ return;}//区间优化，减少递归次数if(right -left +1<10){ InsertSort(arr +left,right -left +1);}else{ //三数取中intmidi =GetMidi(arr,left,right);Swap(&arr[left],&arr[midi]);intkeyi =left;inttmp =arr[keyi];intbegin =left;intend =right;while(begin <end){ while(begin <end &&arr[end]>=tmp){ end--;}arr[keyi]=arr[end];while(begin <end &&arr[begin]<=tmp){ begin++;}if(begin ==end){ arr[begin]=tmp;break;}arr[end]=arr[begin];keyi =begin;}keyi =begin;QuickSort(arr,left,keyi -1);QuickSort(arr,keyi +1,right);}}

挖坑法虽然没有效率的提升，但是相对于hoare版本还是有一些优势：

• 挖坑法不用分析为什么左边取基准值而右边先走的问题，因为当左边取基准值时左边就自然而然的形成了一个“坑”
• 也不用分析为什么相遇位置一定比基准值小（或大）的问题，因为它相遇的位置是坑，自然而然的基准值就应该放在坑里

3.2.3 前后指针法

| 算法思路：
创建前后指针，两个指针从左向右分别找遇到的第一个小于和大于基准值的数进行交换，将所有大于基准值的数全都推到最后，使得小的都排在基准值的左边，大的都排在基准值的右边。

动图演示：

代码实现：

//前后指针法intQuickSort3(int*arr,intleft,intright){ //三数取中intmidi =GetMidi(arr,left,right);Swap(&arr[left],&arr[midi]);intkeyi =left;intprev =left;intcur =prev +1;while(cur <=right){ //先判断大小，再++prev，保证了当不满足大小时prev不再++if(arr[cur]<arr[keyi]&&++prev !=cur){ Swap(&arr[prev],&arr[cur]);}cur++;}Swap(&arr[keyi],&arr[prev]);returnprev;}

这三种快排算法，前后指针法代码是最为清晰明了的，但三种算法时间复杂度是一样的。

| 三种快排算法汇总：

//三数取中intGetMidi(int*arr,intleft,intright){ intmidi =(left +right)/2;if(arr[left]<arr[right]){ if(arr[right]<arr[midi]){ returnright;}elseif(arr[left]<arr[midi]){ returnmidi;}else{ returnleft;}}else{ if(arr[right]>arr[midi]){ returnright;}elseif(arr[left]>arr[midi]){ returnleft;}else{ returnmidi;}}}//hoare法intQuickSort1(int*arr,intleft,intright){ //三数取中intmidi =GetMidi(arr,left,right);Swap(&arr[left],&arr[midi]);intkeyi =left;intbegin =left +1;intend =right;while(begin <end){ //左边作基值，右边先走while(begin <end &&arr[end]>=arr[keyi]){ end--;}while(begin <end &&arr[begin]<=arr[keyi]){ begin++;}Swap(&arr[begin],&arr[end]);}Swap(&arr[begin],&arr[keyi]);returnbegin;}//挖坑法intQuickSort2(int*arr,intleft,intright){ //三数取中intmidi =GetMidi(arr,left,right);Swap(&arr[left],&arr[midi]);intkeyi =left;inttmp =arr[keyi];intbegin =left +1;intend =right;while(begin <end){ while(begin <end &&arr[end]>=tmp){ end--;}arr[keyi]=arr[end];while(begin <end &&arr[begin]<=tmp){ begin++;}if(begin ==end){ arr[begin]=tmp;break;}arr[end]=arr[begin];keyi =begin;}returnbegin;}//前后指针法intQuickSort3(int*arr,intleft,intright){ //三数取中intmidi =GetMidi(arr,left,right);Swap(&arr[left],&arr[midi]);intkeyi =left;intprev =left;intcur =prev +1;while(cur <=right){ //先判断大小，再++prev，保证了当不满足大小时prev不再++if(arr[cur]<arr[keyi]&&++prev !=cur){ Swap(&arr[prev],&arr[cur]);}cur++;}Swap(&arr[keyi],&arr[prev]);returnprev;}voidQuickSort(int*arr,intleft,intright){ //递归结束条件if(left >=right){ return;}//区间优化，减少递归次数if(right -left +1<10){ InsertSort(arr +left,right -left +1);}else{ intkeyi =QuickSort3(arr,left,right);QuickSort(arr,left,keyi -1);QuickSort(arr,keyi +1,right);}}

3.3 快排非递归

上面几种快排算法都是用递归思想解决的，虽然有三数取中和小区间优化的加持，但递归始终是有缺陷的，递归的方法难免在极端情况下有栈溢出的风险，我们可以考虑用非递归来进一度的优化。

我们知道递归是递和归的过程，这和我们之前学过的栈的特点有点类似，因为栈是一个后入先出的结构，它可以模拟递和归的过程，那我们就可以考虑用栈来实现非递归的过程。

事实上非递归的思想还是递归，只是实现方法不同。快排过程每一次递归最主要的数据就是区间，我们可以循环入栈、出栈相应的区间来模拟递归，循环每走一次，相当于一次递归。

voidQuickSortNonR(int*arr,intleft,intright){ stack st;stack_init(&st);stack_push(&st,right);//先入右后入左stack_push(&st,left);while(!stack_empty(&st)){ intbegin =stack_top(&st);stack_pop(&st);intend =stack_top(&st);stack_pop(&st);intkeyi =QuickSort3(arr,begin,end);//先入右区间，再入左区间if(keyi +1<end)//0、1个数时不用入栈{ stack_push(&st,end);stack_push(&st,keyi +1);}if(begin <keyi -1){ stack_push(&st,keyi -1);stack_push(&st,begin);}}stack_destroy(&st);}

其中有几个需要特别注意的点：

• 栈的特点是后入先出，所以区间先入右后入左
• 当区间不存在或者只有一个数时不再需要入栈
• 当栈为空时排序完成

这是一个深度优先遍历的过程，整个过程基本和递归的过程是一样的。

总结

• 相对于插入、选择、冒泡，实际中通常使用效率更高的希尔、堆排、快排等，其中快排的非递归算法使我们应该重点掌握的内容。