C++ 实现快速排序
快速排序算法简介
快速排序（Quick Sort）是一种高效的排序算法，由英国计算机科学家托尼·霍尔（Tony Hoare）在1960年开发。它采用了分治（Divide and Conquer）的策略，其基本思想是通过选择一个基准元素（pivot），将数组分为两部分，使得左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素。然后分别对左右两部分进行递归排序，最终将排序好的左半部分、基准元素和排序好的右半部分合并起来，就得到了一个有序的数组。
快速排序的核心步骤
- 选择基准元素：从数组中选择一个元素作为基准值。常见的选择方法有选择数组的第一个元素、最后一个元素或者中间元素。也可以采用随机选择的方式，以减少在特定输入下算法的最坏时间复杂度。
- 分区操作：通过比较数组中的元素与基准元素，将数组分为两部分。遍历数组，将小于等于基准元素的元素放在左边，大于等于基准元素的元素放在右边。这个过程会改变数组中元素的顺序，使得基准元素处于一个中间位置，左边的元素都不大于它，右边的元素都不小于它。
- 递归排序：对左右两部分子数组分别递归地应用快速排序算法。这意味着不断地在子数组上重复选择基准元素、分区和递归的过程，直到子数组的长度为1或者0（此时子数组已经有序）。
C++ 中实现快速排序
代码实现思路
在C++ 中实现快速排序，我们可以使用函数来封装快速排序的逻辑。首先，我们需要一个函数来进行分区操作，然后再使用一个递归函数来进行整个快速排序的流程。
分区函数实现
// 分区函数，返回基准元素的最终位置
int partition(int arr[], int low, int high) {
// 选择最后一个元素作为基准元素
int pivot = arr[high];
int i = (low - 1); // 小于基准元素的子数组的索引
for (int j = low; j <= high - 1; j++) {
// 如果当前元素小于等于基准元素
if (arr[j] <= pivot) {
i++; // 增大小于基准元素的子数组的索引
// 交换arr[i] 和 arr[j]
std::swap(arr[i], arr[j]);
}
}
// 交换arr[i + 1] 和 arr[high]（基准元素）
std::swap(arr[i + 1], arr[high]);
return (i + 1);
}
在上述代码中，我们选择数组的最后一个元素作为基准元素 pivot。然后通过遍历 low 到 high - 1 的元素，将小于等于 pivot 的元素放到左边，大于 pivot 的元素放到右边。最后，将基准元素放到它应该在的位置，并返回这个位置。
快速排序递归函数实现
// 快速排序递归函数
void quickSort(int arr[], int low, int high) {
if (low < high) {
// pi 是基准元素的位置
int pi = partition(arr, low, high);
// 分别对基准元素的左右两部分进行递归排序
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
在 quickSort 函数中，首先检查 low 是否小于 high，如果是，则进行分区操作得到基准元素的位置 pi。然后分别对基准元素左边（low 到 pi - 1）和右边（pi + 1 到 high）的子数组进行递归排序。
完整代码示例
#include <iostream>
#include <algorithm>
// 分区函数，返回基准元素的最终位置
int partition(int arr[], int low, int high) {
// 选择最后一个元素作为基准元素
int pivot = arr[high];
int i = (low - 1); // 小于基准元素的子数组的索引
for (int j = low; j <= high - 1; j++) {
// 如果当前元素小于等于基准元素
if (arr[j] <= pivot) {
i++; // 增大小于基准元素的子数组的索引
// 交换arr[i] 和 arr[j]
std::swap(arr[i], arr[j]);
}
}
// 交换arr[i + 1] 和 arr[high]（基准元素）
std::swap(arr[i + 1], arr[high]);
return (i + 1);
}
// 快速排序递归函数
void quickSort(int arr[], int low, int high) {
if (low < high) {
// pi 是基准元素的位置
int pi = partition(arr, low, high);
// 分别对基准元素的左右两部分进行递归排序
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// 打印数组函数
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
std::cout << arr[i] << " ";
std::cout << std::endl;
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
std::cout << "原始数组: ";
printArray(arr, n);
quickSort(arr, 0, n - 1);
std::cout << "排序后的数组: ";
printArray(arr, n);
return 0;
}
在 main 函数中，我们定义了一个数组并初始化，然后调用 quickSort 函数对其进行排序，最后通过 printArray 函数打印出排序前后的数组。
快速排序的时间复杂度分析
平均时间复杂度
快速排序的平均时间复杂度为 (O(n log n))，其中 (n) 是数组中元素的个数。这是因为在平均情况下，每次分区操作都能将数组大致分成两个相等的部分。每次递归调用会将问题规模减半，而递归的深度为 (log n)，每层递归的操作次数约为 (n)，所以总体时间复杂度为 (O(n log n))。
最坏时间复杂度
快速排序的最坏时间复杂度为 (O(n^2))。当每次选择的基准元素都是数组中的最大或最小元素时，就会出现这种情况。例如，当数组已经是有序的，并且选择第一个元素作为基准元素时，每次分区都会使得一边的子数组为空，而另一边的子数组包含除基准元素外的所有元素。这样，递归的深度就会达到 (n)，每层递归的操作次数也为 (n)，从而导致时间复杂度为 (O(n^2))。
最好时间复杂度
快速排序的最好时间复杂度也是 (O(n log n))。当每次分区操作都能将数组精确地分成两个长度相等的子数组时，就会达到最好情况。这种情况下，递归的深度为 (log n)，每层递归的操作次数为 (n)，所以时间复杂度为 (O(n log n))。
快速排序的空间复杂度分析
递归调用栈空间
快速排序的空间复杂度主要取决于递归调用栈的深度。在平均情况下，递归调用栈的深度为 (log n)，所以空间复杂度为 (O(log n))。然而，在最坏情况下，递归调用栈的深度会达到 (n)，此时空间复杂度为 (O(n))。例如，当每次选择的基准元素都是数组中的最大或最小元素时，递归调用栈的深度就会达到 (n)。
优化空间复杂度的方法
为了优化快速排序的空间复杂度，可以采用非递归的实现方式，使用栈来模拟递归调用。这样可以将空间复杂度控制在 (O(log n))，即使在最坏情况下也能避免栈溢出的问题。
快速排序与其他排序算法的比较
与冒泡排序比较
冒泡排序是一种简单的比较排序算法，它通过多次比较相邻元素并交换位置，将最大（或最小）的元素逐步“冒泡”到数组的末尾。冒泡排序的时间复杂度为 (O(n^2))，无论在什么情况下都是如此。而快速排序在平均情况下的时间复杂度为 (O(n log n))，性能明显优于冒泡排序。不过，冒泡排序的代码实现相对简单，并且在数据规模较小时，由于其常数项较小，可能在实际运行中表现并不差。
与插入排序比较
插入排序是一种简单的排序算法，它将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的合适位置。插入排序在数据规模较小或者数组已经部分有序的情况下表现较好，时间复杂度可以达到 (O(n))。然而，在一般情况下，其时间复杂度为 (O(n^2))。快速排序在平均情况下的 (O(n log n)) 时间复杂度使其在处理大规模数据时更具优势。
与归并排序比较
归并排序也是一种基于分治思想的排序算法。它将数组不断地分成两半，对每一半进行排序，然后将排序好的两半合并起来。归并排序的时间复杂度始终为 (O(n log n))，无论在最好、平均还是最坏情况下都是如此。而快速排序在平均情况下为 (O(n log n))，最坏情况下为 (O(n^2))。不过，快速排序在实际应用中通常比归并排序更快，因为它不需要额外的辅助数组来进行合并操作（除了递归调用栈所需的空间），从而减少了空间开销并且在数据局部性方面表现更好。
快速排序的优化
随机化基准元素选择
为了避免在某些特定输入下快速排序出现最坏时间复杂度的情况，可以采用随机化基准元素选择的方法。即在每次进行分区操作前，随机选择数组中的一个元素作为基准元素。这样可以使得在大多数情况下，基准元素能够将数组较为均匀地分成两部分，从而减少最坏情况出现的概率。
三数取中策略
另一种优化基准元素选择的方法是三数取中策略。具体做法是在数组的开头、中间和末尾三个位置选择元素，然后取这三个元素的中间值作为基准元素。这种方法比简单的随机选择基准元素更加稳定，能够有效地避免选择到最大或最小元素作为基准元素，从而提高算法的性能。
小数组优化
当子数组的规模较小时，递归调用快速排序的开销可能会超过直接使用简单排序算法（如插入排序）的开销。因此，可以在子数组规模小于某个阈值（例如16）时，切换到插入排序。这样在处理小数组时能够利用插入排序在小规模数据上的优势，提高整体的排序效率。
尾递归优化
在C++ 中，编译器通常会对尾递归进行优化，将其转换为迭代形式，从而避免递归调用栈过深导致栈溢出的问题。尾递归是指递归调用是函数的最后一个操作。在快速排序中，可以通过调整代码结构，使得递归调用成为尾递归，从而利用编译器的优化机制。例如，可以将其中一个递归调用改为循环，然后继续处理另一个子数组的递归调用。
快速排序在实际应用中的场景
大数据集排序
在处理大规模数据集时，快速排序的平均时间复杂度 (O(n log n)) 使其成为一个非常高效的选择。例如，在数据库中对大量数据进行排序时，快速排序可以快速地将数据按照指定的字段进行排序，提高查询和分析的效率。
算法竞赛
在算法竞赛中，快速排序因其高效性和灵活性而被广泛应用。选手可以根据题目要求对快速排序进行适当的优化，如选择合适的基准元素、处理边界情况等，以在规定的时间内完成大规模数据的排序任务。
内存受限环境
虽然快速排序在最坏情况下空间复杂度可能达到 (O(n))，但通过采用非递归实现或者优化基准元素选择等方法，可以将空间复杂度控制在 (O(log n))。这使得快速排序在内存受限的环境中也能够有效地工作，例如在嵌入式系统或者移动设备上对数据进行排序。
数据预处理
在许多数据处理任务中，需要对数据进行预处理，其中排序是一个常见的操作。快速排序可以快速地对数据进行排序，为后续的数据分析、查找等操作提供有序的数据基础，提高整个数据处理流程的效率。
总结快速排序的优缺点
优点
- 平均性能好：快速排序在平均情况下具有 (O(n log n)) 的时间复杂度，这使得它在处理大规模数据时表现非常高效，相比一些时间复杂度为 (O(n^2)) 的简单排序算法（如冒泡排序、插入排序）有明显的性能优势。
- 原地排序：快速排序可以在不使用额外大量辅助空间的情况下完成排序（除了递归调用栈所需的空间），这对于内存受限的环境或者需要处理大规模数据的场景非常重要。
- 灵活性高：可以通过选择不同的基准元素选择策略（如随机化、三数取中）以及结合其他排序算法（如在小数组时使用插入排序）来优化算法性能，适应不同的输入数据特点。
缺点
- 最坏时间复杂度高：在最坏情况下，快速排序的时间复杂度会退化到 (O(n^2))，例如当每次选择的基准元素都是数组中的最大或最小元素时。虽然可以通过优化基准元素选择策略来减少这种情况的发生，但不能完全避免。
- 不稳定排序：快速排序是一种不稳定的排序算法，即相等元素的相对顺序在排序后可能会改变。这在一些对元素顺序有严格要求的场景（如对结构体按照多个字段排序，且需要保持相同关键字元素的原始顺序）中可能不适用。
通过对快速排序的原理、C++ 实现、时间和空间复杂度分析、与其他排序算法的比较、优化方法以及实际应用场景的深入探讨，我们可以更全面地了解和掌握这一重要的排序算法，在实际编程中根据具体需求合理地运用它来解决数据排序问题。