十大排序简介

一、排序分类

按照排序的实现方式，十种排序算法可分为：
1．比较类排序：

• 交换类：冒泡排序、快速排序。
• 插入类：插入排序、希尔排序。
• 选择类：选择排序、堆排序。
• 归并类：归并排序。

2．非比较类排序：计数排序、桶排序、基数排序。

二、排序思路

以从小到大排序为例，各排序算法思路如下。

1．冒泡排序（Bubble Sort）

将列表分为两部分，左无序，右有序。遍历时比较相邻两元素，顺序不对就交换，每遍历一次就能将无序列表中的最大元素逐步“冒泡”到列表的末尾。这样重复遍历无序列表，就能实现整个列表的排序。
时间复杂度：O(n²)

2．选择排序（Selection Sort）

左无序，右有序。每次从无序列表中选择最大值，放在最后（交换）。
时间复杂度：O(n²)

3．插入排序（Insertion Sort）

左有序，右无序。将无序列表第一个元素往前移动，放在第一个比它小的数的后边，从而得到新的有序列表。
时间复杂度：O(n^2)（对于大部分情况），O(n) 在最佳情况下（数据已接近有序）

4．希尔排序（Shell Sort）

是插入排序的一种改进版本，通过先比较距离较远的元素，再逐步缩小间隔进行插入排序。
插入排序的增量可视为1，在某些极端情况下效率较差。而希尔排序改为设立增量序列，按增量序列执行多次插入排序。
希尔排序的时间复杂度与增量序列的选取有关，一般用n除以2一直除到1的序列，但不是最优算法。
时间复杂度：取决于间隔序列的选择，通常为 O(n7/6)。

5．归并排序（Merge Sort）

采用分治法，先分后合。即先将列表分成两半分别排序，再合并已排序的两部分。
时间复杂度：O(n log n)。
空间复杂度：O(n)（需要额外的存储空间用于合并）

6．快速排序（Quick Sort）

采用分治法，在列表中选择一个基准值，然后分区（将列表分割成两部分，比基准值小的放在左侧，大的放在右侧），然后递归每个分区（即按上面的方面此这两部分数据分别进行快速排序）。
快速排序的基准值选择不当可能导致时间复杂度退化，解决办法有随机选值（随机选取基准值）、三数取中（头尾中，三数取中间值作为基准值）等。
时间复杂度：O(n log n)（平均情况），O(n^2)（最坏情况，但可以通过随机选择基准元素等方法改进）

7．堆排序（Heap Sort）

将无序部分构建成一个大顶堆，然后依次堆顶元素（最大值）与末尾元素交换，并重新调整堆结构。算法类似于选择排序。
时间复杂度：O(n log n)
空间复杂度：O(1)（原地排序/就地排序）

8．计数排序（Counting Sort）

适用于一定范围内的整数排序，通过计数元素出现的次数来确定每个元素在排序后的位置。
具体方法是借助数组下标有序，先存入数组并统计个数，再遍历赋值回原数组。
时间复杂度：O(n + k)（k 是待排序数据的范围）
空间复杂度：O(k)

9．基数排序（Radix Sort）

按位（从最低有效位到最高有效位或从最高有效位到最低有效位）对数字进行排序，通常使用计数排序作为子过程。
从最低有效位到最高有效位的基数排序，可以设立0～9十个桶数组，将待排序数按个位放入桶中，依次拿出，再按十位、百位，重复上述过程。
时间复杂度：O(n * k)（k 是数字的最大位数）
空间复杂度：O(n + k)（取决于使用的计数排序的空间需求）

10．桶排序（Bucket Sort）

将待排序数据分到有限数量的桶中，每个桶再分别排序（通常使用其他排序算法），然后依次合并各个桶中的数据。
也就是说，通过映射函数将待排序数据分组，对每个组选择合适的排序算法排序后，遍历每个桶，依次赋值回原数组。
时间复杂度：O(n + k)（k 是桶的数量，且每个桶中的数据均匀分布）
空间复杂度：O(n + k)

三、 稳定性

排序前如果a等于b，a在b的前面，排序后a仍在b的前面，则称该排序算法稳定。
稳定排序：冒泡排序、插入排序、归并排序、计数排序、桶排序、基数排序。
不稳定排序：快速排序、堆排序、选择排序、希尔排序。
速记：不稳定的排序有“快选堆希(吸)”。想象眼前是一堆堆的饮料，快选一堆来吸。

四、时空复杂度

十大排序的时空复杂度列表如下：

n表示待排序数据规模，k表示待排序数据范围，对数以2为底。