数据结构基础第8讲 排序
考点一：排序的概念和性能分析
1.排序的概念
-
稳定性
根据相对位置是否改变判断
-
内排序
2.排序的性能
考点二：插入类排序
1.直接插入排序
\(复杂度O(n^2)\)
3.折半插入排序
改进了比较次数
未改变移动次数，因此复杂度仍为\(O(n^2)\)
3.希尔排序
时间性能：
考点三：交换类排序
想要做分割
- 折半：要求数组且有序
- 快排：要求数组且无序
有序用二分，无序用快排
1.快速排序
对于二分找到中间就停止
快排在中间某个位置相遇就停止
算法分析：
考点四：选择类排序
1.简单选择排序
每次从无需序列中选择最小的和无序首元素交换
ex：
2.堆排序
- 小根堆：根小于左小于右
- 大根堆：根大于左大于右
步骤：
3.归并排序
\(时间O(n \log_2 n)\)
\(空间O(n)\)
考点六：基数排序
ex：
按个位分配到桶中
回收桶间按顺序，桶内按队列顺序
按十位
按百位
按千位
考点七：比较分析
