目录
- 前言
- 1. 直接插入排序
- 2. 折半插入排序
- 3. 希尔排序
- 5、交换排序
- 6、冒泡排序
- 8、快速排序
- 9、选择排序
- 简单选择排序
- 10、归并排序
前言
第八章知识小结
1. 直接插入排序
若出现各种可能排列的概率相同，则可取最好情况和最坏情况的平均情况。
平均情况比较次数和移动次数约为n2/4
时间复杂度为 o(n2)，空间复杂度为 o(1)
是一种稳定的排序方法
适用于：基本有序，元素较少。
2. 折半插入排序
折半插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列。
减少了比较次数，但没有减少移动次数
平均性能优于直接插入排序
时间复杂度为 o(n2)
空间复杂度为 o(1)
是一种稳定的排序方法
3. 希尔排序
基本思路：将整个待排记录序列分割成若干组，分别进行直接插入排序。
分组技巧：分组不是简单地“逐段分割”，而是将相隔某个增量dk的记录组成一个组。让增量dk逐趟缩短，（例如依次取5,3,1），直到dk＝1为止。
优点：
（1）小元素跳跃式前移
（2）最后一趟增量为1时，序列已基本有序
（3）平均性能优于直接插入排序
时间复杂度是n和d的函数：
O(n1.25）～O（1.6n1.25）—经验公式 空间复杂度为 o(1)
5、交换排序
基本思想：两两比较，如果发生逆序则交换位置，直到所有记录都排好序为止。
6、冒泡排序
冒泡排序：两两比较，若逆序则交换，小数如气泡一样上浮（左移），大数如石块一样下沉（右移）。
优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素； 一旦下趟没有交换，还可提前结束排序 时间复杂度为 o(n2) 空间复杂度为 o(1) 是一种稳定的排序方法
8、快速排序
(1)可以证明，最好情况下的时间复杂度为O(nlog2n) ,最坏情况下为O(n)，平均时间复杂度是O(nlog2n)。
(2)实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。
(3)快速排序是递归的，需要有一个栈存放每层递归调用时参数（新的low和high）。
(4)最大递归调用层次数与递归树的深度一致，因此，要求存储开销为 O(log2n) 。
(5)稳定性： 不稳定—可选任一元素为支点。
9、选择排序
简单选择排序
移动次数：最好情况：0。最坏情况：3(n-1) 时间复杂度：O(n²)；空间复杂度：O(1)
稳定 堆排序 什么是堆？ 如何建立堆？（此处不做总结，看书） 时间效率：O(nlog2n) 空间效率：O（1） 稳 定 性：不稳定 适用于n 较大的情况 基本思想：每一趟从待排序的记录中选出关键字最小的记录，按顺序放在已经排好序的记录序列的后面。
10、归并排序
归并：将两个或两个以上的有序表组合成一个新有序表 时间效率：O(nlog2n) 空间效率：O（n) 稳 定 性：稳定
