第四章 排序算法

1. 常用算法

??根据时间复杂度的不同，主流的排序算法可以分为3大类。

1.1 时间复杂度为$O(n^2)$的排序算法

• 冒泡排序
• 选择排序
• 插入排序
• 希尔排序（希尔排序比较特殊，它的性能略优于$O(n^2)$，但右比不上$O(nlogn)$,姑且把它归入本类）

1.2 时间复杂度为$O(nlogn)$的排序算法

• 快速排序
• 归并排序
• 堆排序

1.3 时间复杂度为线性的排序算法

• 计数排序
• 桶排序
• 基数排序

??以上列举的只是最主流的排序算法，在算法界还存在着更多五花八门的排序，它们有些基于传统排序变形而来，有些则是脑洞打开，如鸡尾酒排序、猴子排序、睡眠排序等。
??此外，排序算法还可以根据其稳定性，划分为稳定排序和不稳定排序。
??既如果值相同的元素在排序后仍然保持着排序前的顺序，则这样的排序算法是稳定排序；如果值相同的元素在排序后打乱了排序前的顺序，则这样的排序算法是不稳定排序。例如下面的例子。