C++快速排序代码实现及解析

快速排序（QuickSort）是一种高效的排序算法，它采用分而治之的策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。快速排序由C. A. R. Hoare在1960年提出，该算法采用的策略可以称作是分治法（Divide and Conquer）的一个例子。 快速排序算法的步骤可以概括为以下几点： 1. 选择基准值（Pivot）：从数列中挑选出一个元素作为基准值。不同的选取方式会得到不同的算法变体，例如，最简单的选择第一个元素或最后一个元素作为基准值。 2. 分割（Partition）：重新排列序列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆放在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。 3. 递归排序子序列：递归地（recursive）把小于基准值元素的子序列和大于基准值元素的子序列排序。 4. 基准值归位：在排序完成以后，基准值所在的位置就是整个序列排序完成后的正确位置。 在C++中，快速排序算法的实现示例代码可以如下所示： ```cpp #include <iostream> #include <vector> void quickSort(std::vector<int>& arr, int left, int right) { if (left >= right) return; int pivot = arr[left]; // 基准值 int i = left, j = right; while (i < j) { // 从右向左找小于基准值的数 while (i < j && arr[j] >= pivot) j--; // 从左向右找大于基准值的数 while (i < j && arr[i] <= pivot) i++; // 交换两个数的位置 if (i < j) std::swap(arr[i], arr[j]); } // 交换基准值到正确的位置 std::swap(arr[left], arr[i]); // 递归地对基准值左右两边的子数组进行快速排序 quickSort(arr, left, i - 1); quickSort(arr, i + 1, right); } int main() { std::vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}; quickSort(arr, 0, arr.size() - 1); for (int num : arr) { std::cout << num << " "; } std::cout << std::endl; return 0; } ``` 在上述代码中，`quickSort`函数是快速排序的核心实现，它接受一个整型数组的引用以及要排序的子数组的左右边界索引。`main`函数中定义了一个未排序的数组，并调用`quickSort`函数对其进行排序，排序完成后，遍历并打印出排序后的数组。 快速排序的平均时间复杂度为O(n log n)，在最坏的情况下（每次分割都产生极端不均匀的两个部分）时间复杂度会退化到O(n^2)。然而，在实际应用中，快速排序通常比其他O(n log n)算法更快，因为它的内部循环可以在大多数现代架构上很有效地运行。 快速排序算法有许多变体，例如随机选择基准值来减少算法在数组有序或逆序时的退化情况，三数取中法（median-of-three）选择基准值等。此外，还有基于快速排序原理的非递归实现，称为迭代快速排序。这些变体和技术都是为了解决快速排序中可能出现的性能瓶颈，提升算法在各种情况下的稳定性和效率。