排序算法

定义

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

性质

稳定性

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

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

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

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

时间复杂度

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

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

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

空间复杂度

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

总结

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

排序算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性
选择排序法	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
冒泡排序法	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
插入排序法	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
合并排序法	$O(n log n)$	$O(n log n)$	$O(n)$	稳定
希尔排序法	$O(n log n)$	$O(n^8)$	$O(1)$	不稳定
快速排序法	$O(n log n)$	$O(n^2)$	$O(log n)$	不稳定
桶排序	$O(n+k)$	$O(n^2)$	$O(n+k)$	稳定
堆排序法	$O(n log n)$	$O(n log n)$	$O(1)$	不稳定
计数排序法	$O(n+k)$	$O(n+k)$	$O(k)$	稳定
基数排序法	$O(n+k)$	$O(n*k)$	$O(n+k)$	稳定

排序算法

1.选择排序

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

代码

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

C++

void choose(vector<int> &data)
{
    int n=data.size();
    for (int i=0;i<n-1;i++)
    {
        for (int j=i+1;j<n;j++)
        {
            if (data[i]<data[j])
            {
                swap(data[i],data[j]);
            }
        }
    }
}

Python

def choose(data):
    for i in range(len(data) - 1):
        for j in range(i + 1, len(data)):
            if data[i] < data[j]:
                data[i], data[j] = data[j], data[i]

2.冒泡排序

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

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

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

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

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

优化

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

3.插入排序

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

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

代码

python：

def insertion_sort(data):
    # 外循环：已排序区间为 [0, i-1]
    for i in range(1, len(data)):
        base = data[i]
        j = i - 1
        # 内循环：将 base 插入到已排序区间 [0, i-1] 中的正确位置
        while j >= 0 and data[j] > base:
            data[j + 1] = data[j] # 将 nums[j] 向右移动一位
            j -= 1
        data[j + 1] = base # 将 base 赋值到正确位置

C++：

void insertionSort(vector<int> &nums) 
{
    // 外循环：已排序元素数量为 1, 2, ..., n
    for (int i = 1; i < nums.size(); i++)
    {
        int base = nums[i], j = i - 1;
        // 内循环：将 base 插入到已排序部分的正确位置
        while (j >= 0 && nums[j] > base)
        {
            nums[j + 1] = nums[j]; // 将 nums[j] 向右移动一位
            j--;
        }
        nums[j + 1] = base; // 将 base 赋值到正确位置
    }
}

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

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

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

代码

C++

int res[500010]={0};
int temp[500010]={0};
long long sum=0; //逆序对个数
void msort(int l,int r) //l和r为待排序数组的左右边界
{
    if (l<r)    //划分
    {
        int mid=(l+r)/2;
        msort(l,mid);
        msort(mid+1,r);

        //开始合并
        int l1=l,r1=mid+1;
        int k=l;
        while (l1<=mid && r1<=r)
        {
            if (res[l1]<=res[r1])
            {
                temp[k]=res[l1];
                k++;l1++;
            }
            else
            {
                temp[k]=res[r1];
                k++;r1++;
                sum=sum+mid-l1+1; //此处计算逆序对
            }
        }

        //合并多余元素
        while (l1<=mid)
        {
            temp[k]=res[l1];
            k++;l1++;
        }
        while (r1<=r)
        {
            temp[k]=res[r1];
            k++;r1++;
        }

        //储存临时数组
        for(int i=l;i<=r;i++)
        {
            res[i]=temp[i];
        }
        return;
    }
    else return;
}

Python

def msort(data):    #本函数中未进行逆序对的统计，可自行添加，方法如上
    if len(data) <= 1:
        return data
    mid = len(data) / 2
    left = data[:mid]
    right = data[mid:]

    left = msort(left)
    right = msort(right)
    #开始合并
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop[0])
        else:
            result.append(right.pop[0])
    if left:
        result += left
    if right:
        result += right
    return result

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

