👉插入排序
插入排序的核心思想：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为
止，得到一个新的有序序列
也就是说可以把数组分成前后两个数组，每一次前面的数组都是有序的，再将有序数组后面的数插入到有序的数组中，每一次插入后都会形成一个新的有序数组
下面图片以升序为例
插入排序有几个特性，当数列越接近有序时，插入排序的时间效率越高；它的最坏时间复杂度为O(N^2)；插入排序是一个稳定的排序法
//插入排序 O(N^2)
void InsertSort(int* a, int n) {
//一共要进行n趟排序
for (int i = 0; i < n - 1; i++) {
//记录有序数列待比较的元素下标
int end = i;
//记录待插入的数据
//也就是有序数列的后一个数据
int tmp = a[end + 1];
//最坏情况就是待插入的数据要和有序数列
//中的每一个元素都比较
//所以当待比较的元素下标小于0也就是超出原数组的范围了
//那么循环就结束
while (end >= 0) {
//如果待比较的元素比待插入的元素大
//那就原来待比较的元素就要往后放
//并且待比较的元素位置要往前走一步
if (a[end] > tmp) {
a[end + 1] = a[end];
end--;
}
//如果待插入的数据都不比有序数列最大的元素小了
//就不用继续比下去了
else
break;
}
//退出循环后，也就说明最新的待比较的元素比待插入的元素小
//那么最新的待比较的元素后面的位置就放待插入的元素
a[end + 1] = tmp;
}
}
👉冒泡排序
冒泡排序是一种容易理解且稳定的排序，但是其效率较低，时间复杂度为O(N^2)，所以对于数据量较大的情况下不推荐使用
其原理十分的简单，下面以升序为例：
每一趟排序过程都是让相邻的两个数据进行比较，如果后一个数据比前一个小则进行交换，下面来看动图理解
上图体现出了第一趟排序的过程，接下来看第二趟，看看有什么区别
不难看出，第二趟比第一趟需要排序的次数减少了。这是因为第一趟的时候已经把最大的数据排到了最后面，因此第二趟只需要把第二大的数据排到倒数第二个位置即可。
从中我们可以得出，假设数组长度为n，则需要排n趟，每一趟需要进行n - i次比较（i 为第几趟排序）。所以冒泡排序的时间复杂度为O(N^2)，利用代码实现冒泡排序，只需要用到两个循环即可完成。
当然在代码里我们可以做个简单的优化，因为利用冒泡排序的话，如果某一趟排序结束后，期间并没有发生一次数据的交换，那么这时该数组一定有序，所以我们不妨设一个变量来监视一下是否发生交换，如果没有交换那就退出循环即可
//冒泡排序 O(N^2)
void BubbleSort(int* a, int n) {
//排序总趟次
for (int i = 0; i < n - 1; i++) {
//设置一个变量监视是否发生交换
//如果没有发生交换，退出循环
int exchange = 0;
//每一趟需要排序n-i次
for (int j = 1; j < n; j++) {
//如果前一个数大于后一个则交换
if (a[j - 1] > a[j]) {
//之前写的交换函数接口
Swap(&a[j - 1], &a[j]);
//一旦发生交换，监视的变量值就改变
exchange = 1;
}
}
//如果没有发生交换退出循环
if (exchange == 0)
break;
}
}
👉希尔排序
希尔排序是对插入排序的一种优化，因为插入排序的特性数列越接近有序，它的效率就越快。
所以希尔排序的步骤就是，先对数列进行预排序，也就是让数列接近有序；然后再进行插入排序
预排序
预排序的思想是：
选定一个gap数，让数列每一组间隔为gap的元素组成一个数列，对于这个间隔数的取值，没有一个固定的取值，这里gap的值第一趟取n / 3 + 1；之后的每一趟都是gap / 3 + 1.
当gap==1时，数列会接近有序了，这个时候就相当于是插入排序了
如下图
图中将数列看成[9, 7, 3]；[1, 4, 5]；[2, 8]；[5, 6]这几组。然后分别对这几组进行插入排序，得到新的数列
得到新的数列后，更新gap的值，这个时候gap / 3 + 1后就会变成2，所以再以2为间隔进行分组
分好后再分别对每组进行排序
可以看出这个时候整个数列就相对原数列来说接近有序很多了，这时候我们再更新一下gap，这时我们会发现gap已经是1了，那这个时候排序的过程就相当于是插入排序了
说到这里，是不是觉得希尔排序相较于插入排序也没多大的变化呢（我一开始也是这么觉得），其实希尔排序相较于插入排序的效率快的不是一丁半点，但是由于gap的取值并不是固定的，所以它的时间复杂度也很难计算出来，在《计算机程序设计技巧》这本书中提到了，它的时间复杂度在O(N^1.25)到 O(N^1.25 * 1.6)之间，比插入排序快多了，话不多说，看看代码是如何实现的。
//希尔排序
void ShellSort(int* a, int n) {
//先预排序：接近有序
//再直接插入排序
int gap = n;
//预排log(3为底)N次
while (gap > 1) {
gap = gap / 3 + 1;
//间隔为gap的数据依次多组并排
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a[end + gap];
//每组的排序就是用插入排序完成
//只不过间隔是gap，所以交换后end也要减去gap
while (end >= 0) {
if (a[end] > tmp) {
a[end + gap] = a[end];
end -= gap;
}
else
break;
}
a[end + gap] = tmp;
}
}
}
👉选择排序
直接选择排序
基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
在这里我直接同时选最大和最小值
首先预设两个位置存放最大最小值，这里采用升序，所以一开始下标0的位置(begin)存放最小值，n-1的位置(end)存放最大值。依次遍历数组，假设min，max为begin位置的值，如果遍历到的值小于min，则更新min，同理如果大于max，则更新max，第一趟走完后，最小的数就会在最左边，最大的就会在最右边
可以看到，第一趟结束后，最小的0到最左边，最大的9到了最右边。第一趟排完后只需要让begin++一下排下一个位置，让end–一下排下一个位置，并且每一趟的开始，min，max都等于begin。如果begin>end,说明不需要再排了，已经排好了
代码实现：
//选择排序 O(N^2)
void SelectSort(int* a, int n) {
int begin = 0, end = n - 1;
while (begin < end) {
//选出最小的放在begin位置
//选出最大的放在end位置
int min = begin, max = begin;
for (int i = begin + 1; i <= end; i++) {
if (a[i] > a[max])
max = i;
if (a[i] < a[min])
min = i;
}
Swap(&a[begin], &a[min]);
//这里要注意，如果max的位置没有变得话
//说明所有的数都比begin的小
//为了防止重复交换，先把最小的交换到最右边
//然后再最左边和最右边互换
//所以这时候，先让max=min
if (max == begin)
max = min;
Swap(&a[end], &a[max]);
end--;
begin++;
}
}
堆排序
👉总结
这几个排序的思路和实现都不是很难，搞清了思路后代码的细节也要多加注意，还有剩下的几个排序再之后的文章更新。如果哪里不足，望各位大佬指出🍗
