注：此文章均以升序讲解
经典排序
排序分类 🚀
1. 插入排序🚀
1.1 基本思想🚀
1.2 直接插入排序:🚀
1.3 插入排序特性🚀
2. 希尔排序（缩小增量排序）🚀
2.1 基本思想🚀
2.2 希尔排序代码🚀
2.3 希尔排序特性🚀
3. 选择排序🚀
3.1 基本思想🚀
3.2 直接选择排序🚀
3.3 选择排序特性🚀
4. 堆排序🚀
4.1 基本思想🚀
4.2 堆排序代码🚀
4.3 堆排序特性🚀
5. 冒泡排序🚀
5.1 基本思想🚀
5.2 冒泡排序代码🚀
5.3 冒泡排序特性🚀
6. 快速排序（重点）🚀
6.1 快速排序介绍🚀
6.2 hoare版本🚀
6.3 挖坑法🚀
6.4 前后指针法🚀
6.5 快速排序完整代码（递归）🚀
6.6 快速排序非递归实现🚀
6.7 快速排序特性：🚀
7. 归并排序🚀
7.1 基本思想🚀
7.2 归并排序递归代码🚀
7.3 归并排序特性🚀
7.4 归并排序的非递归实现（难点）🚀
8. 计数排序🚀
8.1 基本思想🚀
8.2 计数排序代码实现🚀
8.3 计数排序特性🚀
9.排序特性总结🚀
排序分类 🚀
1. 插入排序🚀
基本思想🚀
直接插入排序是一种简单的插入排序法，其基本思想是： 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
实际中我们玩扑克牌时，就用了插入排序的思想
直接插入排序:🚀
当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。
代码：
void InsertSort(int* a, int n)//插入排序 { // [0,end]插入 end+1,[0,end+1]有序 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; } }
插入排序特性🚀
- 元素集合越接近有序，直接插入排序算法的时间效率越高（在已排好序的情况下其时间复杂度为O(N).
- 时间复杂度：O(N^2)
- 空间复杂度：O(1),它是一种稳定的排序算法
- 稳定性：稳定
那么所谓的稳定性是什么呢？我想在以链表的排序进行解释，这样好说明。在排序之前，或许会有重复的元素，他们的值相同，但是节点的地址不同，并且一前一后，当排序时，难免会将两个具有相同值的节点的前后顺序颠倒，因为这样对于排序来说值相同前后是无关紧要的，但是他们的节点是不同的，节点与节点的区别在于地址不同，因此，出现了这种情况就代表了排序中的不稳定，相反，这两个节点排序之后的前后顺序相同也就代表着排序是稳定的。
2. 希尔排序（缩小增量排序）🚀
2.1基本思想🚀
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有记录分成gap个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，取重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
先以一次排序进行演示，按照9 1 2 5 7 4 8 6 3 5
为初始数据的话，假设gap = 3，分成的就是这样几组：
9 5 8 5
1 7 6
2 4 3
通过将其分别排序可以变成这样：
5 5 8 9
1 6 7
2 3 4
最后的数据就是这样：
5 1 2 5 6 3 8 7 4 9
先来看看粗略理解的希尔排序
//初始的顺序：9 1 2 5 7 4 8 6 3 5 //预排序 int gap = 3; for (int j = 0; j < gap; ++j)//将gap组依次分别进行排序 { // [0, end]插入 end+gap [0, end+gap]有序 --间隔为gap的数据 for (int i = j; i < n - gap; i += gap) { 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; } } //此时数组得数据顺序变成：`5 1 2 5 6 3 8 7 4 9` //再插入排序 void InsertSort(int* a, int n)//插入排序 { // [0,end]插入 end+1,[0,end+1]有序 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; } } //最后变成：1 2 3 4 5 5 6 7 8 9
这样的预排序可以看出是在直接插入排序的基础上进行改变，里面的两层循环就是将直接插入排序中的1变成gap，得到的这个数据我们称其为预排序，通过这样的排序之后再进行插入排序时将会大幅度的缩短时间（尤其是初始数据为逆序，将其排成升序），这就是希尔排序的思想。上面举的例子为gap=3,那么gap的标准应该如何进行选择呢？这个问题在总结特性的时候会说到，并且后续标准希尔排序代码也会用到。
然而这样的排序似乎有很多疏漏，gap的值应该随着数据量的变化而发生改变，而不是定死的赋予其值的大小，因为我们在插入排序基础上加上预排序变成希尔排序的目的就是让其效率变高，而效率变高本身就是对极其庞大的数来说的，因此，为了使效率变高，我们每次应使gap为不同的值一直进行预排序（上面的只赋值给gap一次，即只进行了一趟排序，就是gap = 3），而我们也发现，gap=1的时候就是直接插入排序，那我们就可以每次这样处理：gap = gap / 3 + 1 ,因为gap不能为0，因此，需要+1，于是外面就可以再来一层循环，while（gap>1）然后gap = gap/3+1,这样就是真正的希尔排序了。但由于循环层数过多（已经达到了4层），因此，我们将思路从上述的：将gap组依次进行排序（这句话在上面代码里）变成让gap组一起排序，这样就是把两个循环合并成了一个循环：（如下代码展示）
gap组依次进行排序：
for (int j = 0; j < gap; ++j)//将gap组依次分别进行排序 { // [0, end]插入 end+gap [0, end+gap]有序 --间隔为gap的数据 for (int i = j; i < n - gap; i += gap) { 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; } }
变成gap组一起排序:
//优化成两层循环,但效率上实际没太大差别 for (int i = 0; i < n - gap; ++i) //gap组数据依次多组并排 { // [0, end]插入 end+gap [0, end+gap]有序 --间隔为gap的数据 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; }
希尔排序代码🚀
void ShellSort(int* a, int n)//希尔排序 { // gap > 1 预排序 // gap == 1 直接插入排序 //优化成两层循环,但效率上实际没太大差别 int gap = n; while (gap > 1) { gap = gap / 3 + 1; for (int i = 0; i < n - gap; ++i) //gap组数据依次多组并排 { // [0, end]插入 end+gap [0, end+gap]有序 --间隔为gap的数据 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; } } }
希尔排序特性🚀
希尔排序的特性总结：
希尔排序是对直接插入排序的优化
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定：
因为我们的gap是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们暂时就按照蓝色框的时间复杂度来算。
3. 选择排序🚀
3.1基本思想🚀
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素
3.2直接选择排序🚀
void SelectSort(int* a, int n) { int begin = 0, end = n - 1; while (begin < end) { //选出最小的放在begin位置 //选出最大的放在end位置 int mini = begin, maxi = begin; for (int i = begin + 1; i <= end; ++i) { if (a[i] > a[maxi]) { maxi = i; } if (a[i] < a[mini]) { mini = i; } } Swap(&a[begin], &a[mini]); if (maxi == begin)//修正一下maxi,因为上一个begin位置已经被换走了 { maxi = mini; } Swap(&a[end], &a[maxi]); begin++; end--; } }
3.3选择排序特性🚀
直接选择排序的特性总结：
- 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
4. 堆排序🚀
4.1基本思想🚀
对于堆排序，之前的文章已经详细的讲到，因此，我将堆排序的链接放在这里，这里主要展示堆排序代码：
堆排序讲解
4.2 堆排序代码🚀
void Swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } void AdjustDown(int* a, int n, int parent) { int child = parent * 2 + 1; while (child < n) { if (child+1 < n && a[child] < a[child + 1]) { 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)//堆排序 { //建堆 for (int i = (n - 1 - 1) / 2; i >= 0; --i) { AdjustDown(a, n, i); } //选数 int i = 1; while (i < n) { Swap(&a[0], &a[n - i]); AdjustDown(a, n - i, 0); ++i; } }
堆排序特性🚀
- 时间复杂度不分情况好坏而变化
- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定
5. 冒泡排序🚀
5.1基本思想🚀
冒泡排序，大家再熟悉不过，就是将其反复交换排序，但是这里将展示冒泡的优化。在冒泡排序的交换过程中，在冒泡排序交换节点的过程中我们新增一个flag,每一次交换排序时如果发现顺序不对那么相邻之间的两个元素就会交换位置，当然，如果在一趟交换排序中一次都没有交换，那么就说明接下来的元素已经是有序的，但对于一般的冒泡排序来说，即便有序，仍然需要将所有都遍历到，但我们的目的是将其优化，也就是当确定这趟排序中已经有序，那么我们就不需要继续排序，跳出这个循环即可，而这个时候就是需要flag这个变量判断：
5.2 冒泡排序代码🚀
void Swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } void BubbleSort(int* a, int n) { for (int i = 0; i < n - 1; i++) { int flag = 0; for (int j = 0; j < n - i - 1; j++) { if (a[j] > a[j + 1]) { Swap(&a[j], &a[j + 1]); flag = 1; } } if (flag == 0) { break; } } }
5.3冒泡排序特性🚀
- 此优化后的代码当完全有序时的时间复杂度为O(N)
- 时间复杂度：O(N)
- 空间复杂度：O(1)
- 稳定性：稳定
