目录
引言
一、直接插入排序
概念
图文解析
1、起始状态
2、循环时
3、最后细节
代码实现
代码
复杂度
稳定性
二、希尔排序
概念
图文解析
1、算法实现
2、设置增量
3、进行交换
4、缩小增量
代码实现
代码
时间复杂度
空间复杂度
稳定性
三、直接选择排序
概念
图文解析
1、初始化
2、交换
代码实现
代码
时间复杂度
空间复杂度
稳定性
四、堆排序
概念
代码实现
代码
时间复杂度
空间复杂度
稳定性
五、冒泡排序
概念
图文解析
代码实现
代码
时间复杂度
空间复杂度
稳定性
六、快速排序
概念
图文解析
Hoare法
挖坑法
前后指针法
代码实现
Hoare法代码
挖坑法代码
前后指针法代码
快排优化
三数取中法
三数取中代码
加入插排
时间复杂度
空间复杂度
稳定性
七、归并排序
概念
图文解析
代码实现
代码
时间复杂度
空间复杂度
稳定性
排序算法，或许是我们日常最常见也是使用频率最多的算法。比如你在电商网站买东西，推荐商品往往基于相似度或者基于销售量等维度排序。我们每日接收的邮件是程序中按照时间进行排序好的，我们点外卖时候推送的列表是按照评分和地理位置进行排序的。搜索引擎检索内容也是按照一定的相似度算法进行排序好才呈现给你的，所以搜索引擎实际上就是一个排序引擎。
本篇文章通过图例的方式逐一讲解最常使用的七大排序算法。
我下面所写的排序都按从小到达排
插入排序是一种原址（in-place）排序，原址的意思就是对于任何的输入数据序列都可以在不占用或者只占用常量的额外存储空间的情况下完成排序。插入排序对于已经排序好的数据可以实现O(n)的最佳排序时间，对于逆序的数据序列排序运行时间最差O(n^2).
总结：插入排序就是把待排序的每条记录按照值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
插入排序的理解，我们可以想象一下，我们与朋友一起玩扑克牌。在摸牌阶段，从牌堆中一张张的取牌，为了保持手里面一副牌一直保持有序状态，每次都会把新取得的扑克牌与手头的牌进行比较，比较的方式是从右向左，找到合适的位置，插入即可，这就是一种典型的插入排序。唯一需要注意的是，排序算法中的插入实际上是一种逐个交换实现的，而不是直接插到指定的位置。
1、起始状态
2、循环时
将 arr[i] 放到 tmp 里，让 arr[j] 和 tmp 中的值比较大小，要是 arr[j] > tmp，那么就交换值，要 是小于的话就跳出这次循环。例如下图：（请大家比对最开始的图片想一下）
3、最后细节
一直这样慢慢的比下去，到最后还需要把tmp里的值放回 arr[j+1]。如下图需要放回。
代码
复杂度
时间复杂度：
- 最好 O(n) 有序
- 最好 O(n^2) 逆序
- 结论：对于直接插入排序，数据越有序越快。
- 应用场景：当数据基本上是有序的时候，使用直接插入排序。
空间复杂度：
O(1)
稳定性
稳定的排序
希尔排序是把序列按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量的逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个序列恰好被分为一组，算法便终止。
1、算法实现
希尔排序需要定义一个增量，这里选择增量为 gap = length / 2，缩小增量以 gap = gap / 2 的方式，这个增量可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列，这个增量是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。
2、设置增量
对于一个无序序列[8，9，1，7，2，3，5，4，6，0]来说，我们初始增量为 gap = length / 2 => 5，所以这个序列要被分为5组，分别是[8，3]，[9，5]，[1，4]，[7，6]，[2，0]，对这5组分别进行直接插入排序，则小的元素就被调换到了前面，然后再缩小增量 gap = gap / 2 => 2。
3、进行交换
下图是第一次交换后的结果，大家观察，希尔排序的一次交换能交换几个值，就不是直接插入排序那样需要一个个的去交换，这样就节省了时间。
4、缩小增量
缩小增量后第二次交换：
序列再次被分为2组，分别是 [3，1，0，9，7] 和 [5，6，8，4，2]，再对这两组进行直接插入排序，那么序列就更加有序了。
然后再缩小增量，gap = gap / 2 => 1，这时整个序列就被分为一组即 [0，2，1，4，3，5，7，6，9，8]，最后再进行调整，就得到了有序序列 [0，1，2，3，4，5，6，7，8，9]。
代码
确定增量代码
排序代码
时间复杂度
参考资料：《数据结构(C语言版)》--- 严蔚敏
希尔排序的分析是一个复杂的问题,因为它的时间是所取“增量”序列的函数,这涉及一些数学上尚未解决的难题。因此,到目前为止尚未有人求得-种最好的增量序列,但大量的研究已得出一-些局部的结论。如有人指出,当增量序列为 dlta[k] = 2^(-k+1) -1时,希尔排序的时间复杂度为 O(n^3/2) 其中 t 为排序趟数, 1 ≤ k ≤ t ≤ [log2(n+1)]。还有人在大量的实验基础上推出，当n在某个特定范围内,希尔排序所需的比较和移动次数约为n^1.3,当n→∞时,可减少到n(log2n)2。 增量序列可以有各种取法中,但需注意:应使增量序列中的值没有除1之外的公因子,并且最后一个增量值必须等于1。
总结来说就是经过很多大佬的计算，希尔排序的时间复杂度没有一个确定的值，确定的大概范围是：O(N^1.3 - N^1.5)
空间复杂度
O(1)
稳定性
不稳定的排序
直接选择排序是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零，选择排序是一种不稳定的排序方法。