＜ 数据结构 ＞ 八大排序

选择排序特性总结

1、直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用

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

3、空间复杂度：O(1)

4、稳定性：不稳定

4、堆排序

堆排序我在上篇博文已经重点讲解过，这里简要提下

1. 对数组建堆要向下建堆，因为其时间复杂度小
2. 排升序要建大堆，排降序建小堆

如若各位小伙伴们还有些疑问，可以看这篇博文

堆排序 + topK问题

• 这里直接给出代码：

//交换void Swap(int* pa, int* pb){int tmp = *pa;*pa = *pb;*pb = tmp;}//向下调整算法void AdjustDown(int* a, size_t size, size_t root){int parent = (int)root;int child = 2 * parent + 1;while (child < size){//1、确保child的下标对应的值最大，即取左右孩子较大那个if (child + 1  a[child]) //得确保右孩子存在{child++; //此时右孩子大}//2、如果孩子大于父亲则交换，并继续往下调整if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = 2 * parent + 1;}else{break;}}}//升序void HeapSort(int* a, int n){//向下调整建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}//大堆升序size_t end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}}int main(){int a[] = { 4,2,7,8,5,1,0,6 };HeapSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < sizeof(a) / sizeof(int); i++){printf("%d ", a[i]);}return 0;}

堆排序特性总结

1、堆排序使用堆来选数，效率就高了很多。

2、时间复杂度：O(N*logN)

3、空间复杂度：O(1)

4、稳定性：不稳定

5、冒泡排序

• 基本思想：

冒泡排序（Bubble Sort）一种交换排序，它的基本思想是：它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。元素项向上移动至正确的顺序，就好像气泡升至表面一样，冒泡排序因此得名。

• 排序步骤：

1. 相邻的两个元素比较，大的上浮，小的下沉，这样一趟冒泡排序即可确保大值排列在一端
2. 确定趟数，趟数为数组总个数-先前排过的趟数

• 动图演示：

• 代码如下：

//交换void Swap(int* pa, int* pb){int tmp = *pa;*pa = *pb;*pb = tmp;}//冒泡排序void BubbleSort(int* a, int n){for (int j = 0; j < n; j++){//单趟for (int i = 1; i  a[i]){Swap(&a[i], &a[i - 1]);}}}}

• 冒泡排序的优化：

根据上述代码，有个缺陷：如果我的数组本身就有序或着说是接近有序，那我还需要每一趟都进去比较相邻两个数字的大小吗？如果每次都要比，那时间复杂度就要提升，为此可以定义一个变量exchange，如果说发生了比较，那么exchange的值保存为1，如果没有比较，则exchange为0，就退出

• 总代码如下：

//交换void Swap(int* pa, int* pb){int tmp = *pa;*pa = *pb;*pb = tmp;}//冒泡排序void BubbleSort(int* a, int n){for (int j = 0; j < n; j++){int exchange = 0;//单趟for (int i = 1; i  a[i]){exchange = 1;Swap(&a[i], &a[i - 1]);}if (exchange == 0)break;}}}

冒泡排序特性总结

1、冒泡排序是一种非常容易理解的排序

2、稳定性：稳定

3、空间复杂度：O(1)

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

最好情况：数组本身是顺序的，外层循环遍历一次就完成

最坏情况：数组本身是逆序的，内外层遍历

6、快速排序

• 基本思想：

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

快速排序分为三种方法

1. hoare法
2. 挖坑法
3. 前后指针法

而其右可以使用递归和非递归来实现，接下来我将依次演示：

hoare法

• 单趟动图演示：

hoare法的快排分为以下步骤：

1. 选出一个key，一般是第一个数，或者是最后一个数
2. 定义变量L和R，L从左走，R从右走
3. R先向前走，找到比key小的位置停下，再让L向后走，找到比key大的值停下
4. 交换L和R代表的数值
5. 继续遍历，同样让R先走，L后走，同上规则
6. 当L和R相遇的时候，把相遇位置的值与key位置的值交换，结束

排完一趟要求如下：

1. 左边的值都比key小
2. 右边的值都比key大

