经典排序算法：快速排序 (Quick Sort)

什么是快速排序？

快速排序是另一种基于分治思想的排序算法。它通过一个“基准”(pivot)元素将数组分区，然后递归地对基准左右两边的子数组进行排序。

算法步骤

1. 选择基准 (Pivot): 从数组中选择一个元素作为基准。
2. 分区 (Partition): 重新排列数组，所有比基准小的元素都移动到基准的左边，所有比基准大的元素都移动到右边。
3. 递归 (Recurse): 递归地对基准左右两边的子数组进行快速排序。

代码实现 (C++)

#include <vector>
#include <algorithm> // For std::swap

// 分区函数
int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素为基准
    int i = (low - 1);

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

// 快速排序主函数
void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

复杂度分析

• 时间复杂度:
  • 平均情况: O(n log n)。
  • 最坏情况: O(n²)，当数组已经有序或接近有序，且每次都选择最大或最小元素作为基准时发生。
• 空间复杂度: O(log n)，递归栈的深度。
• 稳定性: 快速排序是不稳定的排序算法。