1.定义

快速排序是一种分治法（Divide and Conquer）的排序算法。它通过选取一个“基准”元素，将待排序的数组分成两部分，使得一部分的元素都小于等于基准元素，另一部分的元素都大于等于基准元素，然后递归地对这两部分分别进行排序，最终实现整个数组的有序排列

不懂分治法的，先去看分治算法c++详解（看这一篇就够了）_分治算法 c++-CSDN博客

2.概述

快速排序由 C. A. R. Hoare 在 1960 年提出，是一种基于**分治法（Divide and Conquer）**的高效排序算法。它通过递归地将数组划分成较小的子数组进行排序，平均时间复杂度为 O(n log n)，在大多数情况下比其他 O(n log n) 级别的排序算法（如归并排序）更快。

快速排序的特点：

• 时间复杂度：
  • 平均情况：O(n log n)
  • 最坏情况（基准总是最小或最大值）：O(n²)
• 空间复杂度：O(log n)（递归调用栈的开销）
• 稳定性：不稳定（可能交换相同元素的位置）
• 适用性：适用于大规模数据排序，尤其是内排序（in-place sorting）。

快速排序因其高效性而成为最常用的排序算法之一，并且是许多标准库排序函数的核心实现（如 std::sort 在许多实现中都基于快速排序和堆排序的组合）。

3.原理

    算法步骤

• 选择基准（Pivot）：可以是第一个、最后一个、中间的某个元素，或随机选择。
• 划分（Partition）：调整数组，使左侧元素 ≤ 基准，右侧元素 ≥ 基准，并将基准放入正确位置。
• 递归（Recursion）：对左右子数组分别递归执行快速排序，直到子数组长度为 1 或 0，排序完成。

举个栗子

假设有一个无序数组：

[9, 7, 5, 11, 12, 2, 14, 3, 10, 6]

1. 选择基准（Pivot）

• 从数组中选一个元素作为基准值（Pivot）。
• 这里我们选择最后一个元素 6 作为基准值（实际可以选第一个、随机选择或取中位数）。

2. 划分（Partition）

• 重新排列数组，使得所有小于等于基准值的元素放到左边，大于基准值的元素放到右边。
• 遍历数组，把比 6 小的数放到左侧，比 6 大的数放到右侧，最终形成：

  [5, 2, 3, 6, 12, 14, 11, 9, 10, 7]

  • 5, 2, 3 在左边（小于 6）。
  • 12, 14, 11, 9, 10, 7 在右边（大于 6）。
  • 6 被放到了正确的位置。

3. 递归排序左右子数组

• 左子数组 [5, 2, 3] 递归执行快速排序：
  • 选择 3 作为基准值 → 排列为 [2, 3, 5]
  • 左边 [2] 和右边 [5] 已经有序，无需递归。
• 右子数组 [12, 14, 11, 9, 10, 7] 递归执行快速排序：
  • 选择 7 作为基准值 → 排列为 [7, 9, 10, 11, 12, 14]
  • 左边 [7] 已有序，无需递归。
  • 右边 [9, 10, 11, 12, 14] 继续递归，最终变成 [7, 9, 10, 11, 12, 14]。

4. 组合最终结果

排序完成后，最终数组变成：

[2, 3, 5, 6, 7, 9, 10, 11, 12, 14]

4.代码

#include<bits/stdc++.h>
using namespace std;
int arr[110],n;
void quickSort(int left,int right)
{
    if(left>=right)
    {
        return;
    }
    int pivot=arr[right],i=left-1;
    for(int j=left;j<right;j++)
    {
        if(arr[j]<=pivot)
        {
            swap(arr[++i],arr[j]);
        }
    }
    swap(arr[i+1],arr[right]);
    quickSort(left,i);
    quickSort(i+2,right);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
    }
    quickSort(1,n);
    for(int i=1;i<=n;i++)
    {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
    return 0;
}

代码解释：

• 选择 arr[right] 作为基准元素。
• 使用两个指针：i 指向小于等于基准元素的部分的最后一个元素，j 遍历整个数组。
• 如果 arr[j] <= pivot，则交换 arr[i] 和 arr[j]，并且 i 增加。
• 最后将基准元素放到其正确的位置，并递归排序左侧和右侧的子数组。

5.提醒

• 快速排序的性能受基准选择的影响。如果每次选择的基准是最小或最大值（比如选择第一个或最后一个元素），在某些情况下（例如已排序或逆序数组），其时间复杂度可能会退化到 O(n²)。
• 为了避免最坏情况，可以采用随机化快速排序或三数取中法来选择基准元素。
• 快速排序是不稳定的排序算法，因此如果需要稳定排序，可以考虑使用归并排序或插入排序。