排序算法

type

status

date

slug

summary

定义

排序算法（英语：Sorting algorithm）是一种将一组特定的数据按某种顺序进行排列的算法。排序算法多种多样，性质也大多不同。

性质

稳定性

稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。

拥有稳定性这一特性的算法会让原本有相等键值的纪录维持相对次序，即如果一个排序算法是稳定的，当有两个相等键值的记录R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。

稳定排序：基数排序、计数排序、插入排序、冒泡排序、归并排序

不稳定排序：选择排序、堆排序、快速排序、希尔排序

时间复杂度

时间复杂度用来衡量一个算法的运行时间和输入规模的关系，通常用O表示。

简单计算复杂度的方法一般是统计「简单操作」的执行次数，有时候也可以直接数循环的层数来近似估计。

时间复杂度分为最优时间复杂度、平均时间复杂度和最坏时间复杂度。我们更主要关注最坏时间复杂度。

空间复杂度

与时间复杂度类似，空间复杂度用来描述算法空间消耗的规模。一般来说，空间复杂度越小，算法越好。

总结

下面是各种排序算法的比较

排序算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性
选择排序法				不稳定
冒泡排序法				稳定
插入排序法				稳定
合并排序法				稳定
希尔排序法				不稳定
快速排序法				不稳定
桶排序				稳定
堆排序法				不稳定
计数排序法				稳定
基数排序法				稳定

1.选择排序

选择排序（selection sort）就是反复从未排序的序列中取出最小（或最大）的值，加入另一个数列中，最后的结果即为已排列好的数列。

代码

下面均以升序排序做示例。

C++

Python

2.冒泡排序

冒泡排序（bubble sort）是模仿水中气泡上浮过程而创造的排序方法。

基本方法：每次检查相邻两个元素，如果前面的元素与后面的元素满足给定的排序条件，就将相邻两个元素交换。当没有相邻的元素需要交换时，排序就完成了。

以递增序列为例：从第一个数开始，依次比较相邻的两个数，将小的放前面，大的放后面，经过一轮比较，最大的数将位于最后一个位置。然后开始第二轮比较，将第二大的数放在倒数第二个位置。如此往复，直到所有数都完成排序。

冒泡排序交换数据的次数就是数列的逆序对的个数。

由于冒泡排序写法较多，不在此一一展示。

优化

我们发现，如果某轮“冒泡”中没有执行任何交换操作，说明数组已经完成排序，可直接返回结果。因此，可以增加一个标志位flag来监测这种情况，一旦出现就立即返回。

3.插入排序

插入排序（insertion sort）是将待排列元素划分为”已排序“和”未排序“两部分，每次从“未排序的”元素中选择一个插入到“已排序”的元素中的正确位置。

其实就把他想象成打扑克牌时，从桌面上抓一张牌插入手上的牌中，再去抓下一张就好了。

代码

python：

C++：

4.归并排序（合并排序）

归并排序法（merge sort），首先将无需的数列分成若干个小份，分若干份的规则就是不断把每段长度（对半分），直到不能再分为止（当数列中只有一个元素时视为不可再分），然后对最小份进行排序，最后再逐步合并成一个有序的大数列。

归并排序是求逆序对的重要方法！！！

代码

C++

Python

上实战：https://www.luogu.com.cn/problem/P1908?contestId=141690

5.希尔排序

希尔排序是插入排序的一中高级改进版本。希尔排序可以减少插入排序中数据的的移动次数，加快排序进程，因此又被称为缩小增量排序。

基本方法：将原始数据分成几个特定间隔的数据，然后使用插入排序对每组数据进行排序，排序后在减小间隔距离，重复插入法对数据排序，直到所有数据完成排序为止。

说明：间隔位数可以根据需求而定，不一定非要为2。

代码

python：

以下均以python做示例。

6.快速排序

快速排序（quick sort）又称分割交换法，是对冒泡排序的一种改进。快速排序是一种基于分治策略的排序算法，运行高效，应用广泛，在Python和C++中都有封装好的函数，大多数题目都可以直接使用。

基本方法：现在数据中找一个虚拟中间值，并按此虚拟中间值将打算排序的数据分为两部分。其中，小于中间值的数据放左边，大于中间值的数据放右边。再用相同的方法处理左右两边数据，直到排序完成为止。

代码

虽然直接使用sort( )函数很方便，但是我们还是应该掌握快速排序的写法，这种思想有时候十分重要，在直接使用快速排序会超时的时候，我们可以更具题目来考虑时候可以更具快速排序的原理简化过程。

上实战：https://www.luogu.com.cn/problem/P1923

快排为什么快？

