- 思想：分而治之
- 如果局部序列天然有序，则不进行分解
- 任意选取一个元素，排序后，所有比它小的都在它的前面，所有比它大的都在它的后面
- 用同样的方法，对该元素的前后子序列进行排序
- 选取一个元素，以序列头元素为例，作为中轴
- 序列头有一个从左向右扫描的指针i，序列尾有一个从右向左扫描的指针j
- 双向扫描，直到i遇到比中轴大的元素，j遇到比中轴小的元素，交换两个元素
- 继续扫描，直到 i > j ，把中轴与A[j]交换
- 当序列本身有序时，性能会退化到
- 当子序列较短的时候，例如只有三个数，再使用快速排序，增加两个指针，过于麻烦
- 增加选择的随机性，让中轴不至于一直是序列中最小或最大的数
- 当子序列已经比较短时，不继续使用快速排序，而是调用简单的排序算法
- 选取一定的间隔，如5，将第1、6、11，第2、7、12，......，每组元素分别排序
- 缩短间隔，按照同样的方法重新排序
- 当间隔较短时，使用插入排序即可
