排序算法

1. 排序算法分类

常见排序算法可以分为两大类：

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

2. 常见排序算法

a. 冒泡排序

顾名思义：像冒泡一样将最大（小）数从左向右慢慢浮动到顶端。

b. 选择排序

顾名思义：每轮选择出最小（大）值来完成排序。例如，第一轮选择出全局第一小的数据放置在第一个位置（通过与第一个位置的数据交换实现），第二轮则排除第一个位置已经选择出的数据，选择后面最小的的数据放置在第二个位置，以此类推。

c. 插入排序

顾名思义：每轮通过向前插入到合适的位置以形成前置有序，遍历完成后全局有序。

d. 归并排序

顾名思义：归并排序就是每次合并时进行排序，不断合并直到最后一次合并达到全局有序。具体来说是通过分治法实现，要先将整个序列分成最小段才能进行合并排序操作。

e. 快速排序

快速排序，顾名思义，主打的就是一个快！具体来说，通过每轮设置一个key值（通常直接选择最左边的元素），每轮遍历过程中都能将key值放置在排序后的最终位置（因为key将数据分成了两部分，一部分比key小，一部分比key大）。每个key划分成左右两部分数据，如图所示。第一轮划分成左右两部分子序列，第二轮则继续对左右子序列进行划分，以此类推。

---

十大经典排序算法（动图演示） - 一像素 - 博客园