快速排序：高效分治算法详解-洪萨配资

快速排序的基本概念

快速排序是一种高效的排序算法，采用分治策略对数据进行排序。其核心思想是通过一次排序将待排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据小，然后递归地对这两部分数据进行快速排序。

快速排序的平均时间复杂度为 O(n log n)，最坏情况下为 O(n²)，但由于其在实际应用中的高效性，成为最常用的排序算法之一。快速排序的实现依赖于分区（partition）操作，这是算法的关键步骤。

快速排序的实现步骤

快速排序的实现可以分为三个主要部分：选择基准值（pivot）、分区操作和递归排序。以下是详细说明：

选择基准值
基准值的选择直接影响快速排序的效率。常见的基准值选择方法包括：选择第一个元素、选择最后一个元素、选择中间元素或随机选择。随机选择基准值可以避免最坏情况的发生，提高算法的平均性能。

分区操作
分区操作的目标是将数组分为两部分，使得左边的元素都小于基准值，右边的元素都大于基准值。具体步骤如下：

初始化两个指针，左指针指向数组的起始位置，右指针指向数组的末尾。
左指针向右移动，直到找到一个大于基准值的元素。
右指针向左移动，直到找到一个小于基准值的元素。
交换这两个元素。
重复上述步骤，直到左指针大于或等于右指针。
最后将基准值与左指针所指的元素交换，完成分区。

递归排序
分区完成后，递归地对左右两个子数组进行快速排序，直到子数组的长度为1或0，此时数组已经有序。

C++实现快速排序

以下是一个完整的C++实现示例，包含详细的注释：

#include <iostream> #include <vector> #include <algorithm> // 用于swap函数 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; j++) { if (arr[j] < pivot) { 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) { 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}; int n = arr.size(); cout << "排序前的数组: "; printArray(arr); quickSort(arr, 0, n - 1); cout << "排序后的数组: "; printArray(arr); return 0; }

快速排序的优化

虽然快速排序在平均情况下表现优异，但在某些情况下（如数组已经有序或逆序）性能会下降。以下是几种常见的优化方法：

随机化基准值
通过随机选择基准值，可以避免最坏情况的发生。只需在分区函数中随机选择一个元素作为基准值即可。

int partitionRandom(vector<int>& arr, int low, int high) { int random = low + rand() % (high - low + 1); swap(arr[random], arr[high]); // 将随机选择的元素放到最后 return partition(arr, low, high); }

三数取中法
选择第一个、中间和最后一个元素的中位数作为基准值，可以减少不平衡分区的概率。

int medianOfThree(vector<int>& arr, int low, int high) { int mid = low + (high - low) / 2; if (arr[low] > arr[mid]) swap(arr[low], arr[mid]); if (arr[low] > arr[high]) swap(arr[low], arr[high]); if (arr[mid] > arr[high]) swap(arr[mid], arr[high]); return mid; } int partitionMedian(vector<int>& arr, int low, int high) { int median = medianOfThree(arr, low, high); swap(arr[median], arr[high]); return partition(arr, low, high); }

小数组使用插入排序
对于小规模数组（如长度小于10），插入排序的效率可能更高。可以在递归过程中对小数组使用插入排序。

void insertionSort(vector<int>& arr, int low, int high) { for (int i = low + 1; i <= high; i++) { int key = arr[i]; int j = i - 1; while (j >= low && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } } void optimizedQuickSort(vector<int>& arr, int low, int high) { if (high - low < 10) { insertionSort(arr, low, high); return; } int pi = partitionMedian(arr, low, high); optimizedQuickSort(arr, low, pi - 1); optimizedQuickSort(arr, pi + 1, high); }

快速排序的时间复杂度分析

快速排序的时间复杂度取决于分区操作的质量。以下是几种情况的分析：

最佳情况
每次分区都能将数组均匀分成两部分，递归树的深度为 log n，每层的时间复杂度为 O(n)，因此总时间复杂度为 O(n log n)。

最坏情况
每次分区都只能将数组分成一个元素和剩余部分，递归树的深度为 n，时间复杂度为 O(n²)。这种情况发生在数组已经有序或逆序时。

平均情况
通过随机化或优化基准值选择，快速排序的平均时间复杂度为 O(n log n)。

快速排序的空间复杂度

快速排序是原地排序算法，不需要额外的存储空间。但递归调用会使用栈空间，平均情况下栈空间复杂度为 O(log n)，最坏情况下为 O(n)。

快速排序的稳定性

快速排序不是稳定的排序算法。在分区过程中，相等的元素可能会被交换到不同的位置，导致相对顺序改变。

快速排序与其他排序算法的比较

与归并排序比较
归并排序的时间复杂度稳定为 O(n log n)，但需要额外的 O(n) 空间。快速排序在平均情况下性能更优，且是原地排序。

与堆排序比较
堆排序的时间复杂度为 O(n log n)，且不需要递归，但实际应用中快速排序通常更快，因为其常数因子较小。

与插入排序比较
插入排序在小规模数据或近乎有序的数据上表现更好，但时间复杂度为 O(n²)，不适合大规模数据。

快速排序的应用场景

快速排序适合用于大规模数据的排序，尤其是在内存中操作时。由于其高效的平均性能，快速排序被广泛应用于标准库的实现中，如C++的std::sort和Java的Arrays.sort。

快速排序的变种

双轴快速排序
Java的Arrays.sort在排序基本类型时使用了双轴快速排序，通过选择两个基准值将数组分成三部分，进一步提高了效率。

三路快速排序
针对包含大量重复元素的数组，三路快速排序将数组分成小于、等于和大于基准值的三部分，减少了重复元素的重复比较。

void threeWayQuickSort(vector<int>& arr, int low, int high) { if (high <= low) return; int lt = low, gt = high; int pivot = arr[low]; int i = low; while (i <= gt) { if (arr[i] < pivot) { swap(arr[lt++], arr[i++]); } else if (arr[i] > pivot) { swap(arr[i], arr[gt--]); } else { i++; } } threeWayQuickSort(arr, low, lt - 1); threeWayQuickSort(arr, gt + 1, high); }