概述
本节对排序的介绍、复习，均以升序排序为例进行说明。
排序的稳定性
稳定的排序：排序前后含相同关键字的记录相对位置保持不变
不稳定的排序：排序前后含相同关键字的记录相对位置变化
内部排序和外部排序
内部排序，只使用计算机内存存放待排序记录。
外部排序，排序记录不能同时存放在计算机内存中，需要借助计算机外存。
排序方法效率分析
三个指标：
- 时间复杂度（比较次数和移动次数）
- 空间复杂度（附加存储空间）
- 稳定性
插入排序法
以直接插入排序为例进行说明。
排序思想
- 第一个记录看作有序
- 从第二个记录开始，按关键字大小将每一个记录插入到已排好序的序列中
- 一直进行到第n个记录
特点
- 每次排序从第二个记录开始
- 直接插入排序第i趟后，前i+1个记录一定有序
算法分析
- 当原序列呈正序排列时，最省时间
当原序列呈反序排列时，最费时间
最好情况下，比较次数为 n-1，无需移动；
最坏情况下，比较次数、移动次数均为 o(n^2)
直接插入排序是稳定的排序方法
折半插入排序
思想与直接插入排序类似，只不过，在查找插入位置时，使用了二分思想。
希尔排序
本质上也是一种插入排序，只不过需要多次进行插入排序。
- 需要确定增量d，然后每一次以不同的增量进行插入排序，直至最后一次排序的增量减为1，此时就是插入排序。
- 完成增量为d的排序后，序列以d为步长呈现有序特征。
起泡排序
冒泡排序一趟后，最大元素将位于它最终的位置上，即沉底（位于最后），以此类推。
快速排序
快速排序是对冒泡排序的改进。每次会找一个记录的关键字作为“枢轴”，比它小的位于其左侧，比它大的位于其右侧，使得排序一趟后，无序序列将被分为两个部分。
算法思路
分治思想，在一段序列上快速排序时，首先选定枢轴量，然后设置左右双指针，分别依次从最右、从最左开始，找出右边小于枢轴量的数，与枢轴量互换；找出左边大于枢轴量的数，与枢轴量互换；如此循环直至左指针不小于右指针。
算法特点
快速排序是一种不稳定的排序方法。
最好情况下时间复杂度为O(nlogn)，最坏情况下退化为冒泡排序，为O(n^2)
从空间复杂度看，快速排序是一个递归过程，因此需要一个栈的附加空间，其平均深度为O(logn)。