提问：如何保证相遇位置的值比key小？

• 答案：不需要保证，此算法思想（右边先走）足矣解决。注意看本算法思想，它明确了每次让R先走，R找到比key小的值之后才会停下来，这时候才轮到L走，L要么找不到比key大的值就一直走直至相遇R，此时正好满足小于key，要么L找到比key大，交换L和R的值，但随后，R又会继续向前走，一直走，最坏刚好遇到L，因为L先前和R已经换过一次，也就是说这个L的值一定是比key小的，那么同样交换key的值，综上，此算法思想足矣解决。

提问：如若key为最右边的值呢？排完一趟如何？

思想和上面一样，唯一要改变的是此时是L先走，R后走，其余没有变

• 动图演示：

•  接下来，就先写下单趟排序： 

//快排单趟排序int PartSort(int* a, int left, int right){int keyi = left; //选左边作keywhile (left < right){//右边先走，找小while (left = a[keyi]) //防止right找不到比keyi小的值直接飙出去，要加上left < right{right--;}//右边找到后，左边再走，找大while (left < right && a[left] <= a[keyi]) //同上，也要加上left < right{left++;}//右边找到小，左边找到大，就交换Swap(&a[left], &a[right]);}//此时left和right相遇，交换与key的值Swap(a[keyi], &a[left]);return left;}

• 写好了单趟排序，就要进行整体排序了

仔细观察上述单趟排序，有没有发现排完后，key已经排到了正确的位置，因为其左边的值均小于key，而右边的值均大于key，此时key的位置就是最终排序好后应该在的位置。那么如果左边有序，右边有序，那么整体就有序了，只需要用到递归+分治的思想即可。

• 画图演示：

• 总代码如下：

//hoare//快排单趟排序int PartSort(int* a, int left, int right){int keyi = left; //选左边作keywhile (left < right){//右边先走，找小while (left = a[keyi]) //防止right找不到比keyi小的值直接飙出去，要加上left < right{right--;}//右边找到后，左边再走，找大while (left < right && a[left] <= a[keyi]) //同上，也要加上left = end){return;}int keyi = PartSort(a, begin, end);//分成左右两段区间递归// [begin, keyi-1] 和 [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}

挖坑法

• 动图演示单趟挖坑：

 挖坑法的步骤如下：

1. 把最左边的位置用key保存起来，此位置形成坑位
2. 定义变量L和R分别置于最左和最右
3. 让R先向前走，找到比key小的位置停下
4. 找到后，将该值放入坑位，自己形成新的坑位
5. 再让L向后走，找比key大的位置停下
6. 找到后，将该值放入坑位，自己形成新的坑位
7. 再让R走……
8. 当L和R相遇时，把key的值放到坑位，结束

挖坑法相较于上面的hoare法并没有优化，本质上也没有区别，但是其思想更好理解

1. 不需要理解为什么最终相遇位置比key小
2. 不需要理解为什么左边做key，右边先走

• 总代码如下：

//挖坑法int PartSort2(int* a, int left, int right){//把最左边的值用key保存起来int key = a[left]; //把left位置设为坑位pitint pit = left;while (left < right) //当left小于right时就继续{//右边先走，找小于key的值while (left = key){right--; //如若right的值>=key的值就继续}//找到小于key的值时就把此位置赋到坑位，并把自己置为新的坑位a[pit] = a[right];pit = right;//左边走，找大于key的值while (left < right && a[left] = end){return;}int keyi = PartSort2(a, begin, end);//分成左右两段区间递归// [begin, keyi-1] 和 [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}

前后指针法

快排特性总结

1、快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

2、稳定性：不稳定

3、空间复杂度：O(logN)

4、时间复杂度：O(N*logN)

快排的时间复杂度分两种情况讨论：

1. 最好：每次选key都是中位数，通俗讲是左边一半右边一半，具体看是key的左序列长度和右序列长度相同。时间复杂度O(N*logN)
2. 最坏：每次选出最小的或者最大的作为key。时间复杂度O()

• 画图分析：

