C++实现快速排序算法的递归调用示例

快速排序算法由C. A. R. Hoare在1960年提出，它在平均情况下具有O(n log n)的时间复杂度，且由于其原地排序的特性，在处理大量数据时往往比其他排序算法更为高效。 C++实现的快速排序通常采用递归的方式进行编程，其核心思想是：首先选择一个基准值（pivot），通过一系列的交换操作，将数组分为两个子数组，一个包含所有小于基准值的元素，另一个包含所有大于基准值的元素。然后递归地在这两个子数组上继续进行排序。基准值的选择可以是数组的第一个元素、最后一个元素、中间元素或者随机选择一个元素。 快速排序算法的性能在很大程度上取决于基准值的选择。理想情况下，每次划分都能将数组分成两个长度大致相等的子数组，这样能够保证快速排序的性能接近O(n log n)。但最坏情况下，如果每次划分都将数据集分为一个元素和其余所有元素两部分，那么时间复杂度将退化到O(n^2)，这通常发生在数据本来就是有序或接近有序时。为了避免这种情况，可以采用随机化基准值的方法，以期望避免最坏情况的发生。 快速排序可以就地排序，不需要额外的存储空间，其空间复杂度为O(log n)，这是因为递归调用时的栈空间。对于含有大量数据的数组排序，这种空间效率是非常重要的。" 快速排序算法的C++实现代码通常包括以下几个关键部分： 1. 选择基准值（pivot selection）。 2. 划分（partitioning），将数组分成两部分。 3. 递归地对划分后的两个子数组进行快速排序。 以下是一个简单的快速排序C++代码示例： ```cpp #include <iostream> #include <vector> void quickSort(std::vector<int>& arr, int left, int right) { if (left >= right) return; int pivot = arr[left + (right - left) / 2]; // 选取中间值作为基准 int l = left, r = right; while (l <= r) { while (arr[l] < pivot) l++; while (arr[r] > pivot) r--; if (l <= r) { std::swap(arr[l], arr[r]); l++; r--; } } // 递归排序基准值左右两部分 if (left < r) quickSort(arr, left, r); if (l < right) quickSort(arr, l, right); } int main() { std::vector<int> data = {3, 6, 8, 10, 1, 2, 1}; quickSort(data, 0, data.size() - 1); for (int i : data) { std::cout << i << " "; } return 0; } ``` 上述代码中，`quickSort`函数是快速排序的主要逻辑，它接受一个数组（这里使用`std::vector<int>`表示）和数组的左右边界索引。函数内部首先选取一个基准值，然后进行划分操作，最后递归地对基准值左右两侧的子数组进行排序。基准值的选取方式和划分策略可能会根据不同的实现有所变化。 快速排序算法的优缺点都非常明显： 优点： - 在平均情况下效率高，时间复杂度为O(n log n)。 - 空间复杂度低，为O(log n)，主要消耗在递归调用的栈上。 - 原地排序，不需要额外的存储空间。 缺点： - 最坏情况时间复杂度较高，为O(n^2)。 - 不稳定排序，相等的元素可能会因为排序而改变相对位置。 在处理大数据量且对排序性能要求较高的场景下，快速排序往往是首选的排序算法。"