排序算法——快速排序

快速排序是计算机科学中最著名和广泛使用的排序算法之一。自1960年由英国计算机科学家托尼·霍尔（Tony Hoare）发明以来，它以其高效率和简洁的实现而闻名。在本文中，我们将深入探讨快速排序的工作原理、其优缺点，并提供一个用C++编写的实现示例。

工作原理

快速排序是一种“分而治之”的算法。它的核心思想是选取一个元素作为“基准”（pivot），然后将数组分为两部分，使得左边的元素都比基准小，右边的元素都比基准大。这个过程称为“分区”（partitioning）。之后，算法递归地在左右两个子数组上重复这个过程，直到整个数组排序完成。

分区操作

分区是快速排序中最关键的步骤。选择一个元素作为基准值，然后对数组进行重排，使得所有小于基准值的元素都在其左侧，所有大于基准值的元素都在其右侧。基准值在这个过程中会被放置在其最终位置上。

递归排序

一旦完成分区操作，基准值就位于其最终位置。这时，可以递归地对基准值左侧和右侧的子数组执行相同的操作，直到子数组的大小缩减到1或0，这时数组就被认为是排序完成的。

实现示例（C++）

下面是一个用C++编写的快速排序的简单实现。这个实现使用了“Lomuto分区方案”，其中基准值选为子数组的最后一个元素。

#include <iostream>
#include <vector>

using namespace std;

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivot = arr[high];
        int i = low;

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

        quickSort(arr, low, i - 1);
        quickSort(arr, i + 1, high);
    }
}

int main() {
    vector<int> arr = {10, 7, 8, 9, 1, 5};
    quickSort(arr, 0, arr.size() - 1);

    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}

优缺点

优点

1. 效率：在平均情况下，快速排序的时间复杂度为O(n log n)，这使得它在多数情况下非常高效。
2. 就地排序：快速排序不需要额外的存储空间，它是一种就地排序算法。
3. 适应性：对于大型数据集，快速排序通常比其他O(n log n)复杂度的排序算法表现得更好。

缺点

1. 最坏情况性能：在最坏情况下（如输入数组已排序或反向排序），快速排序的时间复杂度降至O(n^2)。
2. 不稳定：快速排序不是一个稳定的排序算法，这意味着相等元素的初始顺序可能在排序后被改变。