十大排序算法
八种常见的排序算法的代码实现，各算法的时间复杂度和空间复杂度，各自的优缺点，以及应用场景。
八种排序算法包括：选择排序，插入排序，希尔排序，冒泡排序，快速排序，归并排序，堆排序，基数排序。
2022-04-05：新增桶排序和计数排序。
Github地址：https://github.com/zhenruyi/SortingAlgos
实现语言：Golang。
0 代码实现
1 选择排序
算法原理
- 首先在数组中找到最小的元素，将该元素和数组第一个元素交换位置；
- 依次从剩余数组元素中找到最小的，放到剩余的数组范围开头位置；
- 重复上一步，直到所有元素排序完毕。
时间复杂度和空间复杂度
时间复杂度
最好的情况：O(n^2)
最坏的情况：O(n^2)
平均：O(n^2)
空间复杂度：O(1)，in-place
不稳定：如果两个元素相等，先被选择的是后面的元素，所以后面的元素会被放到更前面。
优缺点
- 优点
- 简单
- 移动次数已知：n-1
- 缺点
- 慢，比较次数多
应用场景
当数据规模较小时，选择排序性能较好。
2 插入排序
算法原理
- 从数组的第二个元素开始，如果前一个元素比该元素大，则交换元素位置，即把该元素插入到适合的位置上；
- 从头到尾，把所有的元素插入到适当的位置；
- 如果该元素与前面某个元素相等，则插在其后面。
时间复杂度和空间复杂度
时间复杂度
最好的情况：O(n)
最坏的情况：O(n^2)
平均：O(n^2)
空间复杂度：O(1)，in-place
稳定：算法原理第三点。
优缺点
- 优点
- 简单，稳定
- 缺点
- 慢
- 比较次数不一定，比较次数越少，插入点后的数据移动越多
应用场景
基本有序且数据规模较小时，选用插入排序较好。
3 希尔排序
算法原理
- （对插入排序的改进，数组越大，优势越大。）
- 选择一个间隔 interval = 3 * interval + 1 (1, 4, 13, 40, …)；
- 每轮interval /= 3。该轮中，间隔interval的元素均实行插入排序；
- 当 interval = 1 时，整个数组当成一个组来处理，因为已经基本有序，所以比插入排序高效。
时间复杂度和空间复杂度
- 时间复杂度：难以度量，O(n^(3/2))
- 空间复杂度：O(1)，in-place
- 不稳定：interval不确定。
优缺点
- 优点
- 快，数据移动少
- 缺点
- 不稳定
应用场景
数据量较小且基本有序时。
4 冒泡排序
算法原理
- 从第一个元素开始，比较相邻元素，如果第一个比第二个大，交换位置；
- 对每一对相邻元素都这样操作，知道最大的元素到达数组尾；
- 重复以上两个步骤，已经有序的元素不进行操作；
- 直到所有元素都已经有序。
时间复杂度和空间复杂度
时间复杂度
最好的情况：我觉得是O(n^2)，有说O(n)
最坏的情况：O(n^2)
平均：O(n^2)
空间复杂度：O(1)，in-place
稳定：小于才交换，等于不交换。
优缺点
- 优点
- 简单
- 缺点
- 慢
- 每次值移动相邻两个元素
应用场景
用于当数据已经基本有序，且数据量较小时。
5 快速排序
算法原理
- （递归、分治）
- 从数组中选取一个key，比key大的元素放在key右边，比key小的元素放在key左边；
- 第一次的key选择为第一个元素，第一次排序好了后，以key为界分成两个数组；
- 两个数组分别重复上面的步骤。
时间复杂度和空间复杂度
时间复杂度
最好的情况：O(n log n)
最坏的情况：O(n^2)
平均：O(n log n)
空间复杂度：O(log n)递归的深度，每次递归都会保存一些数据，in-place
不稳定
优缺点
- 优点
- 已知最快的排序，数据移动少
- 缺点
- 不稳定，不适合对象排序
应用场景
快速排序适合处理大量数据排序时的场景。
6 归并排序
算法原理
- （归并就是将两个有序的数组合并成一个有序的数组）
- 将数组分成两个子数组，分别排序，最后归并；
- 子数组内又分成两个数组，最后归并；
时间复杂度和空间复杂度
时间复杂度
最好的情况：O(n log n)
最坏的情况：O(n log n)
平均：O(n log n)
空间复杂度：O(n)，out-place
稳定
优缺点
- 优点
- 稳定，适合对象排序
- 缺点
- 辅存很大
应用场景
数据量较大且要求排序稳定时。
7 堆排序
算法原理
- 建立最大堆，把根节点和最后一个节点交换；
- 重复上述步骤。
时间复杂度和空间复杂度
时间复杂度
最好的情况：O(n log n)
最坏的情况：O(n log n)
平均：O(n log n)
空间复杂度：O(1)，in-place
不稳定
优缺点
- 优点
- 最坏的条件下性能很优越，辅存少
- 缺点
- 不适合太小的序列，不稳定不适合对象排序
应用场景
堆排序适合处理数据量大的情况，数据呈流式输入时用堆排序也很方便。
8 基数排序
算法原理
- 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
时间复杂度和空间复杂度
时间复杂度
最好的情况：O(n * k)
最坏的情况：O(n * k)
平均：O(n * k)
空间复杂度：O(n + k)，out-place
稳定
优缺点
- 稳定，快，但是空间复杂度大
应用场景
计数排序虽然时间复杂度较低，但需要满足的条件较多，如果能满足限制条件与空间需求，计数排序自然很快。
9 计数排序
算法原理
- 找出数组中元素的最大值和最小值；
- 新建一个计数字典，把数组元素的值作为key，等于这个值的元素的个数作为value；
- 根据key从小到大遍历字典，将value个数的key放到数组中。
时间复杂度和空间复杂度
时间复杂度
最好的情况：O(n + k)
最坏的情况：O(n + k)
平均：O(n + k)
空间复杂度：O(k)，out-place
稳定
优缺点
- 稳定，快，但是空间复杂度大
应用场景
计数排序虽然时间复杂度较低，但需要满足的条件较多，如果能满足限制条件与空间需求，计数排序自然很快。
10 桶排序
算法原理
- 设置若干个桶，把符合的元素放入桶中；
- 桶内排序；
- 把结果复制回数组中。
时间复杂度和空间复杂度
时间复杂度
最好的情况：O(n + k)
最坏的情况：O(n^2)
平均：O(n + k)
空间复杂度：O(n + k)，out-place
稳定
优缺点
- 稳定，快，但是空间复杂度大
应用场景
如果满足桶排序的假设条件，即均匀分布，那么桶排序的速度是非常快的。
总结
- 基于比较的排序算法
- 简单排序：适用于数据量小的序列
- 插入：基本有序时，性能比较好。O(n)
- 选择：不稳定。当数据量很大时，选择排序性能会更好。
- 冒泡：基本有序时，性能比较好。O(n)
- nlogn时间复杂度
- 快排：内部排序，对随机分布数据时间最短。不稳定。空间复杂度O(log n)。
- 堆：空间复杂度比快排小O(1)，没有快排的最坏情况。不稳定。
- 归并：稳定，没有快排的最坏情况，但是空间复杂度为O(n)。
- 希尔：最差情况多。
- 简单排序：适用于数据量小的序列
- 线性时间排序算法：如果满足了线性时间排序算法的限制条件，使用线性时间排序将会使排序性能得到极大提升。
- 计数排序：表现最好，只能处理范围内的正整数。
- 桶排序：
- 基数排序
参考
1.0 十大经典排序算法 | 菜鸟教程 (runoob.com)
Go排序算法及其性能比较 - 基数排序 - 《Go学习手册（For learning Go Tutorial）》 - 书栈网 · BookStack
图解排序算法(三)之堆排序 - dreamcatcher-cx - 博客园 (cnblogs.com)
https://blog.csdn.net/Hairy_Monsters/article/details/80154391