排序算法

基本概念： 将杂乱无章的数据元素，通过一定的方法（排序算法）按关键字（k）顺序排列的过程叫做排序。

比较类和非比较类

根据元素是否依靠与其他元素的比较来决定元素间的相对次序。以此来区分比较类排序算法和非比较类排序算法。

待排序中可能存在两个或两个以上的关键字相等，排序结果可能会存在不唯一的情况。排序之后，如果相等元素之间原有的先后顺序不变。则称所用的排序方法是稳定的，反之则称为不稳定的。

例：

排序算法	最坏时间	平均时间复杂度	稳定性	空间复杂度
插人排序	$O(n^2)$		稳定	$O(1)$
选择排序			不稳定
冒泡排序			稳定
希尔排序	$O(n^s)$ ,1<s<2,取决于增量序列	$O(n log_2 n)$	不稳定
快速排序	$O(n^2)$	指数阶	$O(n log_2 n)$	不稳定
堆排序	$O(n log n)$			不稳定
归并排序	$O(n log n)$			稳定