当前位置：首页 > article >正文

C++算法深度解析：快速排序的实现、分析与优化

article 2025/3/31 0:06:06

引言

快速排序（Quick Sort）是一种广泛应用于各种编程场景的排序算法。它以其平均时间复杂度O(n log n)和空间复杂度O(log n)而著称，这使得它在处理大数据集时表现出色。本文将深入探讨快速排序的原理、实现、性能分析以及优化策略，并通过C++代码展示其实现过程。

快速排序的原理

快速排序的基本思想是通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

算法步骤

选择基准：从数列中挑出一个元素，称为"基准"（pivot）。
分区操作：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。
递归排序：递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

快速排序的C++实现

以下是快速排序的一个基本实现，使用了Lomuto分区方案。

#include <iostream>
#include <vector>
#include <algorithm> // 引入algorithm库，用于随机数生成

using namespace std;

// 快速排序的分区函数
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];    // 选择最后一个元素作为基准
    int i = (low - 1);  // i指向比基准小的区域

    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于或等于基准
        if (arr[j] <= pivot) {
            i++;    // i向前移动
            swap(arr[i], arr[j]);  // 交换元素
        }
    }
    swap(arr[i + 1], arr[high]);  // 将基准放到正确的位置
    return (i + 1);
}

// 快速排序函数
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        // pi是分区索引，arr[pi]是基准
        int pi = partition(arr, low, high);

        // 分别对基准左边和右边的子数组进行快速排序
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 打印数组
void printArray(const vector<int>& arr) {
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    vector<int> arr = {10, 7, 8, 9, 1, 5, 3, 2, 4, 6, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
    int n = arr.size();

    cout << "Original array: ";
    printArray(arr);

    quickSort(arr, 0, n - 1);

    cout << "Sorted array:   ";
    printArray(arr);

    return 0;
}

快速排序的性能分析

时间复杂度

平均情况：O(n log n)
最坏情况：O(n^2)，当每次分区都非常不平衡时（例如，数组已经有序或逆序）

空间复杂度

递归调用：O(log n)（递归深度）

快速排序的优化

虽然快速排序的平均性能很好，但在某些情况下，它的性能可能会下降到O(n^2)。以下是一些优化策略：

1. 选择更好的基准

三数取中法：取首元素、中间元素和尾元素，比较它们的大小，然后将中间大小的元素与尾元素交换。这样可以在一定程度上避免最坏情况的发生。
随机选择基准：随机选择基准元素可以减少数据已经有序或逆序时快速排序性能下降的问题。

2. 使用尾递归优化

在递归调用中，如果子问题的规模足够小，可以考虑使用尾递归优化来减少递归调用的开销。

3. 小数组使用插入排序

对于小规模的数组，插入排序可能比快速排序更高效。可以在数组规模小于某个阈值时切换到插入排序。

4. 避免递归调用

对于小规模的数组，可以使用迭代的方式来避免递归调用的开销。

优化后的快速排序实现

以下是优化后的快速排序实现，包括随机选择基准和使用尾递归优化。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;

// 快速排序的分区函数
int partition(vector<int>& arr, int low, int high) {
    if (low < high) {
        // 随机选择基准
        int pivotIndex = low + rand() % (high - low + 1);
        swap(arr[pivotIndex], arr[high]);

        int pivot = arr[high];
        int i = (low - 1);

        for (int j = low; j <= high - 1; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr[i], arr[j]);
            }
        }
        swap(arr[i + 1], arr[high]);
        return (i + 1);
    }
    return low;
}

// 快速排序函数
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        if (pi - low < high - pi) {
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        } else {
            quickSort(arr, pi + 1, high);
            quickSort(arr, low, pi - 1);
        }
    }
}

// 打印数组
void printArray(const vector<int>& arr) {
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    srand(time(0)); // 初始化随机数生成器

    vector<int> arr = {10, 7, 8, 9, 1, 5, 3, 2, 4, 6, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30};
    int n = arr.size();

    cout << "Original array: ";
    printArray(arr);

    quickSort(arr, 0, n - 1);

    cout << "Sorted array:   ";
    printArray(arr);

    return 0;
}