快速排序（Quick Sort）的C++实现

1. 算法简介

快速排序是一种基于 分治法 的高效排序算法。通过选择一个“基准”（pivot），快速排序将序列分成两个子序列，分别递归地进行排序。在平均情况下，时间复杂度为 ( O(n \log n) )，且具有较小的常数因子，在实际中通常比其他排序算法更快。

2. 算法步骤

  1. 选择基准值（Pivot）: 通常选择序列中的第一个元素或中间元素作为基准值。
  2. 分区（Partitioning）: 将序列中的元素按照基准值划分成两部分：左侧部分小于基准值，右侧部分大于基准值。
  3. 递归调用: 对左侧和右侧的子序列分别进行快速排序。
  4. 结束条件: 当子序列的长度为1或0时，不再递归。

3. 代码实现

标准的递归实现：
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
#include <iostream>
#include <vector>

// 交换两个元素
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

// 分区函数，返回基准值的位置
int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[low];  // 基准值
    while (low < high) {
        // 从右向左找小于基准值的元素
        while (low < high && arr[high] >= pivot) {
            --high;
        }
        arr[low] = arr[high];  // 将小于基准值的元素移动到左侧

        // 从左向右找大于基准值的元素
        while (low < high && arr[low] <= pivot) {
            ++low;
        }
        arr[high] = arr[low];  // 将大于基准值的元素移动到右侧
    }
    arr[low] = pivot;  // 基准值归位
    return low;  // 返回基准值的位置
}

// 快速排序主函数
void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);  // 划分序列
        quickSort(arr, low, pivotIndex - 1);  // 递归排序左半部分
        quickSort(arr, pivotIndex + 1, high);  // 递归排序右半部分
    }
}

int main() {
    std::vector<int> arr = {29, 10, 14, 37, 13};
    quickSort(arr, 0, arr.size() - 1);
    
    std::cout << "排序结果: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    return 0;
}

4. 细节分析

  1. 选择基准值: 代码中选择了第一个元素作为基准值 pivot，在某些情况下（如已排序的数组）会导致最坏的时间复杂度 ( O(n^2) )。通过随机选择基准值或选择中间元素，可以提高算法在特定输入下的效率。

  2. 分区过程:

    • 从右向左找第一个小于基准值的元素，放在左侧；
    • 从左向右找第一个大于基准值的元素，放在右侧；
    • 这个过程不断交替进行，直到左右两侧交叉，最后将基准值归位。

  3. 递归调用: 快速排序通过递归实现对左右两个子序列的排序。由于每次递归调用的数组长度缩小，因此在平均情况下递归深度为 ( \log n )。

  4. 时间复杂度:

    • 最优时间复杂度: 当每次划分都非常均匀时，递归深度为 ( \log n )，每次分区的代价为 ( O(n) )，因此时间复杂度为 ( O(n \log n) )。
    • 最坏时间复杂度: 当数组已经有序或接近有序时，每次划分都导致极端不平衡的分区，递归深度为 ( O(n) )，时间复杂度为 ( O(n^2) )。

  5. 空间复杂度: 快速排序是 原地排序 算法，因此空间复杂度仅为递归调用时的栈空间，最优情况下为 ( O(\log n) )，最坏情况下为 ( O(n) )。

5. 迭代实现

使用递归容易导致栈溢出问题，在此基础上可以使用栈手动模拟递归过程，进行迭代实现。

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
#include <iostream>
#include <vector>
#include <stack>

struct Range {
    int start, end;
    Range(int s, int e) : start(s), end(e) {}
};

// 分区函数与递归版相同
int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= pivot) --high;
        arr[low] = arr[high];
        while (low < high && arr[low] <= pivot) ++low;
        arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
}

// 迭代实现的快速排序
void quickSortIterative(std::vector<int>& arr) {
    std::stack<Range> stack;
    stack.push(Range(0, arr.size() - 1));
    
    while (!stack.empty()) {
        Range range = stack.top();
        stack.pop();
        
        if (range.start < range.end) {
            int pivot = partition(arr, range.start, range.end);
            stack.push(Range(range.start, pivot - 1));
            stack.push(Range(pivot + 1, range.end));
        }
    }
}

int main() {
    std::vector<int> arr = {29, 10, 14, 37, 13};
    quickSortIterative(arr);
    
    std::cout << "排序结果: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    return 0;
}