跳转至

排序与搜索

概述

排序和搜索是最基本的算法问题。排序将无序数据组织为有序序列，搜索在数据集中高效定位目标元素。理解各种排序算法的特性是算法学习的重要基础。

1. 比较排序

1.1 下界定理

定理：任何基于比较的排序算法在最坏情况下至少需要 \(\Omega(n \log n)\) 次比较。

证明思路：\(n\) 个元素有 \(n!\) 种排列，决策树至少需要 \(\lceil \log_2(n!) \rceil\) 个叶子，由 Stirling 近似：

\[ \log_2(n!) = n \log_2 n - n \log_2 e + O(\log n) = \Omega(n \log n) \]

1.2 冒泡排序（Bubble Sort）

反复交换相邻的逆序元素。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr
  • 最好：\(O(n)\)（已排序，提前终止）
  • 最坏/平均：\(O(n^2)\)
  • 稳定排序，原地排序

1.3 选择排序（Selection Sort）

每次从未排序部分选择最小元素放到已排序部分末尾。

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr
  • 所有情况：\(O(n^2)\)
  • 不稳定排序，原地排序
  • 交换次数最少：\(O(n)\)

1.4 插入排序（Insertion Sort）

将每个元素插入到已排序部分的正确位置。

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr
  • 最好：\(O(n)\)（已排序）
  • 最坏/平均：\(O(n^2)\)
  • 稳定排序，原地排序
  • 对小规模数据或近乎有序的数据非常高效

1.5 归并排序（Merge Sort）

分治策略：递归地将数组分成两半，排序后合并。

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

递推关系：\(T(n) = 2T(n/2) + O(n)\)

  • 所有情况：\(O(n \log n)\)
  • 稳定排序
  • 额外空间：\(O(n)\)

1.6 快速排序（Quick Sort）

分治策略：选择pivot，将数组分为小于和大于pivot的两部分。

def quicksort(arr, lo, hi):
    if lo < hi:
        p = partition(arr, lo, hi)
        quicksort(arr, lo, p - 1)
        quicksort(arr, p + 1, hi)

def partition(arr, lo, hi):
    pivot = arr[hi]
    i = lo
    for j in range(lo, hi):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]
    return i
  • 平均：\(O(n \log n)\)
  • 最坏：\(O(n^2)\)（已排序数组选首/尾为pivot）
  • 不稳定排序，原地排序
  • 实践中常是最快的通用排序算法

随机化快排：随机选择pivot，期望时间 \(O(n \log n)\)。

1.7 堆排序（Heap Sort）

利用最大堆数据结构。

def heapsort(arr):
    n = len(arr)
    # 建堆
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # 逐步取出最大元素
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

def heapify(arr, n, i):
    largest = i
    left, right = 2 * i + 1, 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
  • 所有情况：\(O(n \log n)\)
  • 不稳定排序，原地排序
  • 建堆：\(O(n)\)

2. 非比较排序

2.1 计数排序（Counting Sort）

适用于整数且值域有限的情况。

def counting_sort(arr, max_val):
    count = [0] * (max_val + 1)
    for x in arr:
        count[x] += 1
    result = []
    for val, cnt in enumerate(count):
        result.extend([val] * cnt)
    return result
  • 时间：\(O(n + k)\)，\(k\) 为值域大小
  • 空间：\(O(n + k)\)
  • 稳定排序

2.2 基数排序（Radix Sort）

从最低位到最高位，逐位使用稳定排序。

def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort_by_digit(arr, exp)
        exp *= 10
  • 时间：\(O(d \cdot (n + b))\)，\(d\) 为位数，\(b\) 为基数
  • 空间：\(O(n + b)\)
  • 稳定排序

2.3 桶排序（Bucket Sort）

将元素分配到若干桶中，桶内排序后合并。

  • 平均时间：\(O(n + k)\)（均匀分布时）
  • 最坏：\(O(n^2)\)（所有元素在同一桶）
  • 适用于均匀分布的浮点数排序

3. 排序算法比较

