当前位置：首页 > news >正文

C++算法恢复训练之快速排序

news 2025/9/13 5:35:44

快速排序（Quick Sort）是一种基于分治思想的排序算法，它通过将待排序数组分成两个子数组，其中一个子数组的所有元素都比另一个子数组的元素小，然后对这两个子数组递归地进行排序，最终将整个数组排序。快速排序是一种原地排序算法，其时间复杂度为 $O (n l o g n)$ 。

下面是使用 C++ 实现的经典快速排序算法：

#include <vector>
#include <iostream>
using namespace std;int partitionSimple(vector<int>& array, int left, int right)
{if (left >= right){return -1;}// Use the value of index `right` as the pivotconst int pivot = array[right];int lessBound = left - 1;for (int i = left; i < right; i++){// If the current element is not more than then pivot value,// then swap it with the less part's next value, and make the less part add 1if (array[i] <= pivot){swap(array[i], array[++lessBound]);}}// At last, swap the pivot with the next element of less partswap(array[lessBound + 1], array[right]);return lessBound + 1;
}void quickSortSimple(vector<int>& array, int left, int right)
{if (left >= right){return;}const int pivotIndex = partitionSimple(array, left, right);quickSortSimple(array, left, pivotIndex - 1);quickSortSimple(array, pivotIndex + 1, right);
}void quickSort(vector<int>& array)
{quickSortSimple(array, 0, array.size() - 1);
}

经典快速排序的实现过程可以分为两个步骤：

分割子问题：选取一个元素作为基准值（pivot），将待排序数组分成两个子数组，一个子数组中的元素都小于等于基准值，另一个子数组中的元素都大于等于基准值。
合并解决方案：对两个子数组分别进行快速排序（递归），最后将两个已排序的子数组合并成一个有序数组。

递归的部分其实比较好理解和实现，那么现在可以将问题简化为：给定一个数组，和一个基准值，如何将小于等于基准值的元素放在数组左边，将大于基准值的元素放在数组右边？

我的实现思路是利用一个小于等于pivot值的边界的索引这样一个概念变量，对应代码中的lessBound，它对应的元素及其左边部分都小于等于pivot值。在随后的数组遍历过程中，如果遍历的元素满足这样的条件，则将该元素与lessbound的后一位对调，然后将lessbound的范围扩大一位。核心思路类似快慢指针：即lessbound扮演的是慢指针，i扮演的是快指针。

最后，数组已经被分成了两个子数组，其中一个子数组中的元素都小于等于基准值，另一个子数组中的元素都大于基准值。然后分别对这两个子数组进行递归。

快速排序的时间复杂度为 $O (n l o g n)$ ，其中 $n$ 是待排序数组的长度。快速排序每次将待排序数组分成两个子数组，其中一个子数组中的元素都小于等于基准值，另一个子数组中的元素都大于等于基准值。

由于快速排序每次都将待排序数组分成两个子数组，因此递归树的高度为 $l o g n$ 。每个节点所处理的子问题的规模最大为 $n$ ，因此快速排序的时间复杂度为 $O (n l o g n)$ 。

需要注意的是，在最坏情况下，快速排序的时间复杂度为 $O(n^2)$ ，此时待排序数组已经有序或者接近有序，且每次选取的基准值都是数组中的最小或最大元素。为了避免最坏情况的发生，可以采用以下优化措施：

随机选取基准值。
三数取中法（Median-of-three partitioning）：从子数组的左端、右端和中间位置分别选取一个元素，选择它们的中间值作为基准值。

除此以外，从算法本身出发，经典快排是利用某个值作为基准值，其算法实质在于一个周期内确定这个pivot的下标索引。从这点考虑，可以考虑在这个周期内将所有与pivot相等的值的位置都敲定，在递归时就不考虑这一批数。

C++相应的实现：


vector<int> partitionOptimized(vector<int>& array, int left, int right)
{if (left >= right){return {-1, -1};}int pivot = array[right];int lessBound = left - 1, moreBound = right;int i = left;while (i < moreBound){if (array[i] == pivot){i++;}else if (array[i] < pivot){swap(array[++lessBound], array[i++]);}else{// array[i] > pivotswap(array[--moreBound], array[i]);}}swap(array[right], array[moreBound++]);return {lessBound, moreBound};
}void quickSortOptimized(vector<int>& array, int left, int right)
{if (left >= right){return;}vector<int> bounds = partitionOptimized(array, left, right);quickSortOptimized(array, left, bounds[0]);quickSortOptimized(array, bounds[1], right);
}void quickSort(vector<int>& array)
{quickSortOptimized(array, 0, array.size() - 1);
}

新的算法的最显著的不同之处在于，partition的返回值是一个数组，保存了小于pivot的边界和大于pivot的边界，他们也是新一轮递归的依据。在计算这两个边界时（partition内），需要将一个数组拆分为：小于pivot的部分，等于pivot的部分，以及大于pivot的部分。此时主要是利用三个指针，分别指向小于pivot的部分的边界，大于pivot的部分的边界，以及当前遍历元素。如果当前元素小于pivot，则与之前的思路类似，将当前元素与小于边界的下一位调换，小于的边界扩大一位，继续下一个元素遍历；如果当前元素等于pivot，继续下一个元素遍历，其他不变；如果当前元素大于pivot，则需要将当前元素与大于边界的下一位进行调换，大于的边界减小一位，注意此时仍然需要调查被调换元素的大小，即不继续一个元素的遍历。