排序
本章在选择题中会考察，在大题中也可能会基于本章的排序算法思想出一道相关的代码题。需要熟练掌握各个排序算法的过程，并且能够手写快速排序的代码。
## 排序
### 排序的基本概念
### 内部排序
- 直接插入排序
- 折半插入排序
- 冒泡排序
- 简单选择排序
- 希尔排序
- 快速排序
- 堆排序
- 二路归并排序
- 基数排序
### 外部排序
### 排序算法的分析
比较排序时的五个维度
遇到排序选择题或算法设计题，建议同时检查 比较次数、移动/交换次数、稳定性、辅助空间和输入特征：
- 稳定性只讨论关键字相等元素的相对次序；一次交换是否跨过相同关键字，决定算法是否稳定。
- 时间复杂度要区分最好、平均、最坏情况。快速排序的分区是否均衡、插入排序的初始有序程度都会改变实际代价。
- 空间复杂度除辅助数组外还要考虑递归栈；归并排序和快速排序的空间来源不同。
- 非比较排序依赖关键字范围或位数等额外条件；桶排序、基数排序不能在任意比较模型下突破下界。
- 外部排序的瓶颈常是读写外存，不应只按内存中的比较次数评价。
写算法时先说明升序或降序、下标范围和稳定性要求；完成后用一组含重复关键字的短序列检查边界和相对次序，往往能及时发现分区或归并条件写反的问题。