5.希尔排序

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

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

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

代码

python：

def hill(data):
    n = len(data)
    step = n // 2
    while step >= 1:  #步长从大变小，最后一步必须是1
        for j in range(step, n):
            while j - step >= 0:
                if data[j] < data[j - step]:
                    data[j], data[j - step] = data[j - step], data[j]
                    j -= step
                else:
                    break
        step //= 2

以下均以python做示例。

6.快速排序

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

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

代码

def partition(self, nums: list[int], left: int, right: int) -> int:
    """ 哨兵划分"""
    # 以 nums[left] 作为基准数
    i, j = left, right
    while i < j:
        while i < j and nums[j] >= nums[left]:
            j -= 1 # 从右向左找首个小于基准数的元素
        while i < j and nums[i] <= nums[left]:
            i += 1 # 从左向右找首个大于基准数的元素
        # 元素交换
        nums[i], nums[j] = nums[j], nums[i]
    # 将基准数交换至两子数组的分界线
    nums[i], nums[left] = nums[left], nums[i]
    return i # 返回基准数的索引

def quick_sort(self, nums: list[int], left: int, right: int):
    """ 快速排序"""
    # 子数组长度为 1 时终止递归
    if left >= right:
        return
    # 哨兵划分
    pivot = self.partition(nums, left, right)
    # 递归左子数组、右子数组
    self.quick_sort(nums, left, pivot - 1)
    self.quick_sort(nums, pivot + 1, right)

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

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

快排为什么快？

• 出现最差情况的概率很低：虽然快速排序的最差时间复杂度为 $𝑂(𝑛^2)$ ，没有归并排序稳定，但在绝大多数情况下，快速排序能在 $𝑂(𝑛 log 𝑛)$ 的时间复杂度下运行。
• 缓存使用效率高：在执行哨兵划分操作时，系统可将整个子数组加载到缓存，因此访问元素的效率较高。而像“堆排序”这类算法需要跳跃式访问元素，从而缺乏这一特性。
• 复杂度的常数系数低：在上述三种算法中，快速排序的比较、赋值、交换等操作的总数量最少。这与“插入排序”比“冒泡排序”更快的原因类似。

优化

1. 基准数优化

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

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

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

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

def median_three(self, nums: list[int], left: int, mid: int, right: int) -> int:
    """ 选取三个元素的中位数"""
    # 此处使用异或运算来简化代码
    # 异或规则为 0 ^ 0 = 1 ^ 1 = 0, 0 ^ 1 = 1 ^ 0 = 1
    if (nums[left] < nums[mid]) ^ (nums[left] < nums[right]):
        return left
    elif (nums[mid] < nums[left]) ^ (nums[mid] < nums[right]):
        return mid
    return right
