数据结构|【算法】图解八大排序数据结构|算法

文章图片

文章目录

前言
一、插入排序
二、希尔排序
三、选择排序
四、堆排序
五、冒泡排序
六、快速排序
- 递归版
- - hoare版
  - 挖坑法
  - 前后指针法
- 非递归
七、归并排序
- 递归版
- 非递归
八、计数排序
总结

??注：本文基于C语言编写，由 VisualStudio 2019 所实现前言 ??在我们生活的这个世界中到处都是被排序过的东东，可以说排序是无处不在。

文章图片

常见的莫过于点外卖，按照「销量最高」「好评最多」等选择你今日的午餐；考试按照「分数高低」排名次。

文章图片

值得注意的是：排序有很多种，它们适合的情况不同，需根据不同场景运用。这些排序算法中对应一些基本思想，了解实现原理比光看代码更重要！
提示：以下排序均以升序实现，代码仅供参考
??为方便数据交换，提高代码可读性，先写一个交换函数

void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; }

一、插入排序 【数据结构|【算法】图解八大排序】??插入排序的原理应该是最容易理解的了，因为只要你打过扑克牌，应该能够秒懂。插入排序是一种最简单直观的排序算法，它的原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。如下图：

文章图片

算法思想

通过不断将当前元素「插入」到「有序」序列中，直到所有元素都执行过「插入」操作，则排序结束。

??动图演示

图示	含义
■ 的长柱	表示正在进行比较或移动的数
■ 的长柱	表示已排好序的数
■ 的长柱	表示正在执行插入的数
■ 的长柱	表示待排的数

算法分析

单趟分析：

1.假定「前n-1个」数已经有序，「第n个」数从「第 n-1个」开始，自后向前逐一比较。
2.当前一个数大于「第n个」数时，将该「元素」往后移.
3.当遇到一个小于等于「第n个」数的「元素」或来到「第一个元素位置」时，先将「该元素」往后移，以空出该位置，并将「第n个」数移动到此处。至此，单趟结束

多趟分析：

如何做到前n个元素有序呢？即从第一个元素开始，依次往后进行插入操作，直至最后一个元素为止

例：前5个元素已经有序

??我们看到，首先需要将「第六个元素」和「第五个元素」进行「比较」，如果前者大于后者，则进行「交换」，然后再比较「第六个元素」和「第四个元素」，以此类推，直到「第六个元素」被移动到「合适位置」。
??然后，进行第二轮「比较」，直到「第七个元素」被移动到「合适位置」。
??最后，经过一定轮次的「比较」和「交换」之后，一定可以保证所有元素都是「升序」排列的。

参考代码
??值得注意的是:当第 i 个元素向后移时，即第 i+1 个元素的值被覆盖为第 i 个元素的值，但第 i 个元素值仍未变.因此，跳出循环后，第 i 个元素位置即为待插入位置
代码如下：

