c语言数据结构——八大排序算法实现

八大排序算法

这篇文章是c语言数据结构章节的最后一个部分——排序算法

在我们的日常生活中，排序是无处不在的，比如打开一个购物网站，会发现网站可能会对其上架的商品有多种排序方式：

随便输入一个商品，平台对其都有对应的排序功能如销量、价格等。再到中高考成绩的排序决定考生排位，又或是学校内成绩的排序，最终都离不开排序。

所以今天这篇文章将重点讲解八大排序算法的思想以及实现。因为重点是思想以及功能能够成功实现，所以排序的对象选择整形数组。最重要的是学习背后的思想。其他类型的数据排序只需要稍微改动一些逻辑即可。

排序算法种类

八大排序算法正好两两对应一组：

其中有两种在之前已经接触过了，即堆排序和冒泡排序。所以对应的篇幅会少一些。

接下来，我们将对这几个算法进行深度地剖析及实现。请注意，在这篇文章中，所有的排序算法都已升序进行讲解。

选择排序类

如其名，该类排序最重要的二字就是"选择"。即每一次排序的时候都会在给定数组中选取数据，将选定好的数据放在指定的位置。下面让我们来看看是怎么样操作的。

堆排序

堆排序在之前的堆的实现文章中就已经讲过了，在这里只进行简单的回顾。

感兴趣的读者可以翻阅这篇文章：二叉树概念和堆的实现应用

算法思路

堆本质上是完全二叉树，即逻辑结构是二叉树。但是真正存储的时候，为了效率，其底层选择的是使用数组进行存储。

为了排一个升序的数组，那么应当建大堆。这是之前的文章讲过的。

对于建堆，选择使用向下调整算法建堆的时间复杂度为O(N)，代码如下所示：

void AdjustDown(HPDataType* a, int Heapsize, int parent) {//默认调整小堆//向下调整小堆的逻辑：(但是得保证当前已经是一个小堆)//从传入的parent位置开始 找到parent左右孩子较小的那个  (注意：可能会没有左右孩子)//如果大于较小的那个孩子 就交换 反之退出循环 int Parent = parent;while ((Parent * 2 + 1) < Heapsize) { //如果不是叶子节点就向下调整//假设法找到左右孩子较小的那个//如果能进入循环 说明有左孩子 但不一定有右孩子int Child = Parent * 2 + 1;if (Child + 1 < Heapsize && a[Child] < a[Child + 1])  Child = Child + 1; //调为大堆要改第二个符号 第一个不能改if (a[Parent] < a[Child]) {//想要调整为大堆就改符号 找左右孩子大的 swap(&a[Parent], &a[Child]);Parent = Child;}else break;}
}

这段代码已经修改为调整大堆的版本。如果想要改为调整小堆的请按注释修改！

既然已经建立大堆了，就可以模仿出堆过程。将最大的数(堆顶数据)出堆，其实就是存储在数组的最后一个位置。但是后续会调整堆的大小减小1，所以就可以近似看成出堆操作。

最后代码的实现如下：

void HeapSort(int* a, int n) {//向下调整建堆/*int begin = (n - 1 - 1) / 2;while (begin >= 0) {AdjustDown(a, n, begin);begin--;}*///当然可以使用for循环for (int i = (n - 1 - 1) / 2; i >= 0; i--) {AdjustDown(a, n, i);}//模仿出堆过程while (n > 0) {int end = n - 1;swap(&a[0], &a[end]);AdjustDown(a, end, 0);n--;}
}

时间复杂度和空间复杂度

在上述提及的那篇文章中介绍过：
向下调整算法建堆的时间复杂度为O(N)，出堆过程时间复杂度为O(N * LogN)，所以最后该算法属于是N * LogN级别，所以时间复杂度为O(N * LogN)。

由于该算法没有开辟额外的空间堆数组进行处理，所以空间复杂度为O(1)。
由于已经讲过，便不再赘述。

选择排序

算法思路

这个排序十分简单，即给定一个数组，每次都找到最小值位置，然后与第一个位置的元素交换位置。然后让后面部分的数组执行上述操作。

如下图例子所示：

对于上面这个思路的代码实现：

