常用排序算法总结
- 排序算法的分类
- 常用排序算法复杂度及稳定性
-
- 时间性能
- 空间性能
- 稳定性
- 算法特点
-
- 插入排序
- 交换排序：
- 选择排序
- 归并排序
- 基数排序
- 面试考点
-
- 算法改进
-
- 冒泡排序
- 快速排序
- 选择排序算法准则
说明：本博客适合复习《数据结构》时阅读。
排序算法的分类
比较类，非比较类
常用排序算法复杂度及稳定性
时间性能
平均的时间性能
时间复杂度为 O(nlogn) ：快速排序、堆排序和归并排序
时间复杂度为 O(n^2 ) ：直接插入、冒泡和简单选择排序
时间复杂度为 O(n) : 基数排序
当待排记录序列按关键字顺序有序时
直接插入和冒泡排序：O(n)
快速排序：O(n^2) 。
原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。
空间性能
所有的简单排序方法(直接插入、起泡和简单选择) 和堆排序的空间复杂度为 O(1) ；
快速排序为 O(logn)，为递归程序执行过程中，栈所需的辅助空间 ；
归并排序所需辅助空间最多，其空间复杂度为O(n);
链式基数排序需附设队列首尾指针 ， 则空间复杂度为 O(rd) 。
稳定性
排序算法的稳定性:若待排序的序列中，存在多个具有相同关键字的记录，经过排序，这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对次序发生了改变，则称该算法是不稳定的。
稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序
算法特点
插入排序
包括直接插入排序 ， 二分插入排序 ，希尔排序
直接插入排序：对于有 n 个数据元素的待排序序列，n - 1 次数据比较 ，最好情况 0 次数据移动 （待排序的数据已经有序）。
注意：当 n<16（一说是n<8） 时 ， 直接插入比 O(nlogn) 的排序方法快。
二分插入排序： 用二分查找方法找出应该插入的位置； 二分插入排序减少了关键字的比较次数 ，但数据元素的移动次数不变 ， 其时间复杂度与直接插入排序相同。
希尔排序：设定增量作为距离，按照相同距离分组，对每组进行插入排序。减小增量，重复上述步骤。
综上，插入排序对基本已经排好序的列表有较好的时间复杂度。
交换排序：
包括冒泡排序 ， 快速排序。
快速排序：顾名思义。找到基准元素，遍历列表，大于或等于基准元素的放在基准元素的后面，小于基准元素的放在基准元素的前面。确定基准元素的位置之后，利用分治的思想快排基准元素前后的两个子列。
基准元素的选取：快排不稳定，贸然选择数组第一个元素可能导致最坏结果（如果排序记录基本有序，选择的元素恰为最小元素，时间复杂度o(n^2)）。因此可以选择第一个数据元素、最后一个数据元素、中间位置的数据元素的中位数。
选择排序
包括简单选择排序，堆排序。
简单选择排序：适用于待排序元素较少的情况。
堆排序：大顶堆和小顶堆，本身是一棵完全二叉树。
ps：堆排序涉及到了树的相关知识，比较难理解，附上某位前辈的链接：友情链接
归并排序
多为二路归并排序。
二路归并排序： 分而治之，一趟归并的时间复杂度为 O(n)， 总共需进行 log2n 趟。
基数排序
包括计数排序，桶排序，基数排序，是根据关键字本身的性质进行排序，不通过待排序数据元素之间的比较。
桶排序：每个数据元素关键字的值将其分配到相应的桶中，要求关键字的取值范围已知。
基数排序：“ 分配 ” 时，按当前“关键字位”所取值，将记录分配到不同的“桶”中，每个队列“桶”中记录的 “关键字位” 相同；“ 收集 ”时，按当前关键字位取值从小到大将各“桶”首尾相链成一个链表。对每个关键字位均重复上两步。
“ 分配 ”和“ 收集 ”的实际操作仅为修改链表中的指针和设置队列的头、尾指针；
面试考点
除了比较基本的各个排序算法的定义、特点，时间复杂度和空间复杂度分析以外，还经常考察算法的使用场景，算法的改进方法等。
算法改进
冒泡排序
方法1：设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。
方法2：设置布尔变量isSorted作为标记。如果在本轮排序中，元素有交换，则说明数列无序；如果没有元素交换，说明数列已然有序，直接跳出大循环。
方法3：双向冒泡排序。
这里再推荐一篇博文:友情链接
快速排序
可参考STL中的sort()函数：数据量n<8时采用插入排序，n>=8时采用快速排序。
选择排序算法准则
一般而言，需要考虑的因素有以下四点：
设待排序元素的个数为n.
1）当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。
2）当n较大，内存空间允许，且要求稳定性：归并排序
3）当n较小，可采用直接插入或直接选择排序。
直接插入排序：当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。
直接选择排序 ：元素分布有序，如果不要求稳定性，选择直接选择排序
5）一般不使用或不直接使用传统的冒泡排序。
6）基数排序是一种稳定的排序算法，但有一定的局限性：
1、关键字可分解。
2、记录的关键字位数较少，如果密集更好
3、如果是数字时，最好是无符号的