“东风随春归，发我枝上花。”
前言：
排序是日常生活中极其常见的一种算法，它的功能很简单，就是将数字按照升序/降序排列，最终形成一组有序的数字，不过形成有序数字的过程有多种实现方式，它们各有好坏，接下来，由我带你手撕排序算法。
目录
🥰写在前面
💐Part1.插入排序
1.1直接插入排序
1.1.1思想
1.1.2实现
1.2希尔排序
1.2.1思想
1.2.2实现
🌺Part2:选择排序
2.1选择排序
2.1.1思想
2.1.2实现
2.2堆排序
2.2.1思想
2.2.2实现
写在前面
排序离我们的生活很近，这是一种很重要的算法，比如：
网上购物按价格升序排序
世界500强排名
排序是常见的，也是重要的，寻找最优的排序能做到优化，所以理解掌握排序是必要的。
下面是要讲解的常见排序：
我们默认实现排升序，一个一个来：
Part1.插入排序
1.1直接插入排序
1.1.1思想
相信多数人是打牌的，你知道吗，在摸牌的时候，你就悄悄进行了插入排序操作：
这种排序就是新拿到的数字与已有的数字进行比较，确定合适的位置后进行插入操作。
结合动图深度理解：
可以看到：
• 当只有一个数字时，没有可比性，可理解为有序；
• 取下一个数字b，与前一个数字a比较，如果b小于a，则需要调整二者的位置，如果a小于b，符合升序，则不需要调整；
• 前一部分排好的数字逐渐增多，取此区间后最近的数字进行挨个比对，不是合适位置，比较过的数字就后移一位，是合适位置，就进行插入操作。
1.1.2实现
// 插入排序 void InsertSort(int* a, int n) { for (int i = 1; i < n; i++) { int tmp= a[i]; int endi = i - 1; while (endi >= 0) { if (tmp < a[endi]) { a[endi + 1] = a[endi]; endi--; } else break; a[endi + 1] = tmp; } } }
特征分析：
当原数字越接近有序时，效率越高；
时间复杂度：最好：O(N) 最坏：O(N^2)；
空间复杂度：O(1)；
稳定性(是否动了相同数字的相对位置)：稳定
这个排序看起来效率并不高，希尔在快速排序的基础上进行了优化：
1.2希尔排序
1.2.1思想
本质还是插入排序，只不过希尔做了一个巧妙的处理：引入了 gap ，每隔一个gap分为一组；
先让一部分数字相对有序，再调整下一部分，直至最后有序；
1.2.2实现
// 希尔排序 void ShellSort(int* a, int n) { int gap = n; while (gap > 1) { //gap /= 2; gap = gap/3 + 1; for (int i = 0; i < n - gap; i++) { int endi = i; int tmp = a[i + gap]; while (endi >= 0) { if (tmp < a[endi]) { a[endi + gap] = a[endi]; endi -= gap; } else break; a[endi + gap] = tmp; } } } }
注意：gap是多少并没有明确规定，一般是 gap/3+1
特征分析：
希尔排序是对直接插入排序的优化，给gap相当于进行预排序，当gap==1时数组就相当有序了，比起直接插入，会快一些；
时间复杂度：最好：O(N^1.25)~O(N^1.3) (参考《计算机程序设计技巧》--Knuth) 最坏：O(N^2)；
空间复杂度：O(1)；
稳定性：不稳定
Part2:选择排序
2.1选择排序
2.1.1思想
这种排序方法是我们出厂自带的排序方法，试想：给你一堆乱序的数字，你会怎么排？
通常情况下，我们会从头到尾扫一遍，选出最小的放到最前面，再扫一眼，选出第二大的放到第二位。
这就是选择排序的基本思想。
动图：
是不是挺符合认知规律的？
2.1.2实现
// 选择排序 void SelectSort(int* a, int n) { int left = 0, right = n - 1; while (left < right) { // 初始化 int mini = left; int maxi = left; // 找到较大/较小值的下标 for (int i = left+1; i <= right; i++) { if (a[i] < a[mini]) // 前后顺序会影响结果 { mini = i; } if (a[i] > a[maxi]) { maxi = i; } } Swap(&a[mini], &a[left]); // 调试过程中会有left与maxi重叠的情况，这时需要针对这种情况调整 if (left == maxi) maxi = mini; Swap(&a[maxi], &a[right]); left++; right--; } }
特征分析：
直接选择排序思路易理解，但效率不高，不实用；
时间复杂度：最好：O(N^2) 最坏：O(N^2)；
空间复杂度：O(1)；
稳定性：不稳定
2.2堆排序
2.2.1思想
堆排序在往期 什么是堆，如何实现？(附堆排序，TOP-K问题) 中有详解，
先是建大堆，再是模拟删除操作，这里就不多说啦。
2.2.2实现
//堆排序 void HeapSort(int* a, int n) { //向下调整（效率更高） for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); } int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); end--; } }
特征分析：
利用堆的特性，选数快很多，效率较高
时间复杂度：最坏：O(N*logN) 最好：O(N*logN) ；
空间复杂度：O(1)；
稳定性：不稳定
总结：
这期是常见排序的前半部分，讲了两类排序：插入排序和选择排序，思想不难，多注意实现中的细节。我打算将后半部分放在下期：交换排序和归并排序。
