跳转至

线性时间排序

重点
  • 基于比较的排序算法下界；
  • 计数排序适应的排序对象、算法和时间；
  • 基数排序适应的排序对象、算法和时间；
  • 桶排序适应的排序对象、算法和时间。

排序算法的下界

比较排序可以抽象成一颗决策树：

graph TD;
    A((1:2)) --> B((2:3))
    A --> C((1:3))
    B --> D((<1,2,3>))
    B --> E((1:3))
    C --> F((<2,1,3>))
    C --> G((2:3))
    E --> H((<1,3,2>))
    E --> I((<3,1,2>))
    G --> J((<2,3,1>))
    G --> K((<3,2,1>))

在这棵决策树中，每个边表示一次比较操作（向左为 \(\leqslant\)，向右为 \(>\)），非叶节点表示比较的结果，叶子节点表示排序的最终结果。通过这种方式，我们可以分析比较排序的时间复杂度。

比较排序算法的下界

  • 在最坏情况下，任何比较排序算法都需要 \(\Omega(n \lg n)\) 次比较。
  • 堆排序和归并排序都是渐进最优的比较排序算法。

具体证明省略。

计数排序

假设输入的 \(n\) 个元素的值都在 \(0\) 到 \(k\) 之间，其中 \(k\) 是一个整数。计数排序的基本思想是：对每一个元素 \(x\)，确定小于 \(x\) 的元素的个数。利用这个信息，把它放到正确的位置上。

计数排序的时间复杂度为 \(O(n + k)\)，其中 \(n\) 是输入数组的大小，\(k\) 是输入元素的范围。当 \(k = \Theta(n)\) 时，排序运行时间为 \(\Theta(n)\)。

计数排序
1
2
3
4
5
6
7
8
9
def CountingSort(A, B, k):
    C = [0] * (k + 1)
    for j in range(len(A)):     # 计算每个元素 i 出现的次数
        C[A[j]] += 1
    for i in range(1, k + 1):   # 计算小于等于元素 i 的个数
        C[i] = C[i] + C[i - 1]
    for j in range(len(A) - 1, -1, -1):     # 倒序遍历 A
        B[C[A[j]] - 1] = A[j]               # 利用 C 的信息将 i 放到合适的位置
        C[A[j]] -= 1            # 更新 C，使得 A 中元素不互异时算法也能正常工作

计数排序是一种稳定的排序算法，适用于对整数进行排序，尤其是当整数的范围不大时，效率非常高。

基数排序

基数排序是一种非比较排序算法，适用于对整数进行排序。它的基本思想是将整数按位进行排序，从最低有效位到最高有效位，依次进行排序。

基数排序的时间复杂度为 \(O(d(n + k))\)，其中 \(d\) 是整数的位数，\(n\) 是输入数组的大小，\(k\) 是每个位的取值范围。

基数排序
1
2
3
4
5
def RadixSort(A, d):
    for i in range(1, d + 1):
        # 用一个稳定的排序算法排序 A 的第 i 位
        # 这里可以考虑用上面的计数排序
        pass

基数排序是一种稳定的排序算法，适用于对整数进行排序，尤其是当整数的位数较少时，效率非常高。

桶排序

桶排序是一种非比较排序算法，适用于均匀分布的实数排序。假设所有数据在区间 \([0, 1)\) 上，它的基本思想是将数组元素分配到有限数量的桶中，每个桶内分别进行排序，最后将各个桶中的元素合并得到有序数组。

桶排序的时间复杂度为 \(O(n + k)\)，其中 \(n\) 是输入数组的大小，\(k\) 是桶的数量。当输入数据均匀分布时，桶排序的平均时间复杂度为 \(O(n)\)。

桶排序
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def BucketSort(A):
    n = len(A)
    B = [[] for _ in range(n)]  # 创建 n 个空桶

    for i in range(n):
        index = int(n * A[i])   # 确定元素 A[i] 应该放入哪个桶
        B[index].append(A[i])

    for i in range(n):
        B[i].sort()             # 对每个桶内的元素进行排序

    result = []
    for i in range(n):
        result.extend(B[i])     # 将所有桶中的元素合并

    return result

桶排序是一种稳定的排序算法，适用于对实数进行排序，尤其是当输入数据均匀分布时，效率非常高。