快速排序 (Quicksort)

快速排序（Quicksort）是一种非常高效的、基于比较的、就地（in-place）排序算法。它由东尼·霍尔（Tony Hoare）在1959年发明，是目前使用最广泛的排序算法之一。

核心思想：分治 (Divide and Conquer)

快速排序的核心思想是“分治法”。它将一个大数组不断地分割成越来越小的子数组，然后分别对子数组进行排序，最终使得整个数组有序。

这个过程主要分为三步：

  1. 选择基准 (Pivot): 从数组中挑选一个元素，这个元素被称为“基准”或“枢轴”。
  2. 分区 (Partition): 重新排列数组。将所有小于基准的元素移动到基准的左侧，所有大于基准的元素移动到基准的右侧（等于的可以放在任意一侧）。完成分区后，这个基准元素就处在它在排序后数组中的最终位置。
  3. 递归 (Recurse): 递归地对基准左侧的子数组和基准右侧的子数组重复上述过程。

当一个子数组的大小为 0 或 1 时，它自然就是有序的，递归就停止了。

算法步骤详解

假设我们要对数组 arr 从索引 low 到 high 的部分进行排序：

  1. 选择基准 (Pivot):
    • 选择一个基准 pivot。最简单的策略是选择 arr[high]（最后一个元素）作为基准。其他策略还有选择第一个元素、中间元素或随机选择一个元素（随机选择可以有效避免最坏情况）。
  2. 分区 (Partition):
    • 这是快速排序最关键的一步。目标是找到基准 pivot 在排好序后应该在的“正确位置” pi。
    • 我们使用一个指针 i 来追踪“小于 pivot”区域的边界。
    • 遍历从 low 到 high-1 的所有元素（j）。
    • 如果 arr[j] 小于 pivot，我们就把 i 向右移动一位，并交换 arr[i] 和 arr[j]。这相当于把小的元素 arr[j] 扔到了“小于”区域。
    • 遍历结束后，[low...i] 区域的所有元素都小于 pivot。
    • 最后，我们将基准 pivot（即 arr[high]）与 arr[i+1] 交换。
    • 现在，arr[i+1] 就是基准 pivot，它左边的都比它小，右边的都比它大。我们返回这个索引 pi = i + 1。
  3. 递归 (Recurse):
    • 得到了基准的最终位置 pi 后，原问题被分成了两个子问题：
    • 递归调用 quickSort(arr, low, pi - 1) 来排序左侧的子数组。
    • 递归调用 quickSort(arr, pi + 1, high) 来排序右侧的子数组。

性能分析

时间复杂度

  • 平均情况 (Average Case): $O(n \log n)$
    • 在平均情况下，每次分区都能把数组大致分成两个大小相近的子数组。解决一个大小为 $n$ 的问题需要 $O(n)$ 的分区时间，和解决两个大小为 $n/2$ 的子问题的时间。
  • 最坏情况 (Worst Case): $O(n^2)$
    • 当数组已经完全有序（或逆序），并且你每次都选择第一个或最后一个元素作为基准时，就会发生最坏情况。
    • 这时，每次分区都会产生一个 $0$ 个元素的子数组和一个 $n-1$ 个元素的子数组。递归树会变得极度不平衡，深度为 $n$，导致总时间复杂度变为 $O(n^2)$。
    • （解决方法：随机选择基准，或者使用“三数取中”法。）

空间复杂度

  • 平均情况: $O(\log n)$
    • 空间复杂度主要由递归调用栈的深度决定。平均情况下，递归树的深度为 $O(\log n)$。
  • 最坏情况: $O(n)$
    • 在最坏情况下（如上所述），递归树的深度为 $O(n)$。

稳定性

  • 快速排序是一种 不稳定 的排序算法。
  • 在分区过程中，相等元素的相对顺序可能会被改变。例如，数组 [5a, 3, 5b, 2]（5a 和 5b 值相等但为了区分做了标记），如果选择 3 作为基准，5a 和 5b 的顺序不会变。但如果选择 2，5a 和 5b 的顺序也不会变。但如果选择 5a 作为基准，5b 可能会被交换到 5a 的前面。

C++ 实现

下面是使用 C++ (std::vector) 实现的快速排序，采用了 Lomuto 分区方案（Lomuto partition scheme），即选择最后一个元素作为基准。

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <vector>
#include <algorithm> // 用于 std::swap

/**
 * @brief 分区函数 (Lomuto partition scheme)
 * * 这个函数接收最后一个元素作为基准(pivot)，
 * 将 pivot 放置到它在排序后数组中的正确位置。
 * 所有比 pivot 小的元素都在它左边，所有比它大的都在右边。
 *
 * @param arr 要排序的数组
 * @param low 起始索引
 * @param high 结束索引 (pivot 所在位置)
 * @return int 基准(pivot)最终的位置索引
 */
int partition(std::vector<int>& arr, int low, int high) {
    // 1. 选择最后一个元素作为基准 (pivot)
    int pivot = arr[high];
    
    // i 是 "小于 pivot" 区域的最后一个元素的索引
    // 初始化为 low - 1，表示 "小于" 区域开始时为空
    int i = (low - 1); 

    // 2. 遍历从 low 到 high-1 的元素
    for (int j = low; j <= high - 1; j++) {
        // 3. 如果当前元素(arr[j])小于基准(pivot)
        if (arr[j] < pivot) {
            // "小于" 区域向右扩展一位
            i++; 
            // 将这个小元素(arr[j])换到 "小于" 区域的末尾
            std::swap(arr[i], arr[j]);
        }
    }
    
    // 4. 遍历结束后, [low...i] 都是比 pivot 小的元素
    //    [i+1...high-1] 都是比 pivot 大或等于的元素
    //    此时 i+1 是 pivot 应该在的正确位置
    //    将 pivot (arr[high]) 与 arr[i+1] 交换
    std::swap(arr[i + 1], arr[high]);
    
    // 5. 返回 pivot 的最终索引
    return (i + 1);
}

/**
 * @brief 快速排序主函数 (递归)
 *
 * @param arr 要排序的数组
 * @param low 子数组的起始索引
 * @param high 子数组的结束索引
 */
void quickSort(std::vector<int>& arr, int low, int high) {
    // 递归的基例：当子数组有 0 或 1 个元素时，low >= high
    if (low < high) {
        
        // 1. 进行分区，找到基准的正确位置 pi
        int pi = partition(arr, low, high);

        // 2. 递归地对基准左侧的子数组进行排序
        quickSort(arr, low, pi - 1);
        
        // 3. 递归地对基准右侧的子数组进行排序
        quickSort(arr, pi + 1, high);
    }
}

/**
 * @brief 辅助函数：打印 vector
 */
void printVector(const std::vector<int>& arr) {
    for (int val : arr) {
        std::cout << val << " ";
    }
    std::cout << std::endl;
}

// 主函数：用于测试
int main() {
    std::vector<int> arr = {10, 7, 8, 9, 1, 5, 3, 6, 4, 2};
    int n = arr.size();
    
    std::cout << "Original array: \n";
    printVector(arr);
    
    // 调用快速排序
    // 注意：对整个数组排序，high 应该是 n - 1
    quickSort(arr, 0, n - 1);
    
    std::cout << "\nSorted array: \n";
    printVector(arr);
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <vector>

int partition(vector<int> &arr,int low,int high){
	int pi = arr[low];
	

}

void quicksort(vector<int> &arr,int low,int high){
	

}