算法学习--3 （快速排序）

引言

快速排序（Quick Sort）是计算机科学中最流行的排序算法之一，它基于“分治”思想，通过递归地将数组分成两部分并分别排序，从而实现排序的目的。与冒泡排序和选择排序等简单算法相比，快速排序在平均情况下的性能非常优越，因此广泛应用于实际场景。

本文将详细介绍快速排序的工作原理、实现代码、时间复杂度分析及其优缺点。

快速排序的基本原理

快速排序的核心思想是：通过选取一个“基准”元素（pivot），将数组划分为两部分，一部分小于基准，另一部分大于基准。然后递归地对这两部分分别进行快速排序，最终达到整个数组有序。

快速排序的算法步骤

1. 从数组中选择一个元素作为基准（通常选取第一个、最后一个、中间一个或随机一个元素）。
2. 将数组分区：所有比基准小的元素放到基准的左边，所有比基准大的元素放到右边。
3. 递归地对基准左右两部分进行快速排序。
4. 重复步骤2和3，直到每个子数组都有序。

快速排序动画演示

快速排序的实现代码

下面是用C++实现的快速排序代码：

#include <iostream>
using namespace std;

// 分区函数，返回基准元素的正确位置
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准
    int i = (low - 1);  // i指向小于基准的最后一个元素

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

// 快速排序主函数
void quickSort(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);  // 对基准右边排序
    }
}

// 打印数组
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "排序前的数组: ";
    printArray(arr, n);
    quickSort(arr, 0, n - 1);
    cout << "排序后的数组: ";
    printArray(arr, n);
    return 0;
}

时间复杂度分析

快速排序在大多数情况下表现非常高效。它通过递归地将数组分成两半，平均情况下每次都能将问题规模减半。因此，快速排序的平均时间复杂度为 O(n log n)。

• 最坏情况：当每次划分的结果极为不平衡时，快速排序会退化为 O(n²) 的复杂度。最典型的例子是每次选择的基准都是数组的最大或最小值，这样每次递归只减少一个元素的规模。
• 最好情况：在每次划分都能将数组等分时，快速排序的复杂度为 O(n log n)，这是其平均情况的复杂度。

优化策略

为了避免快速排序在最坏情况下退化，可以采用以下优化策略：

• 随机选取基准：通过随机选取基准元素，可以减少每次都选到最差基准的概率。
• 三数取中：选取第一个、最后一个和中间元素的中位数作为基准，可以有效避免数组初始状态有序时的最坏情况。

快速排序的优缺点

优点：

• 平均时间复杂度低：快速排序的平均时间复杂度为 O(n log n)，对于大多数实际问题表现非常高效。
• 原地排序：快速排序的空间复杂度为 O(log n)，因为它只需要一个额外的栈空间用于递归，不需要额外的数组来存储数据。
• 应用广泛：快速排序广泛应用于许多编程语言的标准库中，如C++的 std::sort() 函数背后实现的就是快速排序。

缺点：

• 最坏时间复杂度高：在最坏情况下，时间复杂度会退化为 O(n²)。
• 不稳定：快速排序不是稳定排序算法，即相同的元素在排序后相对位置可能发生变化。

适用场景

快速排序是一个通用的高效排序算法，适用于绝大多数情况下的数据排序。它在工程应用中非常普遍，尤其是在需要快速处理大量数据时。由于其原地排序的特性，快速排序在内存使用受限的情况下也具有优势。

总结

快速排序是一个高效的分治排序算法，它的平均时间复杂度为 O(n log n)，在实际应用中具有广泛的应用场景。通过合理选择基准元素，可以避免最坏情况的发生。尽管它不是稳定排序，但它的效率和简单实现让它成为实际编程中首选的排序算法之一。