快速排序C++模板，面试常考需背熟
快速排序介绍
快速排序（Quick Sort）是计算机科学领域中极为经典且高效的一种排序算法，它在众多实际应用场景中都发挥着重要作用。该算法由英国杰出的计算机科学家托尼·霍尔（Tony Hoare）于1960年提出，自诞生以来，因其卓越的性能而被广泛应用于各种数据排序任务中。
基本思想
快速排序巧妙地运用了分治法（Divide and Conquer）的策略。分治法的核心概念是将一个复杂的大问题分解为若干个规模较小、相互独立且与原问题形式相同的子问题，接着递归地去解决这些子问题，最后把各个子问题的解合并起来，从而得到原问题的解。在快速排序的实现过程中，就是把一个数组划分成两个子数组，然后分别对这两个子数组进行排序操作。
具体步骤
选择基准点（Pivot）
基准点的选择在快速排序里是一个至关重要的步骤，它直接影响到后续分区操作的效果以及整个算法的性能表现。基准点可以从数组中的任意位置选取，常见的选择方式有以下几种：
- 选择数组的第一个元素：这种方式实现起来较为简单，但在某些特殊情况下，比如数组已经有序或者接近有序时，可能会导致算法性能下降。
- 选择数组的最后一个元素：同样实现简单，但也存在与选择第一个元素类似的性能风险。
- 选择数组的中间元素：选择中间元素作为基准点能够在一定程度上避免最坏情况的发生，使得分区操作更加均匀地将数组分成两部分。
- 随机选择元素：随机选择基准点可以有效地避免某些特定输入导致的最坏情况，提高算法的平均性能。
分区操作（Partitioning）
分区操作是快速排序的核心环节，其目标是对数组中的元素进行重新排列，让所有小于基准点的元素都位于基准点的左侧，所有大于基准点的元素都位于基准点的右侧。这一过程通常借助双指针来完成，一个指针从数组的左侧开始向右移动，另一个指针从数组的右侧开始向左移动，当两个指针相遇时，分区操作就宣告结束。
递归排序
完成分区操作之后，数组会被划分成两个子数组，分别是基准点左侧的子数组和基准点右侧的子数组。对这两个子数组分别递归地应用快速排序算法，直至子数组的长度为1或0。因为长度为1或0的数组本身已经是有序的，无需再进行排序。
复杂度分析
时间复杂度
快速排序的平均时间复杂度为 (O(n log n))。在平均情况下，每次分区操作都能够将数组大致均匀地分成两个相等的子数组，递归的深度为 (log n)，而每次分区操作需要遍历数组中的所有元素，时间复杂度为 (O(n))。不过，在最坏情况下，例如当数组已经有序或者接近有序时，每次选择的基准点恰好是数组中的最大或最小元素，此时时间复杂度会退化为 (O(n^2))。
空间复杂度
快速排序的空间复杂度主要取决于递归调用栈的深度。平均情况下，递归调用栈的深度为 (O(log n))，因此空间复杂度为 (O(log n))。在最坏情况下，递归调用栈的深度为 (O(n))，空间复杂度也会相应地变为 (O(n))。
稳定性
快速排序是一种不稳定的排序算法，这意味着在排序过程中，相等元素的相对顺序可能会发生改变。例如，对于数组 ([3, 2, 3, 1])，排序后两个值为3的元素的相对顺序可能与排序前不同。
应用场景
由于快速排序具备较高的平均性能，所以在大多数场景下都能有出色的表现。它广泛应用于需要对大规模数据进行排序的场景，比如数据库查询结果的排序、大规模数据集的预处理等。此外，快速排序也是许多编程语言标准库中排序函数的实现基础，像Python的 sorted() 函数、Java的 Arrays.sort() 函数等在底层实现时都借鉴了快速排序的思想。
快速排序流程图
快速排序代码
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int x = q[(l + r) / 2];
// 初始化双指针i和j，i从左侧开始，j从右侧开始，注意i和j都往外扩一个，避免边界错误
int i = l - 1;
int j = r + 1;
// 使用while循环进行元素的交换，直到i和j相遇
while (i < j)
{
// 从左向右扫描，找到第一个大于等于基准点x的元素
do i++; while (q[i] < x);
// 从右向左扫描，找到第一个小于等于基准点x的元素
do j--; while (q[j] > x);
// 如果i小于j，说明找到了一对可以交换的元素
if (i < j) swap(q[i], q[j]);
}
// 递归地对子数组进行快速排序，注意递归的边界是j，因为j已经移动到了第一个大于x的元素位置
quick_sort(q, l, j); //j
// 对于j+1到r的子数组，同样递归地进行快速排序
quick_sort(q, j + 1, r);
}
// 调用方法：quick_sort(q, 0, q.size() - 1);