void SelectSort(int* a, int n) {int begin = 0;for(int i = 0; i < n - 1; i++){int min = i;for(int j = i + 1; j < n; j++){if(a[j] < a[min]) min = j; }swap(&a[min],&a[i]);//交换操作}
}

很容易看见，选择排序算法的本质就是暴力查找数据。但是为了排序的效率，能不能再对这个部分的算法进行一定程度的优化呢？

答案是可以的

算法优化

既然是暴力查找，那就可以每一次暴力查找的时候同时找到当前数组中最大和最小的，然后放在数组的头尾，然后不断地查找下去直到无法查找即可。

这样子相比于上面的暴力查找，虽然方法类似，但是效率高了很多，所需要的时间可以近似看成上面那个算法的一半。

代码实现：

void SelectSort(int* a, int n) {//begin从0往后走 end从n-1往前走//每一次都要找到最大和最小的，最小的放begin位置，最大的放end位置//然后begin++   end--//直到begin>=end就出这个循环int begin = 0, end = n - 1;while (begin < end) {int maxi = begin, mini = begin;//最大数和最小数的下标for (int i = begin + 1; i <= end; i++) {if (a[i] > a[maxi]) {maxi = i;}if (a[i] < a[mini]) {mini = i;}}//交换操作if (begin == maxi && end == mini) swap(&a[begin], &a[end]);else if (begin == maxi) {swap(&a[end], &a[maxi]);swap(&a[begin], &a[mini]);}else {swap(&a[begin], &a[mini]);  swap(&a[end], &a[maxi]);}begin++;end--;}
}

但是为什么后续的交换操作如此麻烦呢？

这是因为当一次性找两个数据的时候，有如下几种可能：
1.最大的数字的坐标与寻找数组段的第一个位置元素重合，最小的数字坐标与数组段最后一个位置元素重合
如果此时先swap(&a[begin], &a[mini]);，再swap(&a[end], &a[maxi]);，就会导致数组实际上是没有交换。所以要特殊处理

2.最大的数字的坐标与寻找数组段的第一个位置元素重合，最小的数字坐标与数组段最后一个位置元素不重合
这一种情况下，如果先swap(&a[begin], &a[mini]);，会导致maxi的位置的值发生改变，指向的是被换后的最小值。那么再执行swap(&a[end], &a[maxi]);的时候，就无法将最大的数放在数组的尾部了，所以也要特殊处理。

3.最大的数字的坐标与寻找数组段的第一个位置元素不重合，最小的数字坐标与数组段最后一个位置元素重合及其余情况
第三种情况的前面半个部分和第2条正好相反，那就与上述操作相反即可。对于其余情况，无论先执行哪一条语句都是正确的，所以不用另外再进行判断。

当然，可以再特殊情况下通过调整maxi和mini的位置。但是在这里为了确保正确，选择逻辑判断。感兴趣的读者可以尝试使用调整坐标方法。

时间复杂度和空间复杂度

无论是算法优化前又或是优化后，这个算法总是会出现两层循环嵌套的逻辑。且每一层循环的次数都与数组长度N有关。所以时间复杂度是很明显的O(N^2)，由于比较简单，不进行计算。

没有开辟新的数组对原数组进行处理，所以该算法的时间复杂度是O(1)。

插入排序类

本部分算法的思想就在于”插入“二字。

插入排序

算法思路

一个数组可以看作成已排序区和未排序区。然后从未排序区的第一个数据(记作a)开始，从已排序区的最后一个元素开始向前比较。直到找到第一个小于等于a的数b的时候，就将a插入在b后面的位置。(如果已排序区的数字全部都比a小，那就将a放在第一个位置)

直到已排序区为整个数组的时候，就不用再执行插入算法了。

如图所示：

代码实现非常简单：

void InsertSort(int* a, int n) {//思路：把前面的部分当作已排序区(升序) //然后让已排序区的下一个位置的元素跟已排序区内比较//直到找到一个小于这个元素的位置，在这个位置后面插入该元素for (int i = 0; i < n - 1; i++) {int end = i; int tmp = a[end + 1]; while (end >= 0) { if (a[end] > tmp) { a[end + 1] = a[end]; end--; }else break;}a[end + 1] = tmp; }
}

比tmp小的数会往后挪，直到找到插入位置放入tmp。

注意：这里插入tmp数据尽量不要写在第二层循环内。因为插入排序算法的核心思想就是与前一个位置的数据比较。但是当tmp走到数组第一个位置比较的时候，前面是没有数据的。会退出循环。如果在第二层循环内写插入tmp操作，那么对于刚刚讲到的这个情况需要进行特殊判断。但是写在当前代码显示位置就可以将所有插入情况都满足。故建议写在当前展示的位置。

时间复杂度和空间复杂度

假设最坏的情况下：每一个数字往前插入都要将已排序区的数字全部比较一遍，那么语句执行的次数是一个很明显的等差数列，时间复杂度为O(N^2)。

空间复杂度为O(1)，因为没有额外开辟新的空间。

希尔排序

对于刚刚写的插入排序，我们发现，当数组为倒序的时候，每个数据往前插入的时候，都要与已排序区中的所有元素进行排序。那么效率会退化。当数组中元素较多的时候，那么排序的效率并不高。而当算法是升序的时候，每个元素只要比较一遍就可以不用再执行该算法。

也就是说:对于插入排序来讲，数组越接近升序，那排序效率就越高。

针对这个特点，就提出了希尔排序这个算法。这个算法本质上就是对插入排序算法的优化。

算法思路

希尔排序是这样操作的，既然数组越接近升序插入排序效率越高，那就可以先对数组进行若干次预排序，使其较为接近升序。然后再执行上面实现的插入排序操作，这样效率就高得多。

希尔排序会有一些抽象：
它先规定了一个范围叫gap，需要将这个数组分为gap组。

为了方便讲述，我们先假定gap = 3，数组中有十个元素进行讲解：

如图所示操作，我们会发现所有的数据都被分到了分配的gap组上，且没有重复。

现在这个数组被分为了红、绿、紫三组。希尔排序就是对这红、绿、紫三组指向的元素分别进行预排序。使用的算法就是上面的插入排序算法。只不过此时相邻的数据举例变为了gap = 3，而不是之前的1。

连续对三组预排序的代码编写很困难，不妨先写对红色的预排序，然后再来推广：

//对红色排
for (int end = 0; end < n - gap; end += gap) {int tmp = a[end + gap];//插入排序while (end >= 0) { if (tmp < a[end]) {  a[end + gap] = a[end]; end -= gap; }else break;}a[end + gap] = tmp;
}

在这里有几个注意的点：
1.此时相邻的元素距离变为gap，所以下一个元素的位置是end + gap。
2.截止条件有变，在前一个部分的插入排序算法中，当end走到数组的最后一个位置就得停下。也就是说，当end走到数组倒数第二个元素位置，排序完后就应该停止了。

所以对于红色数组：

倒数第二个元素是4，所以走到4排序完后就应该停下。而end一次会往后走gap个位置，所以要限制end的位置。我们发现正好倒数第二个元素的下一个位置的坐标是n - gap与上面插入排序算法是对应的。(这里有伏笔)

所以就让end的位置限制在n - gap前即可。

而对于绿色和紫色的这两组，本质上的逻辑和上面的代码其实是一样的，只不过是end得其实位置不同罢了。所以我们再套一层循环就好了：

int gap = 3;
for (int j = 0; j < gap; j++) {for (int end = j; end < n - gap; end += gap) {int tmp = a[end + gap];//插入排序while (end >= 0) { if (tmp < a[end]) {  a[end + gap] = a[end]; end -= gap; }else break;}a[end + gap] = tmp;}
}

这样子就成功的对三组数据进行预排序了。然后我们推测，对于gap的取值，数组的长度不同，这个原理应当都成立。实际上确实如此。

然后我们可以对比一下之前写的插入排序算法，发现就是将1换成end了。但是发现外部套了一个循环，还是不太像，能不能对其进行改进，使其更像呢？

答案是可以的：

int gap = 3;
for (int i = 0; i < n - gap; i++) {int end = i; int tmp = a[end + gap]; while (end >= 0) {if (tmp < a[end]) {a[end + gap] = a[end];end -= gap;}else break;}a[end + gap] = tmp;
}

我们进行一点小改进。这个和上面的最大区别就是：
上面的是每一组进行单独排序。一组排完了才到下一组
而下面的这段代码则是一起进行，从数组第一个元素开始，将此时指向的位置记为已排序区的最后一个元素，然后执行对应组的插入排序操作。

虽然减少一层循环，但是并没有效率的提升，因为无论是同时或是分组，都需要进行这么多次的判断以及插入操作。

最后还有一个问题，就是gap如何确定？
这个问题其实并没有严格的要求，但是有一个奇妙的规律：

如果gap越大，那么大的数会越快放在后面，但整个数组不会太接近升序。
如果gao越小，那么大的数会越慢放在后面，但整个数组会比较接近升序。

重点：如果gap = 1的时候，正好就是插入排序。

虽然对gap的要求并没有明显提及，但是最好的办法就是让gap动起来，直到最后一次变为1执行插入排序算法后，就排序成功，所以最终的希尔排序算法应该是：

void ShellSort(int* a, int n) {//很多教科书上写的是两层循环(多组同时进行)  所以这里采用这种写法//但是实际上是没有效率提升的。int gap = n;while (gap > 1) {gap = gap / 3 + 1;//保证最后一次循环操作时gap为1for (int i = 0; i < n - gap; i++) {int end = i; int tmp = a[end + gap]; while (end >= 0) {if (tmp < a[end]) {a[end + gap] = a[end];end -= gap;}else break;}a[end + gap] = tmp;}}
}

gap怎么动也是有讲究的。一开始让其等于数组的长度。一开始希尔这个科学家是建议每次除以2。但是有相关研究证明了每次是不太好的，除以3是比较合理的。这是经验得到的，直接记住就好。

注意：为了确保gap最后一次为1，处理gap的时候应该再最后加上“+1”，这样一定能确保最后一次执行该循环的时候，gap为1，对应的就是插入排序算法。

以上就是希尔排序算法实现的过程，需要多加理解和记忆。

时间复杂度和空间复杂度

在这里先给出结论，希尔排序的时间复杂度大致是O(N^1.3)，这看着十分的奇怪。这是因为希尔排序的时间复杂度计算是比较困难的。当前以大部分的数学水平是无法计算的。在这里只讲一下其计算的困难之处：

假设第一次gap = n/3，即将数组分为n/3组，每一组的个数n/(n/3) = 3个。对于一个大小为x的数组进行插入排序，最坏情况就是倒序的时候为1+2+3+4+…+x-2+x-1 = 1/2 * x * (x-1)。所以第一次预排的语句执行次数(即消耗) = 每组消耗 * 组数 = 3(将x=3代入上述公式) * n/3 = n

对于第二次，gap再除以3，应该是n/9，每组个数为9个。假设还是最坏情况，那么语句执行次数是：36(x = 9代入) * n/9 = 4n。

再下一次gap应该就是n/27了。但是由于我们一开始让gap = n/3，这是比较大的分组间距。在之前提到过，gap越大，那么预排序后大的数会越快跑到数组后面。而因为我们将gap不断调整，所以经过一定次数的预排序后，这个数组再来分组预排序就很难再出现最坏情况，而具体内部是什么情况以当前的数学水平大部分人是无法证明的。

但我们所知道的是，最后一次排序时gap = 1，这就相当于是插入排序算法。由于这个数组之前进行了若干次的预排序，所以是比较接近升序的。插入排序在面对升序的时候时间复杂度是O(N)，效率高。所以对于最后一次gap = 1的排序，我们可近似看作语句执行次数为n。

最后我们大致得到希尔排序算法的消耗与gap的关系：

由于中间部分的不确定性，所以希尔排序的时间复杂度计算比较困难。但有人大致证明了这个时间复杂度为O(N^1.3)，那就记住这个结论即可。

空间复杂度仍是O(1)，因为没有开辟额外的数组。

非比较排序类

这个部分的排序方式不需要进行两两比较后再来执行一些操作。因为不进行比较，最大的特点就是需要另外开辟空间来操作数据。

计数排序

这个也可以叫做统计排序，即统计一个数字出现的次数。

比如现有数组{1,5,3,4,5,3,6,9,1,2}，为了统计次数，开辟一个数组count，大小为10，并将count数组中所有元素复赋值为0.此时对应的下标正好是0~9。然后通过遍历原数组，将数字出现个数在对应下标处记录。

此时count数组中记录下了每个元素出现的次数，这个元素就是count数组的下标。

然后再根据这个特性一次将元素按顺序输出即可：{1,1,2,3,3,4,5,5,6,9}，这就完成排序。

但是现在有一个问题：开辟的count数组的大小是待排序数组中最大值 + 1，这样子很容易造成空间浪费。如给定一个数组：{44,46,48,88,68,44,46,100}，此时按照上面的方法，会发现要开辟101个空间，但是真正使用的只有3个数据，这应该如何操作呢？

这个时候，我们就可以减少开辟数组的数量，比如对于上述提到的数组：{44,46,48,88,68,44,46,100}

最大值是100，最小值是44，我们就可以开辟一个大小为range的数组，其中range = max - min + 1。在之前的那个思路是直接映射，遍历数组是多少，count数组中下标为该数字的位置的元素就+1.而我们现在改为相对的映射，最小值存储在下标为0的位置，那么最大的值得数据就是在range - 1的位置。

此时来研究一下相对映射的关系：
还是这个数组：{44,46,48,88,68,44,46,100}
我们要开辟一个数组，大小为100 - 44 + 1 = 57
最小的数min = 44，存储在下标为0的位置，即44 - min
最大的数max = 100，存储在下标56的位置，即100 - min
所以我们就发现，相对映射放到count数组中的坐标就是本身减去min(最小值)。

所以我们可以展示代码了：

void CountSort(int* a, int n) {int max = a[0], min = a[0];//找出最大最小值for (int i = 1; i < n; i++) {if (a[i] > max) max = a[i];if (a[i] < min) min = a[i];}int range = max - min + 1;int* count = (int*)calloc(range, sizeof(int));if (!count) {perror("calloc");exit(-1);}//统计 相对映射for (int i = 0; i < n; i++) {count[a[i] - min]++;}//将count中已排序数据输入回去int j = 0;for (int i = 0; i < range; i++) {while (count[i]--) {a[j++] = i + min;}}free(count);count = NULL;
}

值得注意的是，当根据count数组中的统计个数输出数据到原数组的时候，由于原来是相对映射过来的，那输出的时候就需要进行相应的映射。

还有一个重点就是，经过相对映射改进的方法是可以对负数进行排序的。原来的方法因为数组下标没有负数。而经过相对映射，只需要把负数中的最小值放在下标为0的位置，其余的数据只需要根据相对映射关系进行统计就可以了。

但是这个算法也是有缺点的，就是无法比较浮点数。因为下标没有浮点数。

时间复杂度和空间复杂度

时间复杂度很好计算，对于统计操作部分，只需要执行n次即可，时间复杂度为O(N)。对于将数据覆盖回数组当中，由于count数组只有range个位置，且每个位置统计的次数是比较确定的，所以时间复杂度为O(range)，所以总的时间复杂度是O(N + range)，这是线性的时间复杂度。相比于前面讲到的一些算法，快得多。

但是也是有缺陷的，不能排序浮点数，因为需要另开辟空间的缘故，空间复杂度为O(N)，当数据较多的时候对存储的要求较大。同时这个排序算法比较适合整形数据较多较为集中的情况。

归并排序

归并算法的思想就是将几个有序的 子数组合并到一个新的数组，使之有序

算法思路

假设当前有这么一个数组，对于当前的数组想让其有序，我们可以先把这个数组分成两部分(尽可能等分)，如果左右两段都是有序的，那我们只需要开辟一个新的数组，依次将小的数据插入到新的数组后排好序，再赋值回给原来的数组。

但是左右子区间可能并不是有序的，怎么办呢？很简单，直接执行上述的操作不就好了吗。让子区间的左右子区间有序就好了。我们发现，这不就是“递推公式”吗？那我们可以直接使用递归来进行实现，现在只需要找到递归的停止条件就好了。

当区间内只剩下一个或者没有数据的时候，就认定其有序就可以了，那此时就不用再对其拆分成左右两个子区间了。

递归实现

void _MergeSort(int* a, int left, int right, int* tmp) {//递归需要有终止条件//当区间只有一个元素或者没有元素 停止if (left >= right) return;int mid = (left + right) / 2;//假设左右区间有序 即可执行归并//[left   mid]  [mid + 1  right]//不能划分成[left   mid - 1]  [mid  right] 会出现问题 这一点到博客上说明////刚进来这个函数肯定无法保证左右区间有序，所以递归下去_MergeSort(a, left, mid, tmp);_MergeSort(a, mid + 1, right, tmp);//数组归并int begin1 = left, end1 = mid; int begin2 = mid + 1, end2 = right; //合并两个有序数组到新数组很简单，尾插到新数组即可int i = begin1; while (begin1 <= end1 && begin2 <= end2) {if (a[begin1] < a[begin2]) {tmp[i++] = a[begin1++];}else tmp[i++] = a[begin2++];}while (begin1 <= end1) {tmp[i++] = a[begin1++];}while (begin2 <= end2) {tmp[i++] = a[begin2++];}//将tmp数组中的内容复制回去a数组中memcpy(a + left, tmp + left, (right - left + 1) * sizeof(int));
}void MergeSort(int* a, int left, int right) {//归并排序就是把数组等分成两个区间，假设左右两个区间均有序 然后新开一个数组把两个数组有序合并后的结果插入数组中//然后将归并好的数组复制回原来数组if (left >= right) return;int sz = right - left + 1;int* tmp = (int*)malloc(sizeof(int) * sz);if (!tmp) {perror("malloc");exit(-1);}//这个函数新开一个空间传入子函数//使用子函数去操作后续的归并会方便得多，就不用每次归并的时候都需要开一个数组_MergeSort(a, left, right, tmp);free(tmp);tmp = NULL;
}

我们在MergeSort函数中开辟一个数组，传入子函数_MergeSort进行操作。按照归并算法的思想，是需要开辟一个数组来处理操作数据的。但是由于递归过程中开辟数组是很难把控的，所以选择外部开辟，传入子函数，子函数只需要对整个数组操作即可。

合并两个有序数组的算法是很简单的，在这里就不赘述了。

对于递归的过程还需要进行一些说明，因为尽可能需要二等分区间，所以要取中间位置坐标mid。但是左右区间如何分是有要求的：
必须是[left mid] [mid+1 right]，如果分成了[left mid-1] [mid right]是回出现问题的。
如下图所示：

当出现区间左坐标为偶数，右坐标为奇数的时候，就会引发栈溢出的问题。

对于递归的截止条件，当左右坐标相同的时候即只有一个元素，若按照正确方法二分区间，那么当左坐标大于右坐标的时候，就是区间不存咋，也就是没有元素。

所以递归的停止条件是left >= right，然后退回来执行归并。

最后要注意的就是需要将归并好的数组赋值回原数组，为了方便，选择使用库函数memcpy进行赋值。但需要注意的是：
操作归并算法的时候起点是当前子区间的左坐标，也就睡每次递归的left值，所以赋值的时候需要正确计算当前左右子区间归并元素的个数，并且还要对a和tmp两个数组选择正确的起点进行赋值操作，否则会导致排序失败。

非递归实现

使用递归的方法总是会担心是否有栈溢出的风险，特别是当数据量较大的时候。所以我们能否考虑使用非递归的方式呢？

答案是可以的。如果我们使用栈来模拟这个递归是否可行呢？一起来看看：
对于一个数组，将其左右区间坐标入栈，出栈后再先后地将这个区间的右区间和左区间入栈，乍一看，这好像可行啊。但是最要命的问题来了，左右区间入栈后再出栈，那要怎么对其排序呢？就得多开辟一个栈，将出栈的左右区间进行接收后再排序。这很复杂。所以我们考虑换一个思路。

因为归并算法是不断地将区间二等分并将左右子区间进行归并排序。来设想一个最完美的场景。如果数组的元素个数正好是2的整数次幂呢？如1，2，4，8，16等。

那就可以先一个一个排序，然后再两个两个排序，四个四个排序，最后正好完成排序。对于不是这个情况的，我们先不管，我们先处理刚刚这种情况，然后具体的问题再来具体分析就好。

每次都是从头开始分区间：
1.区间的个数从1开始，每相邻的两个区间进行归并后，插入到tmp数组对应位置，然后赋值回原数组对应为支持
2.然后区间的数量变为原来的2倍，然后执行上述操作
直到gap的值为数组长度的一半时，进行最后一次归并算法

//先假设数组元素个数是2的整数次幂个
int gap = 1;//每组元素的个数
while (gap < n) {for (int i = 0; i < sz; i = i + 2 * gap) {//sz为数组元素个数int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;//[begin1 end1]  [begin2 end2]正好是归并的两个区间的起始节点//合并两个有序数组到新数组很简单，尾插到新数组即可int j = begin1;int tmpnum = end2 - begin1 + 1;while (begin1 <= end1 && begin2 <= end2) {if (a[begin1] < a[begin2]) {tmp[j++] = a[begin1++];}else tmp[j++] = a[begin2++];}while (begin1 <= end1) {tmp[j++] = a[begin1++];}while (begin2 <= end2) {tmp[j++] = a[begin2++];}memcpy(a + i, tmp + i, tmpnum * sizeof(int));}
}

但是这种情况只能针对数组大小为2的整数次幂的情况，那如果个数不是整数次幂怎么办呢？来分析一下：

如果不是2的整数次幂的情况下，那么像上面那样分组是会出现坐标越界的。

比如现在有十个数据，每四个分一组前两组是没有问题的。但是第三组会出现区间坐标越界。
所以我们可以分析一下如何进行这些越界情况的处理：

首先知道，begin1和end1、begin2和end2正好指向的是要归并的两组数据的首尾坐标。

根据循环过程分析，begin1一定是不会越界的，所以当对两组进行归并的时候，会出现以下三种情况：
1.end1 begin2 end2越界
2.begin2 end2越界
3.end2越界
我们对这三种情况分别分析，当归并的两组出现了第一种情况和第二种情况，即第二个数组的整个空间都越界，就是不存在的，那就不需要进行此次的归并了。由于我们的归并是从头至尾进行归并的，第二个区间不存在的情况下一定是出现在当前最后一次子区间归并的过程中。无论end1是否越界，我们都可以先不管，因为第二个区间根本不存在，没办法归并，自然就不用处理end1越界时的问题，如图所示：

由于第二个子区间完全越界，所以没办法归并，直接跳出当前循环。哪怕时end1也越界(end1当前位置无元素)，但是由于第二个空间完全不存在，所以不用进行处理也可以。直接等待gap改变后重新分配区间的时候再来判断是否需要调整。

但是只有end2越界的时候，也就是说此时的两组归并子区间只不过是数据个数不一样，第二个区间的尾坐标只需要进行以下调整就好，如下图所示：

此时只需要将end2调整到原来数组中最后一个位置坐标即可。

所以最后我们来改动最后版本的代码：

void MergeSortNonRecursion(int* a, int left, int right) {int sz = right - left + 1;int* tmp = (int*)malloc(sizeof(int) * sz);if (!tmp) {perror("malloc");exit(-1);}int gap = 1;//归并时，每一组的个数while (gap < sz) {//先假设数组元素个数是2的整数次幂个for (int i = 0; i < sz; i = i + 2 * gap) { int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; //前两种begin2越界，那就不需要归并了//只有end2越界，修正到数组最后一个位置即可if (begin2 >= sz) break;if (end2 >= sz) end2 = sz - 1;//合并两个有序数组到新数组很简单，尾插到新数组即可int j = begin1;int tmpnum = end2 - begin1 + 1;//当前需要归并的两个数组的元素个数while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[j++] = a[begin1++]; }else tmp[j++] = a[begin2++];}while (begin1 <= end1) {tmp[j++] = a[begin1++];}while (begin2 <= end2) {tmp[j++] = a[begin2++];}memcpy(a + i, tmp + i, tmpnum * sizeof(int));}gap *= 2;}free(tmp);tmp = NULL;
}

还需要再注意一下的是，最好就是两两归并的时候就将tmp中的对应的数据赋值回原数组a中，如果要全部一起来赋值的话会出现一些问题：

比如当第二个归并区间不存在的时候，再来将数据赋值回原数组，就得判断载之前一共归并了多少个数据。否则可能会把tmp中的随机值赋值回给原数组中，导致原本没有参与归并排序的部分数据缺失。这是很容易出错的。所以不妨每归并一次就赋值回去一次。

时间复杂度和空间复杂度

时间复杂度的计算还是比较方便的，我们假设最坏的情况下，数据为2的整数次幂个。那么分的区间次数大致为Log₂N：

每一层归并的次数为N，最后总体次数为N * Log₂N，故时间复杂度为O(N * LogN)
对于非递归其实并没有效率的提升，其本质逻辑和递归类似，所以时间复杂度一样。

但是递归和非递归的空间复杂度不一样。非递归版本的只需要开一个大小为N的数组即可，空间复杂度为O(N)，但是对于递归的部分，不仅要额外开辟大小为N的数组，同时递归回开辟函数栈帧，函数栈帧也是额外开的空间，也是要计算到的。每一次递归调用就要开一次栈帧，空间复杂度大约为O(LogN)，因为深度为LogN。

可能会有人好奇，开辟栈帧的复杂度应该是O(2^N)啊，因为每一次函数内都又两个递归调用。这个时候就得提及一下栈帧开辟的原则，当函数栈帧调用结束后，会马上销毁。也就是说，某个区间下，左区间调用开辟完后，栈帧销毁。但是右区间又要开辟栈帧，为了节省空间，其新开的栈帧其实就是原来销毁的栈帧。所以一个区间的左右子区间用的其实是同一块栈帧空间。所以最后的空间复杂度是LogN的2倍，最后空间复杂度为O(LogN)

所以递归最后的时间复杂度为N + LogN，其实还是线性量级O(N)，但是和非递归还是有区别的

交换排序类

这个部分将对最后一个板块的排序算法进行讲解，即交换类。最重要的就是交换思想。

冒泡排序

这个排序算法很简单，初学c语言的很多学者都会接触到，所以就简单带过了。

冒泡排序最重要的特征就是通过交换将最大的数据向后调整，其已排序区在数组末端。对于一个n个元素的数组，需要进行n-1趟冒泡排序：

void BubbleSort(int* a, int n) {//冒泡排序的思路就是，把大的数往后挪//n个数走n - 1趟for (int i = 1; i <= n - 1; i++) {//冒泡排序的趟数int flag = 1;//假设每一次冒泡都有序 for (int j = 0; j <= n - 1 - i; j++) {//第一趟走过倒数第二个节点(下标n - 1 - 1 )就停止冒泡//第二趟走过倒数第三个节点(下标n - 1 - 2 )//第i趟走过 (下标n - 1 - i )if (a[j] > a[j + 1]) {swap(&(a[j]), &(a[j + 1]));flag = 0;//一旦执行过一次交换操作后，就说明原本的状态是无序的，需要进行下一趟的冒泡}}if (flag) break;}
}

这里还对算法进行了一些优化，即每次冒泡排序操作前，先假定右序。如果已经是有序的，那flag的值是不会被改变的，那就根据这个来判断是否还需要继续进行冒泡排序。

时间复杂度和空间复杂度

时间复杂度很简单，这是标准的等差数列计算，所以时间复杂度为O(N^2)。
空间复杂度O(1)，因为没有额外的开辟新的空间。

快速排序

快速排序是本篇文章中最重要的一个部分，将详细的讲解其原理及其如何优化的过程，最后进行实现。

三种单趟排序思路

快速排序的思想其实就是单趟排序后，分为两个区间不断执行单趟排序，直到无法再进行拆分
所以快速排序也是可以使用递归进行是是西安的。每一次的递归就是单趟排序过程。现在我们来讲解一下如何进行单趟排序。

单趟排序有三种实现方法：
1.Hoare提出的经典方法
2.前后指针法
3.挖坑法

其中第一种方法是最开始提出来的也是最经典的。

先对第一种方法进行讲解：

以数组第一个位置为轴，定义begin从轴开始从前往后走，end从最后一个数字往前走。在begin与end不相遇的情况下，end先找到第一个比轴小的值，begin找到第一个比轴大的值，交换这两个值，然后end继续向前走，begin继续向后走，执行上述操作，直到end与begin相遇时，将相遇位置的值与轴的值交换，并且轴的位置改为相遇位置。

这样子就叫做一次单趟排序，然后我们发现，经过这一趟单趟排序后，原本轴的位置的值a被放在了后面，保证了如果其左边有值，左边的值<=a，右边有值，右边的值就>=a。也就是说，把原来的轴的值a确定了位置，此时只需要将这个a这个值左右两边执行单趟排序操作就可以了，直到无法执行单趟排序操作。这是递归的事情，我们现在只是对单趟排序编写：

int PivotHoare(int* a, int left, int right) {//甩轴(甩到中间) 目的是获取换轴后的新轴位置 便于后面分区间int keyi = left;//轴坐标int end = right, begin = left;while (begin < end) {while (a[end] > a[keyi] && begin != end) {//!=可以写成< 但是都一样 因为规定了begin必须小于end 相同的时候要退出end--; }//找到右边第一个小于轴的while (a[begin] < a[keyi] && begin != end) { begin++;}//找到左边第一个大于轴的//但是这里有一个问题就是：很快能会导致begin走到end的后面 这是不允许的 所以要加判断swap(&a[begin], &a[end]);}//出循环后 要换轴swap(&a[keyi], &a[begin]);keyi = begin;return keyi;//
}

这里先对代码展示和原理讲解，对于函数的返回值为int这放在后面来讲。

可能会好奇为什么这样操作，为什么能确保begin和end相遇的时候值为什么一定会比轴小，从而可以与轴交换达到确定原本轴值位置的效果：

我们来证明一下：
以最左边为轴 右边先找最小的

当begin和end相遇的时候有两种情况：
1.begin往后找碰到end
2.end往前走碰到begin

对于第一种情况：肯定是end已经找到了比轴小的值了，那么begin往后相遇的话，那此时一定小于轴的值。
对于第二种情况：由于是end先走，所以不可能出现begin找到比轴大的值后，end再往前与其相遇。而是在上一次的begin和end交换后，end往前走来相遇begin。而begin位置的值由于在上一次已经和end完成交换，所以指向的值一定是小于轴的。

所以得到一个结论，以左边为轴，end先走。当然可以以右边为轴，只不过就得左边先走。其逻辑与上述正好是相反的。这种方法是比较抽象且不够直观的，所以介绍另外两种方法。

第二种方法：前后指针法

思路如图所示：定义cur和prev指针，当cur指向的值大于等于轴，就往直接往前走，反之让prev++后二者值交换。最后当cur越界的时候换轴。其原来其实和第一种方法时一样的，但是思路比第一种简单的多，也很好实现。很多教科书上是以这一种作为例子的。

我们发现，最后达成的效果其实也是一样的。
代码实现：

int PivotDoublePointer(int* a, int left, int right) {//三节点中取轴int midi = ArrayMidi(a, left, right);swap(&a[left], &a[midi]);int keyi = left;//轴坐标int prev = left, cur = left + 1;//前后指针遍历while (cur <= right) {if (a[cur] < a[keyi] && ++prev != cur) {swap(&a[prev], &a[cur]);}cur++;}swap(&a[keyi], &a[prev]);keyi = prev;return keyi;
}

3.挖坑法

其实这个方法的本质和也是将轴甩到后面，然后便于分左右区间。
代码实现：

int PivotDigHole(int* a, int left, int right) {//三节点中取轴int midi = ArrayMidi(a, left, right); swap(&a[left], &a[midi]);int key = a[left];int Hole = left;//坑位int begin = left, end = right;while (begin < end) {while (a[end] > key && begin != end) {end--;}//找到右边第一个比key小的值 放到当前坑位置 改变坑位置a[Hole] = a[end];Hole = end;while (a[begin] < key && begin != end) {begin++; }//找到左边第一个比key大的值 将这个值放到当前坑位 改变坑位置a[Hole] = a[begin];}a[Hole] = key;return Hole;
}

上述的三种方法都是快速排序的单趟排序算法。

快排递归实现

有了上面的三种单趟排序作为支撑，快速排序的递归就非常容易实现了：

void QuickSort(int* a, int left, int right) {//递归需要有终止条件//当区间只有一个节点(Left == right) || 区间无节点 区间不存在 经过分析 这个情况是(Left > right)if (left >= right) return;int keyi = 0;//三个单趟排序方法效率差不多 随意选一个就可以keyi = PivotHoare(a, left, right);   //keyi = PivotDoublePointer(a, left, right); //keyi = PivotDigHole(a, left, right);//再分左右区间执行上述操作QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}

每次递归都是讲轴甩到后面并且进行划分左右区间执行上述操作，直到区间元素个数为1或0的时候结束递归。

这个时候我们再来看为什么前面三个单趟排序要返回新的轴keyi的位置，就是为了划分区间。

递归实现的优化

当然上述的快排还是有一些劣势的，比如给定的数据是升序的时候，那位于最左边的轴是没办法甩到中间的。那此时以新轴再划分区间，那么左区间一定是空，右区间是n-1个元素。

以此类推下去，那么划分区间的次数是N次。如果每次都能把轴尽可能地甩到中间，那么分区间的次数大约为LogN。这个区别是很大的。所以不能一昧地选最左边地位置为轴。

对于选轴的方法这里提供两组思路：
1.随机数选，在当前区间范围内进行选择。
2.三数选中，即在当前区间的最左，中间，右边三个位置选择中间的那个数作为轴的值，然后将这个中间数与最左边位置的值交换。

可能会有想要找整个数组的中间数来做轴，这当然好，但是找到中间数是很难的，几乎要给这个数组再排一次序。所以这个方案不太可能。

随机数听着总感觉不太好，所以不妨用第二种方法：
我们先写一个三数取中间的函数：

int ArrayMidi(int* a, int left, int right) {int midi = (left + right) / 2;int arr[3] = { 0 };arr[0] = a[left];arr[1] = a[midi];arr[2] = a[right];InsertSort(arr, 3);int midNum = arr[1];if (a[left] == midNum) return left;else if (a[midi] == midNum) return midi;else return right;
}

这里可以使用逻辑判断，但我选择先对三个数据排序，放在数组中。然后判断哪个坐标对应的值和数组中间的数相同就返回哪个坐标。

注意：一定是返回坐标，因为要将三数中间的那个位置的值与最左边进行交换，是需要用到坐标的。用值是不合理的，因为值可能会重复，且需要重新查找。

然后我们就进行了第一次改进：

```c
int PivotHoare(int* a, int left, int right) {//三节点中取轴int midi = ArrayMidi(a, left, right);swap(&a[left], &a[midi]);//甩轴(甩到中间) 目的是获取换轴后的新轴位置 便于后面分区间int keyi = left;//轴坐标int end = right, begin = left;while (begin < end) {while (a[end] > a[keyi] && begin != end) {//!=可以写成< 但是都一样 因为规定了begin必须小于end 相同的时候要退出end--; }//找到右边第一个小于轴的while (a[begin] < a[keyi] && begin != end) { begin++;}//找到左边第一个大于轴的//但是这里有一个问题就是：很快能会导致begin走到end的后面 这是不允许的 所以要加判断swap(&a[begin], &a[end]);}//出循环后 要换轴swap(&a[keyi], &a[begin]);keyi = begin;return keyi;//
}int PivotDoublePointer(int* a, int left, int right) {//三节点中取轴int midi = ArrayMidi(a, left, right);swap(&a[left], &a[midi]);int keyi = left;//轴坐标int prev = left, cur = left + 1;//前后指针遍历while (cur <= right) {if (a[cur] < a[keyi] && ++prev != cur) {swap(&a[prev], &a[cur]);}cur++;}swap(&a[keyi], &a[prev]);keyi = prev;return keyi;
}int PivotDigHole(int* a, int left, int right) {//三节点中取轴int midi = ArrayMidi(a, left, right); swap(&a[left], &a[midi]);int key = a[left];int Hole = left;//坑位int begin = left, end = right;while (begin < end) {while (a[end] > key && begin != end) {end--;}//找到右边第一个比key小的值 放到当前坑位置 改变坑位置a[Hole] = a[end];Hole = end;while (a[begin] < key && begin != end) {begin++; }//找到左边第一个比key大的值 将这个值放到当前坑位 改变坑位置a[Hole] = a[begin];}a[Hole] = key;return Hole;
}

只需要将这个三数取中的优化方法插入到单趟排序算法即可。因为换轴是单趟排序的事情。

但是还有一个问题：就是当区间元素个数较少的时候，仍然要执行多次递归，这不也是很浪费时间吗？该如何优化呢？

对此提出了一个小区间优化法：即当区间元素个数小于某个值的时候，对其采用更快的排序算法。在元素个数不多的情况下，前面的算法经过综合选择，插入排序算法是最好的。

所以来看一下第二次改进：

void QuickSort(int* a, int left, int right) {//递归需要有终止条件//当区间只有一个节点(Left == right) || 区间无节点 区间不存在 经过分析 这个情况是(Left > right)if (left >= right) return;//小区间优化if (right - left + 1 <= 10) {InsertSort(a + left, right - left + 1);return;}int keyi = 0;//三个方法效率差不多 随意选一个就可以keyi = PivotHoare(a, left, right);   //keyi = PivotDoublePointer(a, left, right); //keyi = PivotDigHole(a, left, right);//再分左右区间执行上述操作QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}

这就是基础的优化过程，经过这样的操作，快速排序就是真的快了。这个优化思路和c语言库函数qsort是很类似的。其底层也大致是这样一个逻辑。

当然对于快速排序还有更多的优化方案，在这里就不做过多介绍，因为不是本篇文章重点。

非递归实现

对于快排，如何使用非递归来实现呢？

答案是用栈，在讲归并排序的时候我们就讲到了，可以用栈来模仿递归过程。

比如当前左右坐标为0和9，入栈
出栈后进行单趟排序，再来分区间
假设分区间很均匀
就先将右区间5到9入栈，再将0到4入栈
再出栈0到4，单趟排序，分区间…

不断执行上述操作，是很像二叉树的先序遍历的。根据这个特性，我们使用栈来模拟。当然也可以使用队列来进行处理。但是使用栈更加贴合递归的思想，所以在这里我就展示如何使用栈

有人会提问，栈之前实现的是对整形进行操作呀，现在要入区间，那是不是得改一下栈存储的元素的数据类型呢？

如果不嫌麻烦当然可以，但是不想改也可以，可以先将区间的右坐标入栈，再入栈左坐标。出栈两次不就能先后得到区间左右坐标了吗？

void QuickSortNonRecursion(int* a, int left, int right) {Stack st;StackInit(&st);StackPush(&st, right);StackPush(&st, left);while (!StackEmpty(&st)) {//每次进行单趟排序算法即可int begin = StackTop(&st);StackPop(&st);int end = StackTop(&st);StackPop(&st);//单趟排序int keyi = PivotHoare(a, begin, end);//划分区间  [begin   keyi-1]  [keyi + 1    end]//右区间满足条件入栈if (keyi + 1 < end) {StackPush(&st, end);StackPush(&st, keyi + 1);}//左区间满足条件入栈if (begin < keyi - 1) {StackPush(&st, keyi - 1);StackPush(&st, begin);}}StackDestroy(&st);
}

本质上就是模仿递归的思想，只不过借用栈这个媒体把递归方式化简为非递归而已。

时间复杂度和空间复杂度

再对使算法进行优化以后，轴会尽可能地甩到中间，所以分区间次数大致为LogN，每次单趟排序由于是遍历全部数据一次，所以时间复杂度为O(N)，故最后时间复杂度为O(N * LogN)。对于非递归方式其实没有太大地提升时间效率。当然展示的非递归代码并没有小区间优化。但是总体而言差别不大。时间复杂度大致都为O(N * LogN)。

空间复杂度：对于递归算法和非递归，空间复杂度都为O(LogN)，递归是开辟函数栈帧。但是刚刚讲到过，同一个区间的左右区间使用的栈帧其实是同一块。所以最后开辟的空间次数就大约是LogN次。而非递归来讲，使用的是栈这个数据结构。但是由于分区间的次数大是LogN次，但是需要将区间出栈后才会入左右子区间。所以这个流程和栈帧还是有点像。所以最后空间复杂度都为O(LogN)。

排序算法性质与总结

对于排序算法的总结有几种指标：时间复杂度、空间复杂度、稳定性等。本部分只对前三个进行总结。

时间复杂度和空间复杂度总结

时间复杂度和空间复杂度在之前的每个算法实现部分都有讲到，所以只进行汇总：

算法	时间复杂度	空间复杂度
堆排序	O(NLogN)	O(1)
选择排序	O(N^2)	O(1)
插入排序	O(N^2)	O(1)
希尔排序	O(N^1.3)	O(1)
计数排序	O(N+range)	O(N)
归并排序	O(NLogN)	O(N)
冒泡排序	O(N^2)	O(1)
快排排序	O(NLogN)	O(LogN)

稳定性

所谓稳定性，不明所以地会认为稳定性就是时间复杂度的波动程度。其实不然，实际上，上述所有算法的时间复杂度都是具有波动的。总不能说所有算法都是不稳定的吧。

稳定性的意思是：原数组种相同的元素，再经过排序之后，原本的相对位置不变。

如图所示，排序前，红色三角指向的1在绿色三角指向的1之前，排序后，红色仍在前。

可能会好奇，这有什么用呢？不都一样吗？
这是因为当前排序的数据只有整形。如果排序的是结构体呢？就比如高考的排位，如果总分一样的情况下，就需要比较数学分数。那应该如何操作呢？

我们可以先对所有考生的数学成绩进行排序，然后再使用稳定的排序算法，那么就一定能保证同分下在前的考生一定是数学成绩高的。这就很有用了。只不过当前排序的数据比较单一看不出来这个性质罢了。

然后就来讨论一下各种算法是否稳定：
1.堆排序
堆排序是不稳定的，理由很简单，因为堆排序的过程是模仿出堆的过程。如果有相同数据，靠上的会先放在数组的后面。那不就改变了相对顺序吗?所以堆排序不稳定

2.选择排序
选择排序看似稳定，实则不然，我们可以举一个例子：
数组{1,6,6,7,5,4}
第一躺选择排序后{1,6,6,5,4,7}
第二趟排序后{1,4,6,5,6,7}
发现此时就出问题了，原本在前面的6跑到后面去了，所以也是不稳定的

3.插入排序
这个排序是很稳定的。过程是让未排序区的第一个元素在已排序区内寻找第一个比自己小的数或者插入第一个位置。我们可以通过逻辑来控制。当碰到相同的数据的时候，就放在其后面即可。所以是可以通过逻辑的控制来决定其稳定性的。

4.希尔排序
乍一看，希尔排序的思路和插入排序也差不多，那也是稳定的。那就大错特错了，因为希尔排序是不同组进行插入排序，那不同组的结果是没法得知的，也无法控制其逻辑使其保持相对顺序，所以希尔排序是不稳定的。

5.归并排序
归并排序需要考虑的地方就是归并到tmp数组的时候。但是我们也可以通过逻辑的控制来保证其稳定性。即当两个数组此时要插入的值一样时，优先让上面的先插入，即在前面的先插入。这就保证了稳定性。

6.计数排序
计数排序是利用统计概念进行排序。但是正由于其独特的排序方式，其实是不太好判断其稳定性的。因为也不知道第一个输出的数据是原本在前还是在后。所以不做过多讨论

7.冒泡排序
冒泡排序是很稳定的。其逻辑是从头开始在未排序区内交换数据，让大的数据不断下沉到数组尾部。我们仍然可以通过逻辑的控制，当两个数据相同的时候，不执行交换操作。这样就能保证相对位置不改变了。

8.快速排序
快速排序一定是不稳定的，原因在其”甩轴“的过程。
举例：数组{6,5,2,3,6,8,1}经过简单的单趟排序后变成了{1.5.2.3.6.6.8}
原本在第一个位置的6跑到了倒数第二个位置，相对位置直接就改变了。所以快排不稳定。

算法适用范围

由时间复杂度来看，选择排序，冒泡排序，插入排序的速度是比较慢的。
但是他们三个也是有区别的，效率上：选择 < 冒泡 < 插入
虽然时间复杂度是O(N^2)，但是插入排序还是很有作用的。特别是当数据个数比较少的时候，插入排序算法是非常好用的，不用额外开辟空间，而希尔排序预排序的过程只在数据个数量大的情况下才会比较有优势。所以快排的小区间优化法选择的是插入排序算法。

而对于其余两个排序算法其实用的很少，冒泡排序算法几乎只剩下了教学意义。

当数据比较接近升序的时候，使用希尔排序是最快的。

快速排序每一次单趟排序都能确定一个数据的位置。

当数据范围比较集中且只有整数的时候，用计数排序是最快的。

这些就是这些排序的大致用法了。

全文总结

本篇文章重点是从排序算法的引入开始，从算法的思路到实现，再到算法的优化，以及性能的总结进行讲解。到此本篇文章就彻底结束了。