def partition(self, nums: list[int], left: int, right: int) -> int:
    """ 哨兵划分（三数取中值）"""
    # 以 nums[left] 作为基准数
    med = self.median_three(nums, left, (left + right) // 2, right)
    # 将中位数交换至数组最左端
    nums[left], nums[med] = nums[med], nums[left]
    # 以 nums[left] 作为基准数
    i, j = left, right
    while i < j:
        while i < j and nums[j] >= nums[left]:
            j -= 1 # 从右向左找首个小于基准数的元素
        while i < j and nums[i] <= nums[left]:
            i += 1 # 从左向右找首个大于基准数的元素
        # 元素交换
        nums[i], nums[j] = nums[j], nums[i]
    # 将基准数交换至两子数组的分界线
    nums[i], nums[left] = nums[left], nums[i]
    return i # 返回基准数的索引

1. 尾递归优化

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

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

def quick_sort(self, nums: list[int], left: int, right: int):
    """ 快速排序（尾递归优化）"""
    # 子数组长度为 1 时终止
    while left < right:
        # 哨兵划分操作
        pivot = self.partition(nums, left, right)
        # 对两个子数组中较短的那个执行快排
        if pivot - left < right - pivot:
            self.quick_sort(nums, left, pivot - 1) # 递归排序左子数组
            left = pivot + 1 # 剩余未排序区间为 [pivot + 1, right]
        else:
            self.quick_sort(nums, pivot + 1, right) # 递归排序右子数组
            right = pivot - 1 # 剩余未排序区间为 [left, pivot - 1]

7.堆排序

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

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

8.桶排序

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

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

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

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

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

def bucket_sort(nums: list[float]):
    """ 桶排序"""
    # 初始化 k = n/2 个桶，预期向每个桶分配 2 个元素
    k = len(nums) // 2
    buckets = [[] for _ in range(k)]
    # 1. 将数组元素分配到各个桶中
    for num in nums:
        # 输入数据范围 [0, 1)，使用 num * k 映射到索引范围 [0, k-1]
        i = int(num * k)
        # 将 num 添加进桶 i
        buckets[i].append(num)
    # 2. 对各个桶执行排序
    for bucket in buckets:
        # 使用内置排序函数，也可以替换成其他排序算法
        bucket.sort()
    # 3. 遍历桶合并结果
    i = 0
    for bucket in buckets:
        for num in bucket:
            nums[i] = num
            i += 1

如何实现平均分配

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

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

9.计数排序

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

def counting_sort_naive(nums: list[int]):
    """ 计数排序"""
    # 简单实现，无法用于排序对象
    # 1. 统计数组最大元素 m
    m = 0
    for num in nums:
        m = max(m, num)
    # 2. 统计各数字的出现次数
    # counter[num] 代表 num 的出现次数
    counter = [0] * (m + 1)
    for num in nums:
        counter[num] += 1
    # 3. 遍历 counter ，将各元素填入原数组 nums
    i = 0
    for num in range(m + 1):
        for _ in range(counter[num]):
            nums[i] = num
            i += 1

计数排序和桶排序的联系

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

局限性

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

10.基数排序

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

def digit(num: int, exp: int) -> int:
    """ 获取元素 num 的第 k 位，其中 exp = 10^(k-1)"""
    # 传入 exp 而非 k 可以避免在此重复执行昂贵的次方计算
    return (num // exp) % 10

def counting_sort_digit(nums: list[int], exp: int):
    """ 计数排序（根据 nums 第 k 位排序）"""
    # 十进制的位范围为 0~9 ，因此需要长度为 10 的桶
    counter = [0] * 10
    n = len(nums)
    # 统计 0~9 各数字的出现次数
    for i in range(n):
        d = digit(nums[i], exp) # 获取 nums[i] 第 k 位，记为 d
        counter[d] += 1 # 统计数字 d 的出现次数
    # 求前缀和，将“出现个数”转换为“数组索引”
    for i in range(1, 10):
        counter[i] += counter[i - 1]
    # 倒序遍历，根据桶内统计结果，将各元素填入 res
    res = [0] * n
    for i in range(n - 1, -1, -1):
        d = digit(nums[i], exp)
        j = counter[d] - 1 # 获取 d 在数组中的索引 j
        res[j] = nums[i] # 将当前元素填入索引 j
        counter[d] -= 1 # 将 d 的数量减 1
    # 使用结果覆盖原数组 nums
    for i in range(n):
        nums[i] = res[i]

def radix_sort(nums: list[int]):
    """ 基数排序"""
    # 获取数组的最大元素，用于判断最大位数
    m = max(nums)
    # 按照从低位到高位的顺序遍历
    exp = 1
    while exp <= m:
        # 对数组元素的第 k 位执行计数排序
        # k = 1 -> exp = 1
        # k = 2 -> exp = 10
        # 即 exp = 10^(k-1)
        counting_sort_digit(nums, exp)
        exp *= 10

为什么从最低位开始

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

局限性

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