可能有人会觉着正常的数组怎么会次次都会选出最小的或者最大的作为key呢？这也太巧合了，但是仔细想想，当数组是有序或者接近有序时，不就是最坏的情况吗？更何况如若数据量再大一点，程序很有可能会因为数据量过多而递归次数过多以至于栈溢出，

综上我们需要深思：能否针对快排最坏的情况进行优化？看下文：

快排优化

 就以最坏的情况为例：

三数取中

小区间优化

假设快排每次递归的过程中，选出key，然后递归分成左边和右边，并且都是均匀的，如果是有序，每次选中间值，这个过程就像是二分，跟二叉树的样子差不多，正如上述画过的图：

快排递归调用的简化图其实就类似于一个二叉树，假设长度N为1000，那么递归调用就要走logN层也就是10层，假设其中一个递归到只有5个数了，那么还要递归3次，当然这只是左边的，右边还要递归3次，这么小的一块区间还要递归这么多次，小区间优化就是为了解决这一问题，针对最后的小区间进行其它的算法排序，就比如插入就很可以

当递归到越小的区间时，递归次数就会越多，针对这一小区间采取插入排序更优，减少了大量的递归次数

• 代码如下：

//三数取中优化int GetMidIndex(int* a, int left, int right){    //……}//前后指针法int PartSort3(int* a, int left, int right){//三数取中优化int midi = GetMidIndex(a, left, right);Swap(&a[midi], &a[left]);    //……}//小区间优化void QuickSort2(int* a, int begin, int end){//子区间相等只有一个值或者不存在那么就是递归结束的子问题if (begin >= end){return;}//小区间直接插入排序控制有序if (end - begin + 1 <= 10){InsertSort(a + begin, end - begin + 1);}else{int keyi = PartSort3(a, begin, end);// [begin, keyi-1] 和 [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}}

快排非递归

先前的学习中，我们的快排都是用递归来实现的，但是要知道：递归也是有缺陷的。如果深度过大，可能会导致栈溢出，即使你用了快排优化可能也无法解决此问题，所以我们引出非递归的版本来解决栈溢出问题。

• 规则：

在快排递归的过程中是要建立栈帧的，仔细看看每次递归时传的参数，有begin和end，其递归过程存储的是排序过程中要控制的区间，那我们用非递归模拟递归的过程中也要按照它这个存储方式进行，这就需要借助栈了，跟上篇博文的层序遍历一样利用到了栈

依旧以如下乱序数组示例：

• 代码如下：

//快排非递归void QuickSort3(int* a, int begin, int end){ST st;StackInit(&st);//先把第一块区间入栈StackPush(&st, begin);StackPush(&st, end);while (!StackEmpty(&st)) //栈不为空就继续{int right = StackTop(&st);StackPop(&st);int left = StackTop(&st);StackPop(&st);//使用前后指针法进行排序int keyi = PartSort3(a, left, right); // keyi已经到了正确位置// [left, kryi-1]  [keyi+1, right]if (left < keyi - 1)//如若左区间不只一个数就入栈{StackPush(&st, left);StackPush(&st, keyi - 1);}if (keyi + 1 < right)//若右区间不只一个就入栈{StackPush(&st, keyi + 1);StackPush(&st, right);}}StackDestory(&st);}

上述代码恰好巧妙的实现了递归的过程，仔细观察上述代码，一开始我们入栈了下标为begin和end的值，如下：

 随后，取出这两个值，并用right和left分别保存起来，随后对区间[left，right]这块区间进行单趟排序，取出keyi的值为5，此时a[keyi]也就排到了正确的位置了，接下来就是效仿递归的关键了，以keyi为分界线，将数组分为两块区间：【left，keyi-1】和【keyi+1，right】，此时再把这两块区间的入栈：

 接下来进入第二趟while循环，同样是再次出栈里的两个数据6和9，并再次传入单趟排序，算出keyi的值为8，也就意味着a[keyi]到了正确的位置，再以keyi为分界线，将右区间的数组分为【6，7】和【9，8】以此类推……一直排下去

7、归并排序

• 动图演示：

• 基本思想：分治思想

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并