void InsertSort(int* a, int n) { assert(a); //所有趟 for (int i = 0; i < n - 1; i++) {// 单趟排序 // end 表示有序序列最后元素的下表 int end =i; // 待插入的元素 int tmp = a[end + 1]; while (end >= 0) {if (tmp < a[end]) {//后一个元素被前一个元素覆盖 a[end + 1] = a[end]; end--; } else {break; } } // 待插入位置，值为 tmp a[end + 1] = tmp; } }

时间复杂度
??由图可以看出，当待排序列越接近有序，其时间复杂度越低，越接近无序，时间复杂度越高。例如：当整体序列为「升序序列」时为O(N) ,最坏情况下，即整体序列为「降序序列」时为O( N 2 N^2 N2)
二、希尔排序 ??希尔排序，也称递减增量排序算法，按其设计者希尔（Donald Shell）的名字命名，该算法由希尔 1959 年公布，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：

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

算法思想

??希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
??即，先进行预排序，使之接近有序，再进行插入排序。
??动图演示

文章图片

注:每一趟排序中，相同颜色为一组
算法分析

??由图可以看出，希尔排序一个特点是：子序列的构成不是简单的「逐段分割」,而是将相隔某个增量「gap」的数据组成一个子序列。如上图：

第一趟排序时: gap = 5 ， 9 和 4 为一组， 1 和 8 为一组， 2 和 6 为一组， 3 和 5 为一组， 5 和 7 为一组。
第二趟排序时: gap = 2 ， 4，2，5，5，8为一组， 1，3，6，7，9为一组.
第三趟排序时: gap = 1 ，整体为一组

??因为是相隔 gap 的元素为一组，每组各自进行排序，因此在整体来看，每个元素的移动是「跳跃式」的
??不断减小 gap，整体愈加接近「有序」
??当 gap = 1 时，即为「插入排序」,只需要对以上数列进行简单的微调，不需要大量的移动操作即可完成整个数组的排序。

??这里有个问题： gap 取多少合适？

gap 越大，数据挪动快，但越不接近有序
gap 越小，挪动越慢，但越接近有序

??事实上，gap 的取法有多种。最初Shell提出取gap = 「n / 2」，gap=「gap / 2」，直到 gap = 1,后来Knuth提出取gap=「gap / 3」+1。还有人提出都取奇数为好，也有人提出各gap互质为好。无论哪一种主张都没有得到证明。
参考代码

void ShellSort(int* a, int n) { // gap > 1预排序 // gap == 1 直接插入排序 int gap = n; while (gap > 1) {// 保证最后一次为 1 gap = gap / 3 + 1; // 间隔为gap,多组并排 for (int i = 0; i < n - gap; i++) {int end = i; int tmp = a[end + gap]; while (end >= 0) {if (a[end] > tmp) {a[end + gap] = a[end]; end -= gap; } else {break; } } a[end + gap] = tmp; } } }

时间复杂度
??时间复杂度:O(N log N)
??其中，《数据结构(C语言版)》— 严蔚敏有以下说明

文章图片

三、选择排序算法思想
??每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在待排序列的起始位置，直到全部待排序的数据元素排完。
??动图演示

图示	含义
■ 的长柱	表示正在进行比较的数
■ 的长柱	表示已排好序的数
■ 的长柱	表示最小的数
■ 的长柱	表示待排的数

算法分析

??首先，找到待排序列中「最小/大」的元素，拎出来，将它和序列的「第一个元素」交换位置，第二步，在剩下的元素中继续寻找「最小/大」的元素，拎出来，和序列的「第二个元素」交换位置，如此循环，直到整个序列排序完成。
??实际上，我们可以一次选出「最小」和「最大」的元素，分别置于待排序列的「起始」和「末尾」，以提高算法效率。这就要求，我们必须考虑待排序列的「末端位置」，以及「最大/小」元素的「下标」。

参考代码
错误范例：

void SelectSort(int* a, int n) { int begin = 0; int end = n - 1; // 当begin 和 end 相遇，即只有一个元素 while (begin < end) {// 分别用以记录最大/小值下标 int maxi = begin; int mini = begin; for (int i = begin; i <= end; i++) {//大于最大值，重新赋值 if (a[i] > a[maxi]) {maxi = i; } //小于最小值，重新赋值 if (a[i] < a[mini]) {mini = i; } } //将最小值与起始位置交换 Swap(&a[mini], &a[begin]); //最大值与末尾交换 Swap(&a[maxi], &a[end]); //对应新的首尾位置 end--; begin++; } //跳出循环，则排序完成 }

??事实上，运行结果并不正确，示例如图

文章图片

??分析第二次运行，第一趟交换，可以发现，当「maxi 」与「begin 」重合时，进行第一次「交换」后，「maxi 」对应值来到了「mini」的位置。故须考虑「maxi 」是否与「begin 」重合的情况，如图：

正确代码如下：

void SelectSort(int* a, int n) { int begin = 0; int end = n - 1; // 当begin 和 end 相遇，即只有一个元素 while (begin < end) {// 分别用以记录最大/小值下标 int maxi = begin; int mini = begin; for (int i = begin; i <= end; i++) {if (a[i] > a[maxi]) {maxi = i; } if (a[i] < a[mini]) {mini = i; } } Swap(&a[mini], &a[begin]); //考虑maxi 与 begin关系，相同，则maxi对应位置变化为 mini if (maxi == begin) {maxi = mini; } Swap(&a[maxi], &a[end]); //对应新的首尾位置 end--; begin++; } //跳出循环，则排序完成 }

时间复杂度
??时间复杂度:O( N 2 N^2 N2)
??直接选择排序思想非常好理解，但是效率不是很好，实际中很少使用。且其稳定性：不稳定
四、堆排序 ??堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
准备知识
大根堆和小根堆
性质：每个结点的值都大于其左孩子和右孩子结点的值，称之为大根堆；每个结点的值都小于其左孩子和右孩子结点的值，称之为小根堆。如图：

文章图片

基本概念
查找数组中某个数的父结点和左右孩子结点，比如已知索引为i的数，那么
父结点索引：(i - 1) / 2（取整）
左孩子索引：2 * i + 1
右孩子索引：2 * i + 2
算法思想

1.首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端
2.将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为 n - 1
3.将剩余的 n - 1 个数再构造成大根堆，再将顶端数与 n - 1 位置的数交换，如此反复执行，便能得到有序数组

??动图演示
建大堆：

图示	含义
??	表示正在比较的数
■ 的矩形	表示堆中正在比较的数，对应数组元素位置

堆排序：

文章图片

算法分析
建大堆：

建堆有一个方法，叫做「向下调整法」。那么如何实现呢？
如图：左右子树均为大堆

文章图片

1.选出左右孩子中较大元素，若大于根节点，与之交换
2.原来的大孩子变为父亲节点，与其孩子比较，重复步骤一，直至调整到叶子节点为止。
若孩子均小于父亲节点，则无需再处理。已经是大根堆了。如图所示：

文章图片

那么，如何保证左右子树均为大根堆呢？即从最后一个根节点往前进行「向下调整法」，即可保证左右子树均为大堆。

参考代码
向下调整法：

void AdjustDown(int* a, int n, int root) { //创建孩子节点 int child = root * 2 + 1; while (child < n) {// 若child == n - 1，不可加 //找到最大的孩子 if (child + 1 < n && a[child] < a[child + 1]) {child++; } // 与最大的孩子进行交换 if (a[root] < a[child]) {Swap(&a[root], &a[child]); root = child; child = child * 2 + 1; } else {break; } } }

堆排序：

void HeapSort(int* a, int n) { assert(a); //建大堆 int root = (n - 1 - 1) / 2; while (root >= 0) {AdjustDown(a, n, root); root--; } //堆排序 while (n) {//首位交换，保证最大的来到最后 Swap(&a[0], &a[n - 1]); // 参与排序的元素个数减 1 n--; // 向下调整 AdjustDown(a, n, 0); } }

时间复杂度
??时间复杂度:O(N log N)
五、冒泡排序 ??冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端
算法思想
??通过不断比较相邻的元素，如果「左边的元素」大于「右边的元素」，则进行「交换」，直到所有相邻元素都保持升序，则排序结束。

??动图演示

图示	含义
■ 的长柱	表示正在进行比较或交换的数
■ 的长柱	表示已排好序的数
■ 的长柱	表示待排的数

算法分析

1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
单趟分析：

假设从第一趟开始，将「第一个」元素与「第二个」元素进行「比较」，若「前者」大于「后者」，进行「交换」。随后，将「第二个」元素与「第三个」元素进行上述操作，直至将「倒数第二个」元素与「最后一个」元素进行「比较」，至此，「最大」元素来到了最后。

多趟分析：

假设共有 n 个数，则须进行 n - 1 趟上述操作，每一趟比较前 n - i + 1 个数，最大元素来到第 n - i -1 的位置（ i = 1,2,3~~n)

因此冒泡的代码还是相当简单的，两层循环，外层冒泡趟数，里层依次比较，江湖中人人尽皆知。

参考代码
??冒泡有一个最大的问题就是这种算法不管你有序还是无序，闭着眼睛把你循环比较了再说。针对这个问题，我们可以设定一个临时遍历来标记该数组是否已经有序，如果有序了就不用遍历了。
代码如下：

void BubbleSort(int* a, int n) { // 该循环用于控制趟数 for (int end = n - 1; end > 0; end--) {//设置临时变量exchange，记录数据是否交换 int exchange = 0; for (int i = 0; i < end - 1; i++) {if (a[i] > a[i + 1]) {Swap(&a[i], &a[i + 1]); //exchange 变为1，表示该趟有数据交换 exchange = 1; } } //若exchange == 0，表示该趟无数据交换，已经有序，跳出循环 if (exchange == 0) break; } }

时间复杂度
??我们看到嵌套循环，应该立马就可以得出这个算法的时间复杂度:O( N 2 N^2 N2)
六、快速排序 ??快速排序(QuickSort)是对冒泡排序的一种改进。
算法思想
??它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
递归版 hoare版
算法思想
??快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
算法图解
单趟：

??选择最左边的元素作为关键值key,
文章图片

??首先哨兵「 j 」开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵「 j 」先出动，这一点非常重要（请自己想一想为什么）。哨兵「 j 」一步一步地向左挪动（即 j – ），直到找到一个小于「 key」的数停下来。接下来哨兵「 i 」再一步一步向右挪动（即 i++ ），直到找到一个大于「 key」的数停下来。最后哨兵 j 停在了数字 5 面前，哨兵「 i 」停在了数字 7 面前。交换数据…

文章图片

??接下来哨兵「 j 」继续向左挪动（注：每次必须是哨兵「 j 」先出发）。他发现了4 （比基准数「 key」要小，满足要求）之后停了下来。哨兵「 i 」也继续向右挪动，他发现了 9（比基准数「 key」要大，满足要求）之后停了下来。此时再次进行交换…

文章图片

??第二次交换结束，“探测”继续。哨兵「 j 」继续向左挪动，他发现了 3之后又停了下来。哨兵「 i 」继续向右移动，糟啦！此时哨兵「 i 」和哨兵「 j 」相遇了，说明此时“探测”结束。我们将「 key」和哨兵「 i 」所处地址的值进行交换，单趟探测结束。并返回基准值的下标

文章图片

多趟：

??每一趟返回一个基准值下标，表示该基准值已来到正确位置。通过返回值，将待排序列分割左右两组，重复上述步骤。

参考代码
单趟代码如下：

int PartSort1(int* a, int left, int right) { //选择一个基准值 int keyi = left; while (left < right) {//注意：left < right 这一判断条件必不可少 //遇到小于基准值则停下 while (left < right && a[right] >= a[keyi]) {right--; } //遇到大于基准值则停下 while (left < right && a[left] <= a[keyi]) {left++; } //交换 Swap(&a[left], &a[right]); } Swap(&a[left], &a[keyi]); return left; }

时间复杂度
??时间复杂度:O(N log N)
挖坑法
算法图解
单趟动图如下：

如图可以看出:

1.先选出一个值存放在key中，通常为最左或最右边的值
2.定义L，R，(若key选自最左边，则R先走）
3.当R遇到小于key的值，将该值移动到坑(hole)中，并将该处变为新的坑(hole)
4.当L遇到大于key的值，将该值移动到坑(hole)中，并将该处变为新的坑(hole)
5.重复上述步骤3、4，当L和R相遇，停止移动，并将key移动到坑(hole) 中。至此，单趟结束。

参考代码
单趟代码如下：

int PartSort2(int* a, int left, int right) { // 所需正确移动的关键数 int key = a[left]; // 初始坑位 int hole = left; while (left < right) {// 右边，遇到小的则停止 while (left < right && a[right] >= key) {right--; } // 填坑，更换新的坑位置 a[hole] = a[right]; hole = right; // 左边，遇到大的则停止 while (left < right && a[left] <= key) {left++; } // 填坑，更换新的坑位置 a[hole] = a[left]; hole = left; } // 当左右相遇，即 key 的正确位置 a[hole] = key; return left; }

时间复杂度
??时间复杂度:O(N log N)
前后指针法
算法图解
单趟动图如下：

由图可知其步骤如下:
1.先选出一个值存放在key中，通常为最左或最右边的值
2.定义prev和cur, prev 指向待排序列起始位置，且cur= prev + 1
3.当cur指向的值小于key，先 ++prev ，再将prev所指向的值与cur所指向的值进行交换。如此重复至cur越界
4.此时，将key与prev所指向的值交换，可以得到，key左边值均比其小，key右边值均比其大。

参考代码
单趟代码如下：

int PartSort3(int* a, int left, int right) { int keyi = left; int cur = left + 1; int prev = left; while (cur <= right) {if (a[cur] <= a[keyi] && ++prev != cur) {Swap(&a[cur], &a[prev]); } cur++; } Swap(&a[keyi], &a[prev]); return prev; }

时间复杂度
??时间复杂度:O(N log N)
代码优化
??实际上，上述图片仅仅是理想状态下所实现。举个例子，倘若每次选择的key均是最大/小值，则上述区间被划分为分别包含 n - 1 个和 0 个元素的区间，故而时间复杂度O( N 2 N^2 N2).因此选择一个适中的key是必要的。在此给出三数取中法，如下：

??选择给定区间的左值，右值，以及中间元素的值，将次大的元素与区间首元素交换，再将key选定为新的首元素，从而保证key左右均有元素。

代码如下：

int GetMidIndex(int* a, int left, int right) { //防止溢出 int mid = left + (right - left) / 2; if (a[left] > a[right]) {if (a[mid] > a[left]) {return left; } else if (a[mid] > a[right]) {return mid; } else {return right; } } else {if (a[mid] > a[right]) {return right; } else if (a[mid] > a[left]) {return mid; } else {return left; } } }

优化后代码如下：

int PartSort1(int* a, int left, int right) { //得到中间值元素下标 int keyi = GetMidIndex(a, left, right); //与首元素交换 Swap(&a[left], &a[keyi]); keyi = left; while (left < right) {while (left < right && a[right] >= a[keyi]) {right--; } while (left < right && a[left] <= a[keyi]) {left++; } Swap(&a[left], &a[right]); } Swap(&a[left], &a[keyi]); return left; }

其他两种方法优化方式同上。
多趟代码

void QuickSort(int* a, int left, int right) { //递归条件 if (left >= right) {return; } // 中间值下标 //int key = PartSort1(a, left, right); //int key = PartSort2(a, left, right); int key = PartSort3(a, left, right); //递归左区间 QuickSort(a, left, key - 1); //递归右区间 QuickSort(a, key + 1, right); }

非递归 ??我们都知道，递归会开辟新的函数栈帧。因此将递归版转化为非递归版，需借用一个数据结构–栈不熟悉的可以参看一下我的这篇文章【数据结构】栈
??通过上述文章，我们可以发现，三种递归版本不过是单趟排序有些许差异，多趟排序仍一致且递归实现。因此我们可以将单趟函数封装起来，将递归转化为非递归。可以发现，递归实际上是将大区间分成许多小区间，将小区间有序化，则大区间亦有序。
算法思路
??

1.将待排区间的第一个和最后一个元素下标入栈。
2.进行一趟排序，得到返回的key的下标，则得到新的两段区间。将旧区间出栈，新区间入栈。
3.重复步骤2，直到栈为空。

参考代码

void QuickSortNonR(int* a, int left, int right) { assert(a); //借助栈来实现 //创建栈 Stack st; //初始化栈 StackInint(&st); //先入栈，否则无法进入循环 StackPush(&st, right); StackPush(&st, left); //当栈为空，则已排好序 while (!StachEmpty(&st)) {//获取栈顶元素，需注意顺序 int begin = StackTop(&st); StackPop(&st); int end = StackTop(&st); StackPop(&st); //取中间值 int mid = PartSort3(a, begin, end); //如果左区间范围大于1，进行入栈 if (begin < mid - 1) {StackPush(&st, mid - 1); StackPush(&st, begin); } //右区间同理 if (end > mid + 1) {StackPush(&st, mid + 1); StackPush(&st, end); } } StackDestroy(&st); //free() }

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

图二：

文章图片

算法分析

1.由图可以发现，我们需先将待排序列分成许多子序列，直至每个序列仅有1个元素，并开辟新的相同大小的数组
2.将子序列元素进行排序。因为每个序列分为新的1~2 个子序列，排完子序列后赋值给原数组，返回上一层，再进行新一轮排序。再返回上一轮，直至排序完成。
3.基于上述分析，可以发现，我们需先递归，再排序。且需要一个子函数来实现递归功能。

参考代码

void _MergeSort(int* a, int left, int right,int* tmp) { if (left >= right) return; //防止left + right溢出 int mid = left + (right - left) / 2; _MergeSort(a, left, mid, tmp); _MergeSort(a, mid + 1, right, tmp); //记录left初始位置 int index = left; //左区间 int begin1 = left; int end1 = mid; //右区间 int begin2 = mid + 1; int end2 = right; //将两组元素进行排序至临时数组中 while (begin1 <= end1 && begin2 <= end2) {if (a[begin1] < a[begin2]) tmp[left++] = a[begin1++]; else tmp[left++] = a[begin2++]; } while (begin1 <= end1) {tmp[left++] = a[begin1++]; } while (begin2 <= end2) {tmp[left++] = a[begin2++]; } //归并后，拷贝至原数组 for (int i = index; i <= right; i++) {a[i] = tmp[i]; } }

void MergeSort(int* a, int n) { int* tmp = (int*)malloc(n * sizeof(int)); //避免malloc失败 if (tmp == NULL) {printf("malloc failed\n"); exit(-1); } _MergeSort(a, 0, n - 1, tmp); free(tmp); tmp = NULL; }

时间复杂度
??时间复杂度:O( N 2 N^2 N2) ，归并的缺点在于需要O(N) 的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
非递归算法分析
??通过上述内容，我们可以发现，每次递归先将待排序列分为多组，每组有左右两个区间，直至每个区间仅有一个元素后，再排序。由此我们可以先将待排序列分为多组，每个区间仅一个元素，每一趟将两个区间进行一次归并，再归并下一组。下一趟排序时，新区间又是由上一趟两个区间元素构成。基于此，我们有以下思路:

1.每一趟进行多组排序
2.每进行一趟排序，重新分组

如图:

文章图片

??不过，有以下三种情况值得注意：
情况一:右区间不存在

文章图片

情况二:左区间不完整

文章图片

情况三:右区间不完整

文章图片

参考代码

void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(n * sizeof(int)); //避免malloc失败 if (tmp == NULL) {printf("malloc failed\n"); exit(-1); } //初始组内元素个数为1 int GroupNum = 1; while (GroupNum < n) {for (int i = 0; i < n; i += 2 * GroupNum) {//左右区间 int begin1 = i; int end1 = i + GroupNum - 1; int begin2 = i + GroupNum; int end2 = i + 2 * GroupNum - 1; //记录区间初始位置 int index = begin1; //end2越界，需要修正后归并 if (end2 >= n) {end2 = n - 1; } //[begin2,end2] 不存在, 修正为一个不存在的区间 if (begin2 >= n) {begin2 = n + 1; end2 = n; } //end1越界,修正一下 if (end1 >= n) {end1 = n - 1; }//将两组元素进行排序至临时数组中 while (begin1 <= end1 && begin2 <= end2) {if (a[begin1] < a[begin2]) tmp[index++] = a[begin1++]; else tmp[index++] = a[begin2++]; } while (begin1 <= end1) {tmp[index++] = a[begin1++]; } while (begin2 <= end2) {tmp[index++] = a[begin2++]; } } //归并后，拷贝至原数组 for (int i = 0; i < n - 1; i++) {a[i] = tmp[i]; } GroupNum *= 2; } free(tmp); }

八、计数排序 ??计数排序是一种非基于比较的排序算法，我们之前介绍的各种排序算法几乎都是基于元素之间的比较来进行排序的。
算法思想
??计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
??动图演示

算法分析

??计数排序，顾名思义，该算法不是通过比较数据的大小来进行排序的，而是通过统计待排序列中元素出现的次数，然后通过统计的结果将序列回收到原来的序列中。步骤如下：

1.首先，准备一个「计数器数组」，通过一次「遍历」，找出最大值「 max」。
2.开辟出一个大小为「 max + 1」的数组。
3.再次「遍历」原数组，统计元素每个元素出现次数。每个元素值与新数组下标「一一对应」。例如，数字「5」对应新数组下标为 5 的地址。每出现一次「5」，则新数组下标为 5 处的值++.
4. 「遍历」新数组，嵌套两层循环。外层新数组从头到尾「遍历」，内层进行「原数组赋值」。如果新数组遍历处值为 0 ，则无需赋值。直至遍历完。

??有个问题值得思考：假设原数组为{1000,1002,1005,1003,1008,1004}.那么开辟 1008 + 1个元素大小的数组，势必造成前1000个空间浪费。此外,倘若数组为 {-1,-2,-3},还会出现数组越界的情况。因此，我们必须考虑上述两种情况。

??在此，我们再来优化一下。通过一次「遍历」，找出最大值「 max」和最小值「 min」.则须开辟新数组大小为「 max - min + 1」.则对应关系相应变化。值为 i 的元素，对应新数组下标为「 i - min」，下标为 j 的新数组下标，对应值为「 j + min」.

参考代码
??基于上述分析，有如下代码：

void CountSort(int* a, int n) { // 定义最大/小值 int max = a[0]; int min = a[0]; //找出最大/小值 for (int i = 1; i < n; i++) {if (a[i] > max) max = a[i]; if (a[i] < min) min = a[i]; } //开辟新数组，同时赋值为 0 int* tmp = (int*)calloc(max - min + 1, sizeof(int)); if (tmp == NULL) {printf("malloc failed\n"); exit(-1); } // 遍历原数组，统计个数 for (int j = 0; j < n; j++) {tmp[a[j] - min]++; } // 遍历新数组 for (int i = 0,j = 0; j < max - min + 1; j++) {//进行原数组重新赋值 while (tmp[j]--) {a[i++] = j + min; } } }

时间复杂度
??我们看到嵌套循环，第一反应就是这个算法的时间复杂度:O( N 2 N^2 N2) ?但事实上并非如此。细想一下，两层循环，加起来不过是原数组重新赋值，故正确的时间复杂度:O(N + range)??
??此外，计数排序也有它的局限性。计数排序只适合「数据较为集中」，且数据均为「整形」的序列。若数据分散，则会造成数据浪费的情况。
总结 ??完整代码链接八大排序

排序算法	平均情况	最好情况	最坏情况	稳定性
冒泡排序	O( N 2 N^2 N2)	O(N)	O( N 2 N^2 N2)	稳定
简单选择排序	O( N 2 N^2 N2)	O( N 2 N^2 N2)	O( N 2 N^2 N2)	不稳定
直接插入排序	O( N 2 N^2 N2)	O(N)	O( N 2 N^2 N2)	稳定
希尔排序	O(N log N) ~ O( N 2 N^2 N2)	O( N 1.3 N^{1.3} N1.3)	O( N 2 N^2 N2)	不稳定
堆排序	O(N log N)	O(N log N)	O(N log N)	不稳定
归并排序	O(N log N)	O(N log N)	O(N log N)	稳定
快速排序	O(N log N)	O(N log N)	O( N 2 N^2 N2)	不稳定