排序

排序是指：给定 n 个整数，将它们按（非降）序排列。

排序算法大致可分为两类：

• 基于比较的排序（comparison based algorithm，C.B.A.）：归并排序、冒泡排序、快速排序、希尔排序，其时间复杂度的下限为 \(O(nlogn)\)
• 非基于比较的排序：桶排序、计数排序、基数排序

排序算法的稳定性（stability）指重复元素在输入、输出序列中的相对次序，是否保持不变？

• 稳定的排序：归并排序、插入排序、冒泡排序
• 不稳定的排序：快速排序、堆排序

输入含重复元素时，算法的稳定性是更为细致的要求。

排序算法多种多样，对于程序员来说，重点需要熟记归并排序、快速排序、堆排序和插入排序这四种。

各个排序的时间复杂度如下：