算法 最好 平均 最坏 空间 稳定 原地
冒泡排序 \(O(n)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\) 是 是
选择排序 \(O(n^2)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\) 否 是
插入排序 \(O(n)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\) 是 是
归并排序 \(O(n\log n)\) \(O(n\log n)\) \(O(n\log n)\) \(O(n)\) 是 否
快速排序 \(O(n\log n)\) \(O(n\log n)\) \(O(n^2)\) \(O(\log n)\) 否 是
堆排序 \(O(n\log n)\) \(O(n\log n)\) \(O(n\log n)\) \(O(1)\) 否 是
计数排序 \(O(n+k)\) \(O(n+k)\) \(O(n+k)\) \(O(n+k)\) 是 否
基数排序 \(O(dn)\) \(O(dn)\) \(O(dn)\) \(O(n+b)\) 是 否
桶排序 \(O(n+k)\) \(O(n+k)\) \(O(n^2)\) \(O(n+k)\) 是 否 
graph TD
    Q1{数据量大?} -->|否| INS[插入排序]
    Q1 -->|是| Q2{值域有限?}
    Q2 -->|是| COUNT[计数/基数排序]
    Q2 -->|否| Q3{需要稳定?}
    Q3 -->|是| MERGE[归并排序]
    Q3 -->|否| Q4{内存受限?}
    Q4 -->|是| HEAP[堆排序]
    Q4 -->|否| QUICK[快速排序]

4. 二分搜索

4.1 基本二分搜索

在有序数组中查找目标值。

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2  # 防止溢出
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
  • 时间：\(O(\log n)\)
  • 空间：\(O(1)\)

4.2 二分搜索变体

查找第一个等于target的位置：

def lower_bound(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

查找第一个大于target的位置：

def upper_bound(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo

在旋转排序数组中搜索：

def search_rotated(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        if arr[lo] <= arr[mid]:  # 左半有序
            if arr[lo] <= target < arr[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:  # 右半有序
            if arr[mid] < target <= arr[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

4.3 二分搜索的应用

应用 描述
有序数组查找 基本应用
求平方根 二分逼近 \(\sqrt{x}\)
最小化最大值 二分答案
分配问题 二分+贪心验证
查找峰值 山峰数组

二分搜索的思维框架

二分搜索不仅适用于"在有序数组中查找"，更广泛地适用于任何具有单调性的判定问题：如果答案为 \(x\) 时可行，那么答案为 \(x+1\) 时也可行（或反之）。这种"二分答案"的思想非常强大。

5. 其他搜索算法

5.1 插值搜索

对于均匀分布的数据，估计目标位置：

\[ \text{pos} = lo + \frac{(target - arr[lo]) \cdot (hi - lo)}{arr[hi] - arr[lo]} \]
  • 平均：\(O(\log \log n)\)（均匀分布）
  • 最坏：\(O(n)\)

5.2 指数搜索

先指数增长找到范围，再二分：

def exponential_search(arr, target):
    if arr[0] == target:
        return 0
    bound = 1
    while bound < len(arr) and arr[bound] <= target:
        bound *= 2
    lo = bound // 2
    hi = min(bound, len(arr) - 1)
    return binary_search_range(arr, target, lo, hi)
  • 时间：\(O(\log n)\)
  • 适用于无界或非常大的有序序列

6. 选择算法

6.1 第 \(k\) 小元素

快速选择（QuickSelect）：

def quickselect(arr, lo, hi, k):
    if lo == hi:
        return arr[lo]
    p = partition(arr, lo, hi)
    if k == p:
        return arr[p]
    elif k < p:
        return quickselect(arr, lo, p - 1, k)
    else:
        return quickselect(arr, p + 1, hi, k)
  • 平均：\(O(n)\)
  • 最坏：\(O(n^2)\)

中位数的中位数（Median of Medians）：

  • 将数组分为 \(\lceil n/5 \rceil\) 组，每组5个
  • 递归找到中位数的中位数作为pivot
  • 保证最坏情况 \(O(n)\)

参考资料

  • Cormen et al., Introduction to Algorithms (CLRS), Chapters 2, 6-9
  • Sedgewick, Algorithms

相关章节：

评论 #