排序算法小结

排序是工作和生活中非常常见的一个问题。现在已经有比较成熟的排序技术，被广泛地应用于各种程序语言或数据库中。不同的排序算法有不同的性能和适用场景，下面的视频对比了 9 种排序算法的性能表现。排序算法依次为选择排序、希尔排序、插入排序、归并排序、快速排序、堆排序、冒泡排序、梳排序、鸡尾酒排序。

九种排序算法的可视化及比较

冒泡排序

冒泡排序（Bubble Sort）是一种交换排序，基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

在最好的情况下，也就是数列本身是排好序的，需要进行 n – 1 次比较；在最坏的情况下，也就是数列本身是逆序的，需要进行 n(n-1)/2 次比较。因此冒泡排序总的时间复杂度是 O(n^2)。

选择排序

选择排序(Selection sort) 的基本思想是每一趟在 n – i + 1 (i = 1,2,***,n – 1)个记录中选取关键字最小(或最大)的记录作为有序序列的第 i 个记录，直到所有元素排序完成。选择排序是不稳定的排序算法。

选择排序的时间复杂度为 O(n^2)，但性能上略优于冒泡排序。

插入排序

插入排序类似于整理扑克牌，基本操作是将一个记录插入到已经排好序的有序数列中，从而得到一个有序但记录数加一的有序数列。

插入排序的时间复杂度为 O(n^2)，是稳定的排序方法，适用于数量较少的排序。

鸡尾酒排序

鸡尾酒排序是冒泡排序的一种变形。先找到最小的数字，放在第一位，再找到最大的数字放在最后一位。然后再找到第二小的数字放到第二位，再找到第二大的数字放到倒数第二位。以此类推，直到完成排序。

鸡尾酒排序的时间复杂度为 O(n^2)。

希尔排序

希尔排序(Shell Sort)是插入排序的一种，是针对直接插入排序算法的改进。基本思想是将相距某个增量 d 的记录组成一个子序列，通过插入排序使得这个子序列基本有序，然后减少增量继续排序。

操作上先取一个小于 n 的整数 d1 作为第一个增量，把全部记录分成 d1 个组，所有距离为 dl 的倍数的记录放在同一个组中。先在各组内进行直接插人排序，然后取第二个增量d2 < d1 重复上述的分组和排序，直至所取的增量 dt = 1 (dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

希尔排序的时间复杂度可以达到 O(n^(3/2))，要好于前面几种算法。

梳排序

梳排序和希尔排序很类似。希尔排序是在直接插入排序的基础上做的优化，而梳排序是在冒泡排序的基础上做的优化，也就是将相距某个增量 d 的记录组成一个子序列，通过冒泡排序使得这个子序列基本有序，然后减少增量继续排序。

梳排序的时间复杂度是 O(nlogn)。

归并排序

归并排序(MERGE-SORT) 是一种分治算法，是建立在归并操作上的一种有效的排序算法。常用的 2 路归并排序假设初始序列有 n 个记录，可以看成是 n 个长度为 1 的子序列，进行两两归并，可以得到 n / 2 个长度为 2 或 1 的子序列；再两两归并，******，直到得到一个长度为 n 的有序序列为止。

归并排序的时间复杂度是 O(nlogn)，是一种效率高且稳定的算法。

快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是通过一趟排序将待排记录分割成独立的两部分，其中一部分的记录都比另一部分小，然后再分别对这两个部分进行快速排序，最终实现整个序列的排序。

快速排序的时间复杂度为 O(nlogn)，是一种不稳定的排序算法；

堆排序

堆是具有下列性质的完全二叉树：

1. 每个节点的值都大于或等于其左右孩子节点的值，称为大顶堆；

2. 每个节点的值都小于或等于其左右孩子节点的值，称为小顶堆。

堆排序（Heap sort）是指利用堆这种数据结构所设计的一种排序算法。基本思想是把待排序的序列构造成一个大顶堆，此时序列的最大值就是队顶元素，把该元素放在最后，然后对剩下的 n – 1 个元素继续构造大顶堆，直到排序完成。

堆排序的时间复杂度为 O(nlogn)，由于要构造堆，因此不适用于序列个数较少的情况。