快速排序与归并排序：两种高效排序算法的深度解析

排序算法是计算机科学中的基础内容，在日常开发中有着广泛应用。本文将深入探讨两种经典的高效排序算法：快速排序和归并排序，分析它们的工作原理、实现方式、时间复杂度以及适用场景。

快速排序 (Quick Sort)

快速排序由计算机科学家Tony Hoare于1960年提出，是一种分治法策略的排序算法。它的核心思想是”分而治之”，通过选择一个”基准”元素，将数组分为两部分，一部分所有元素都小于基准，另一部分所有元素都大于基准，然后递归地对这两部分进行排序。

快速排序的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def quick_sort(arr):
    """
    快速排序算法实现
    :param arr: 需要排序的列表
    :return: 排序后的列表
    """
    # 基本情况：如果列表长度小于等于1，则已经是排序好的
    if len(arr) <= 1:
        return arr
    
    # 选择基准元素（这里选择中间元素）
    pivot = arr[len(arr) // 2]
    
    # 分区：小于基准、等于基准、大于基准
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    # 递归排序并合并结果
    return quick_sort(left) + middle + quick_sort(right)

上面的实现采用了列表推导式，使代码更加简洁。实际应用中，为了减少内存开销，更常见的是采用原地(in-place)分区的方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
def quick_sort_in_place(arr, low=None, high=None):
    """
    原地快速排序实现
    :param arr: 需要排序的列表
    :param low: 排序起始索引
    :param high: 排序结束索引
    """
    # 初始化low和high参数
    if low is None:
        low = 0
    if high is None:
        high = len(arr) - 1
    
    # 基本情况：如果起始索引大于等于结束索引，则无需排序
    if low >= high:
        return
    
    # 分区操作，返回基准元素的最终位置
    pivot_index = partition(arr, low, high)
    
    # 递归排序基准元素左右两部分
    quick_sort_in_place(arr, low, pivot_index - 1)
    quick_sort_in_place(arr, pivot_index + 1, high)

def partition(arr, low, high):
    """
    分区操作
    :param arr: 要分区的列表
    :param low: 分区起始索引
    :param high: 分区结束索引
    :return: 基准元素的最终位置
    """
    # 选择最右边的元素作为基准
    pivot = arr[high]
    
    # i是小于基准区域的边界
    i = low - 1
    
    # 遍历数组，将小于基准的元素放到左边
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    # 将基准元素放到正确的位置
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

快速排序的特性

  1. 时间复杂度：

    • 平均情况：O(n log n)
    • 最坏情况：O(n²)（当输入数组已经排序或接近排序时）
    • 最好情况：O(n log n)

  2. 空间复杂度：

    • 递归实现：O(log n) ~ O(n)（取决于递归深度）
    • 原地实现：O(log n)（主要是递归调用栈的开销）

  3. 稳定性：不稳定排序（相等元素的相对顺序可能改变）

  4. 特点：

    • 实际应用中通常比其他O(n log n)算法快
    • 缓存友好，因为它具有良好的局部性
    • 对已经排序的数据性能较差，可以通过随机选择基准元素来改善
    • 不适合对链表进行排序

归并排序 (Merge Sort)

归并排序是另一种基于分治法的排序算法，由John von Neumann于1945年提出。它将数组分成两个 halves，分别对它们进行排序，然后将排序好的两半合并在一起。

归并排序的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def merge_sort(arr):
    """
    归并排序算法实现
    :param arr: 需要排序的列表
    :return: 排序后的列表
    """
    # 基本情况：如果列表长度小于等于1，则已经是排序好的
    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):
    """
    合并两个已排序的列表
    :param left: 第一个已排序列表
    :param right: 第二个已排序列表
    :return: 合并后的排序列表
    """
    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

归并排序也可以实现为原地排序，但实现较为复杂：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
def merge_sort_in_place(arr, left=None, right=None):
    """
    原地归并排序实现
    :param arr: 需要排序的列表
    :param left: 排序起始索引
    :param right: 排序结束索引
    """
    if left is None:
        left = 0
    if right is None:
        right = len(arr) - 1
    
    # 基本情况：如果起始索引大于等于结束索引，则无需排序
    if left < right:
        # 找到中间点
        mid = left + (right - left) // 2
        
        # 递归排序左半部分和右半部分
        merge_sort_in_place(arr, left, mid)
        merge_sort_in_place(arr, mid + 1, right)
        
        # 合并已排序的两部分
        merge_in_place(arr, left, mid, right)

def merge_in_place(arr, left, mid, right):
    """
    原地合并两个已排序的子数组
    :param arr: 包含两个已排序子数组的数组
    :param left: 第一个子数组的起始索引
    :param mid: 第一个子数组的结束索引
    :param right: 第二个子数组的结束索引
    """
    # 计算两个子数组的长度
    n1 = mid - left + 1
    n2 = right - mid
    
    # 创建临时数组
    L = [0] * n1
    R = [0] * n2
    
    # 复制数据到临时数组
    for i in range(n1):
        L[i] = arr[left + i]
    for j in range(n2):
        R[j] = arr[mid + 1 + j]
    
    # 原地合并临时数组到原数组
    i = j = 0
    k = left
    
    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1
    
    # 复制剩余元素
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1
    
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1

归并排序的特性

  1. 时间复杂度：

    • 平均情况：O(n log n)
    • 最坏情况：O(n log n)
    • 最好情况：O(n log n)

  2. 空间复杂度：

    • 标准实现：O(n)（需要额外的存储空间）
    • 原地实现：O(log n)（主要是递归调用栈的开销）

  3. 稳定性：稳定排序（相等元素的相对顺序保持不变）

  4. 特点：

    • 性能稳定，不受输入数据分布影响
    • 适合对链表进行排序
    • 需要额外的存储空间（除非使用复杂的原地实现）
    • 并行性好，可以很容易地并行化处理

快速排序与归并排序的对比

特性快速排序归并排序
平均时间复杂度O(n log n)O(n log n)
最坏时间复杂度O(n²)O(n log n)
空间复杂度O(log n) ~ O(n)O(n) 或 O(log n)
稳定性不稳定稳定
原地排序可以可以，但实现复杂
对缓存友好性好一般
对已排序数据性能差性能稳定
并行性一般好
实现复杂度较简单较复杂

总结与建议

  • 快速排序通常在实际应用中表现更好，因为它的缓存利用率高，并且不需要额外的大量内存。适合大多数一般情况的排序需求。

  • 归并排序的优势在于其稳定性和可预测的O(n log n)时间复杂度，适合对排序稳定性有要求的场景，或者处理链表排序。

在选择排序算法时，应根据具体的应用场景、数据特征和性能要求进行选择。在许多标准库中，会结合两种算法的优点，例如Java的Arrays.sort()对于原始类型使用双轴快速排序，对于对象类型使用归并排序（Java 7及之前）或TimSort（Java 8及之后）。