目录
1.排序的稳定性
2.直接插入排序的特性总结
3.希尔排序的特性总结
4.直接选择排序的特性总结
5.堆排序的特性总结
6.冒泡排序的特性总结
7.快速排序的特性总结
8.归并排序的特性总结
9.计数排序的特性总结
10.总结
1.排序的稳定性
排序的稳定性是说 相同大小的元素在排序后的相对位置不发生改变
例如，
一种排序只要能保证数据稳定性，我们就说它是稳定的
排序稳定性在多字段排序、数据去重、数据库查询等场景中，能确保结果符合预期且可预测
2.直接插入排序的特性总结
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定
当元素等于前一个元素时，可选择将该元素放置到前一个元素后，此时可保证排序稳定
3.希尔排序的特性总结
1. 希尔排序是对直接插入排序的优化
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定
所以只记结论，时间复杂度为O(N*logN)，约为 (n^1.25) 到 (1.6*n^1.25)
4. 稳定性：不稳
希尔排序是通过分组排序和缩小增量的操作实现数组有序的，那么相同大小的数组难免被分到不同的组中，排序后难以保证相对位置的稳定
4.直接选择排序的特性总结
1. 直接选择排序思考非常好理解，但是效率不是很好，实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
如上，2的相对位置发生了改变，直接选择排序不能保证稳定
5.堆排序的特性总结
1. 堆排序使用堆来选数，效率就高了很多
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
这个大堆排升序后，9的相对位置发生改变，不稳定
6.冒泡排序的特性总结
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定
当某元素等于后一元素时，不交换，就可以保证排序的稳定性
7.快速排序的特性总结
hoare版本
前后指针版本
挖坑法
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
如上，快排是不稳定的，与关键值相同的元素可能有多个
8.归并排序的特性总结
1. 归并的缺点在于需要O(N)的空间复杂度
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
只需要让相对位置在前的相等大小的元素先归并，即可达到排序稳定
9.计数排序的特性总结
1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限
2. 时间复杂度：O(MAX(N,范围))
3. 空间复杂度：O(范围)
4. 稳定性：稳定
顺序计数，反向填充写(覆盖写)就可以实现稳定排序
10.总结
快排： 初始顺序影响较大，有序是性能最差
插入: 接近有序，性能最好
希尔：希尔是对插入排序的优化，这种优化是在无序的序列中才有明显的效果，如果序列接近有序，反而是插入最优。
堆排，归并，选择对初始顺序不敏感
次序列接近有序，所以如果是插入排序，时间复杂度逼近O(n)
快排： 逼近O(n^2)
归并和堆排仍然是nlogn