假设我们有左右两块有序区间的数组，可以对它直接进行合并。此时我们需要借助第三方数组，一次比较两块区间的起始位置，把小的那个放到新数组，随后依次比较，小的就放新数组，一直到结束。

但是现在存在一个问题？上述条件是假设了左半区间和右半区间有序，但是原先数组是无序的啊，也就是左半区间和右半区间均无序。怎么才能达到左半区间和右半区间有序最后再归并成整体有序呢？这就体现到了分治的思想了，将数组一直分，分到1个1个的，归并成有序变成2个2个的，然后归并成有序成4个4个的，最后再4个4个的归并成有序，最终至整体有序。

• 画图解析其完整的归并过程：

 这里我们先用代码实现其分解递归的过程，并用打印法表示其结果

画图演示其部分递归分治的过程：

• 总代码如下：

void _MergeSort(int* a, int begin, int end, int* tmp){if (begin >= end)return; //区间不存在就返回int mid = (begin + end) / 2;//[begin, mid] [mid+1, end]_MergeSort(a, begin, mid, tmp); //递归左半_MergeSort(a, mid + 1, end, tmp); //递归右半//归并[begin, mid] [mid+1, end]//printf("归并[%d,%d][%d,%d]\n", begin, mid, mid + 1, end);int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int index = begin;while (begin1 <= end1 && begin2 <= end2){//将较小的值放到tmp数组里头if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}//如若begin2先走完，把begin1后面的元素拷贝到新数组while (begin1 <= end1){tmp[index++] = a[begin1++];}//如若begin1先走完，把begin2后面的元素拷贝到新数组while (begin2 <= end2){tmp[index++] = a[begin2++];}//归并结束后，把tmp数组拷贝到原数组memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));}//归并排序void MergeSort(int* a, int n){//malloc一块新数组int* tmp = (int*)malloc(sizeof(int) * n);assert(tmp);_MergeSort(a, 0, n - 1, tmp);free(tmp);}

归并排序非递归

• 思想：

归并的非递归不需要借助栈，直接使用循环即可。递归版中我们是对数组进行划分成最小单位，这里非递归我们直接把它看成最小单位进行归并。我们可以通过控制间距gap来完成，先看图：

上述情况其实是在理想状态下可行的，只要数组长度不是2的次方倍都会出现问题，先简要看下理想状态下的伪代码，并用printf打印下归并过程：

再强调一遍，只要数组长度不是2的次方倍都会出现问题，像上述长度为8没有问题，那如若长度为6呢？

当长度为6不再是2的次方数时就运行出现问题了，综上我们需要考虑下极端情况：根据上述的区间范围，我们可以总结出以下三个可能会出现越界的情况：

1. end1越界
2. begin2越界
3. end2越界

1、end2越界：

2、begin2和end2均越界：

 

3、end1和begin2和end2均越界 

 

综上，我们需要单独对这些极端情况处理

//end1越界，修正即可if (end1 >= n){end1 = n - 1;}//begin2越界，第二个区间不存在if (begin2 >= n){begin2 = n;end2 = n - 1;}//begin2 ok，end2越界，修正下end2即可if (begin2 = n){end2 = n - 1;}

•  总代码如下：

//归并非递归void MergeSortNonR(int* a, int n){int* tmp = (int*)malloc(sizeof(int) * n);assert(tmp);int gap = 1;while (gap < n){//分组归并，间距为gap是一组，两两归并for (int i = 0; i = n){end1 = n - 1;}//begin2越界，第二个区间不存在if (begin2 >= n){begin2 = n;end2 = n - 1;}//begin2 ok，end2越界，修正下end2即可if (begin2 = n){end2 = n - 1;}printf("归并[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);int index = i;while (begin1 <= end1 && begin2 <= end2){//将较小的值放到tmp数组里头if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}//如若begin2先走完，把begin1后面的元素拷贝到新数组while (begin1 <= end1){tmp[index++] = a[begin1++];}//如若begin1先走完，把begin2后面的元素拷贝到新数组while (begin2 <= end2){tmp[index++] = a[begin2++];}}memcpy(a, tmp, n * sizeof(int));gap *= 2;}free(tmp);}

归并排序特性总结

 1、归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。

2、时间复杂度：O(N*logN)

3、空间复杂度：O(N)

4、稳定性：稳定 

内排序和外排序

在排序中，分为内排序和外排序，简单了解下其概念：

• 内排序：数据量较少，在内存中进行排序
• 外排序：数据量很大，在磁盘上进行排序

而我们前面学习的排序中，归并排序既可作为内排序，也可作为外排序，而其它几个排序只能是内排序，这也就说明了在处理数据量很大时，采用归并排序才能解决，其它排序不可。

如若我要排10亿个整数，就只能使用归并排序了，现在来简要算下其占比大小：

• 1G = 1024MB
• 1MB = 1024KB
• 1KB = 1024Byte
• 综上1G = 1024*1024*1024Byte，而10亿个整数40亿Byte，所以10亿个整数占4G

现在有10亿个整数（4G）的文件，只给你1G的运行内存，请对文件中的10亿个数进行排序

核心思想：数据量大，加载不到内存。想办法控制两个有序文件，两个有序文件归并成一个更大的有序文件。可以把这4G的文件分成4等份，每一份1G，分别读到内存进行归并排序，排完后再写回到磁盘小文件

8、计数排序

• 动图演示：

• 基本思想：

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。用到的是哈希映射的思想。

• 操作步骤：

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

假设现在要对如下数组进行排序：

计数的核心步骤就是数组中数字的值是多少，就把该值映射到新开辟数组的下标上。仔细观察这串数组，最大数字为10，所以这里我们要开辟11个空间，才能保证数字10放到新数组下标为10的位置，遍历原数组，一个val出现几次，它映射的位置++几次

上述方法即哈希的绝对映射思想，原数组的某个元素是几，对应新开辟数组下标为几的位置就相应的加加，出现几次，加加几次。此方法看似可行，但存在一个大问题，空间复杂度过大，如若一组数据为【10000，9999，5000，9999，5000，8888】，难道说为了排这几个数字，你要开辟10001个大小空间的数组吗，得不偿失，更何况你这10001个空间的前5000个空间没有值映射，纯纯浪费了空间，这就是绝对映射的弊端，因此要用相对映射

• 绝对映射：原数组是几，映射到新数组下标位置++
• 相对映射：此时新数组下标的范围是从0到原数组最小的值，而映射到下标的位置为原数组val的值 - 原数组最小min的值

看图说话： 

综上，基数排序使用于数据有一些重复，数据范围比较集中 ，从而避免空间浪费过于严重

• 代码如下：

//计数排序void CountSort(int* a, int n){int min = a[0], max = a[0];//先求出原数组的最大和最小值for (int i = 1; i < n; i++){if (a[i]  max)max = a[i];}//求出新数组的范围int range = max - min + 1;//开辟新数组int* countA = (int*)malloc(sizeof(int) * range);assert(countA);//把新开辟数组初始化为0memset(countA, 0, sizeof(int) * range);//计数for (int i = 0; i < n; i++){countA[a[i] - min]++; //统计相同元素出现次数（相对映射）}//排序int j = 0;for (int i = 0; i < range; i++){while (countA[i]--){a[j++] = i + min; //赋值时，记得加回原先的min}}free(countA);}

计数排序特性总结

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(N + range)
3. 空间复杂度：O(range)
4. 稳定性：稳定

9、图表汇总

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

10、总结

读到这的小伙伴，非常感谢你们的支持，此博文真的是耗费了n久，写了得有1周多，本不需要这么长，奈何自己手残，在创作快结束的时候按了个ctrl+z键，1.8w的大长文只剩下2k不到了，自己还没备份，可真是命苦啊，纯纯大冤种！！最后无奈又重新复盘了一份，害，说多了都是泪。以后再无ctrl z。还得感慨下这个动图是真的不好做，还记得自己前些天挑灯夜战动图，只为呈现更好的效果~

• 想要排序源码的可以到我的gitee仓库里查看：

八大排序汇总集合