C++实现快速排序算法详解

快速排序是一种高效的排序算法，由C. A. R. Hoare在1960年提出。快速排序的基本思想是选择一个基准元素，通过一趟排序将待排序的记录分割成独立的两部分，其中一部分的所有记录均比另一部分的所有记录小，然后分别对这两部分记录继续进行排序，以达到整个序列有序。 快速排序在C++中的实现通常包括以下几个关键步骤： 1. 选择基准（Pivot）：在数组中选择一个元素作为基准，基准的选择可以有很多种方法，例如选择第一个元素、最后一个元素、中间元素，或者随机选择一个元素。快速排序的性能在很大程度上取决于基准的选择。 2. 分区（Partitioning）：根据基准将数组中的元素重新排列，所有比基准小的元素摆放在基准前面，而所有比基准大的元素摆放在基准后面。这一过程结束后，基准元素所在位置即是其最终排序完成的位置。 3. 递归排序：递归地对基准前后的两个子数组进行快速排序，因为子数组已经是部分有序的，所以递归排序时可以减少不必要的比较和交换操作。 4. 终止条件：递归排序的终止条件通常是在每次递归过程中，待排序的数组区间大小为0或1，因为大小为1的数组已经自然有序。 在C++中，快速排序可以使用数组或标准库中的容器来实现。由于C++语言的面向对象特性，可以将排序算法封装成函数，也可以封装成类。 以下是快速排序的C++代码示例： ```cpp #include <iostream> #include <vector> void quickSort(std::vector<int>& arr, int low, int high) { if (low < high) { // Partitioning index int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); // Recursively sort elements before partition quickSort(arr, pi + 1, high); // Recursively sort elements after partition } } int partition(std::vector<int>& arr, int low, int high) { int pivot = arr[high]; // pivot int i = (low - 1); // Index of smaller element for (int j = low; j <= high - 1; j++) { // If current element is smaller than or equal to pivot if (arr[j] <= pivot) { i++; // increment index of smaller element std::swap(arr[i], arr[j]); } } std::swap(arr[i + 1], arr[high]); return (i + 1); } int main() { std::vector<int> arr = {10, 7, 8, 9, 1, 5}; int n = arr.size(); quickSort(arr, 0, n - 1); std::cout << "Sorted array: \n"; for (int i = 0; i < n; i++) std::cout << arr[i] << " "; std::cout << std::endl; return 0; } ``` 在上述代码中，`quickSort` 函数是一个递归函数，用于对数组的指定部分进行排序。`partition` 函数用于根据基准进行分区，并返回分区点。主函数`main`初始化一个数组，调用`quickSort`函数进行排序，并打印排序后的数组。 快速排序算法的平均时间复杂度为O(n log n)，但最坏情况下的时间复杂度为O(n^2)。通常情况下，快速排序的性能优于其他O(n log n)时间复杂度的排序算法，如归并排序、堆排序等。 在实际使用中，快速排序算法的效率受到基准选择的影响。如果每次都能选择到中位数作为基准，则可以保证快速排序的平均性能。然而，在最坏情况下（例如，当输入数组已经是有序的），快速排序的性能会降低。为了避免这种情况，可以采用随机化快速排序或者三数取中法来选择基准。 在工程实践中，快速排序往往是内置在语言的标准库中的，例如C++的STL中的`std::sort`函数就使用了快速排序的变种算法。因此，在大多数情况下，开发者不需要手动实现快速排序，而是直接使用语言提供的标准排序算法。但在学习和理解算法原理时，手动实现快速排序是一个非常好的练习方式。