出现最差情况的概率很低：虽然快速排序的最差时间复杂度为，没有归并排序稳定，但在绝大多数情况下，快速排序能在的时间复杂度下运行。

缓存使用效率高：在执行哨兵划分操作时，系统可将整个子数组加载到缓存，因此访问元素的效率较高。而像“堆排序”这类算法需要跳跃式访问元素，从而缺乏这一特性。

复杂度的常数系数低：在上述三种算法中，快速排序的比较、赋值、交换等操作的总数量最少。这与“插入排序”比“冒泡排序”更快的原因类似。

优化

基准数优化

快速排序在某些输入下的时间效率可能降低。举一个极端例子，假设输入数组是完全倒序的，由于我们选择最左端元素作为基准数，那么在哨兵划分完成后，基准数被交换至数组最右端，导致左子数组长度为，右子数组长度为0。如此递归下去，每轮哨兵划分后的右子数组长度都为0，分治策略失效，快速排序退化为“冒泡排序”。

为了尽量避免这种情况发生，我们可以优化哨兵划分中的基准数的选取策略。例如，我们可以随机选取一个元素作为基准数。然而，如果运气不佳，每次都选到不理想的基准数，效率仍然不尽如人意。

需要注意的是，编程语言通常生成的是“伪随机数”。如果我们针对伪随机数序列构建一个特定的测试样例，那么快速排序的效率仍然可能劣化。

为了进一步改进，我们可以在数组中选取三个候选元素（通常为数组的首、尾、中点元素），并将这三个候选元素的中位数作为基准数。这样一来，基准数“既不太小也不太大”的概率将大幅提升。当然，我们还可以选取更多候选元素，以进一步提高算法的稳健性。采用这种方法后，时间复杂度劣化至的概率大大降低。

尾递归优化

在某些输入下，快速排序可能占用空间较多。以完全倒序的输入数组为例，由于每轮哨兵划分后右子数组长度为0，递归树的高度会达到，此时需要占用大小的栈帧空间。

为了防止栈帧空间的累积，我们可以在每轮哨兵排序完成后，比较两个子数组的长度，仅对较短的子数组进行递归。由于较短子数组的长度不会超过，因此这种方法能确保递归深度不超过，从而将最差空间复杂度优化至。

7.堆排序

堆排序（heap sort）是一种基于堆数据结构实现的高效排序算法。堆是一个接近二叉树的结构，同时满足堆积的性质，即子节点的键值或索引总是小于（或者大于）他的父节点。

在此我们不进行过多介绍。

8.桶排序

桶排序（英文：Bucket sort）是排序算法的一种，适用于待排序数据值域较大但分布比较均匀的情况。

考虑一个长度为 𝑛 的数组，元素是范围 [0, 1) 的浮点数。如图

1. 初始化 𝑘 个桶，将 𝑛 个元素分配到 𝑘 个桶中。

2. 对每个桶分别执行排序。

3. 按照桶的从小到大的顺序，合并结果。

如何实现平均分配

为实现平均分配，我们可以先设定一个大致的分界线，将数据粗略地分到3个桶中。分配完毕后，再将商品较多的桶继续划分为3个桶，直至所有桶中的元素数量大致相等。

如果我们提前知道商品价格的概率分布，则可以根据数据概率分布设置每个桶的价格分界线。值得注意的是，数据分布并不一定需要特意统计，也可以根据数据特点采用某种概率模型进行近似。

9.计数排序

技术额排序（counting sort）通过统计元素数量来实现排序，通常应用于整数数组。

计数排序和桶排序的联系

从桶排序的角度看，我们可以将计数排序中的计数数组 counter 的每个索引视为一个桶，将统计数量的过程看作是将各个元素分配到对应的桶中。本质上，计数排序是桶排序在整型数据下的一个特例。

局限性

计数排序只适用于非负整数。

计数排序适用于数据量大但数据范围较小的情况。如果数据范围过大，会占用过多空间。

10.基数排序

基数排序（radix sort）的核心思想与计数排序一致，也通过统计个数来实现排序。在此基础上，基数排序利用数字各位之间的递进关系，依次对每一位进行排序，从而得到最终的排序结果。

为什么从最低位开始

在连续的排序轮次中，后一轮排序会覆盖前一轮排序的结果。举例来说，如果第一轮排序结果，而第二轮排序结果，那么第二轮的结果将取代第一轮的结果。由于数字的高位优先级高于低位，我们应该先排序低位再排序高位。

局限性

相较于计数排序，基数排序适用于数值范围较大的情况，但前提是数据必须可以表示为固定位数的格式，且位数不能过大。例如，浮点数不适合使用基数排序，因为其位数过大，可能导致时间复杂度。