#qs001. 快速排序

快速排序

快速排序

题目描述

​ 给定 n 个整数 xix_i,请使用快速排序(Quick Sort) 的思想,将这些整数按从小到大的顺序输出(包含重复元素,即每个出现几次就输出几次)。

算法概念

​ 快速排序是一种高效的基于分治思想的排序算法。它通过选择一个基准元素(pivot),将待排序序列划分为左右两个子序列:左子序列中所有元素都不大于基准,右子序列中所有元素都不小于基准。然后递归地对两个子序列进行同样的操作,最终使整个序列有序。快速排序平均时间复杂度为 O(n log n),是实际应用中最常用的排序算法之一。

算法原理与步骤

  1. 选择基准:从当前待排序区间 [l, r] 中选取一个元素作为基准(pivot),通常选择区间左端元素 a[l]。此时,a[l] 位置被“挖空”,形成一个坑位,pivot 值暂存于变量中。
  2. 分区操作(挖坑填数):使用两个指针 i(从左向右)和 j(从右向左)扫描区间,通过交替挖坑和填数,将所有小于 pivot 的元素移到左边,大于 pivot 的元素移到右边。
    • 从右向左移动 j,寻找第一个小于 pivot 的元素 a[j](即 a[j] < pivot)。找到后,将 a[j] 填入当前左侧的坑位(即 a[i] = a[j]),此时 a[j] 位置变为新的坑位(右侧坑)。
    • 从左向右移动 i,寻找第一个大于 pivot 的元素 a[i](即 a[i] > pivot)。找到后,将 a[i] 填入当前右侧的坑位(即 a[j] = a[i]),此时 a[i] 位置变为新的坑位(左侧坑)。
    • 重复上述两步,直到 i 和 j 相遇(i == j),此时相遇位置就是最后一个坑位。
  3. 基准归位:将 pivot 填入最后一个坑位(即 a[i] = pivot),此时 pivot 左侧元素均不大于它,右侧元素均不小于它,pivot 已处于排序后的最终位置。
  4. 递归排序:对基准左侧子区间 [l, i-1] 和右侧子区间 [i+1, r] 递归调用快速排序,直到子区间长度不超过 1,递归结束。

​ 具体说明“移动到左边/右边”的含义:每当我们从右或左找到一个应该移到另一侧的元素时,我们不是直接交换,而是用该元素的值填充当前坑位,从而将该元素“移动”到正确的一侧。原位置随即成为新的坑,等待下一个元素填入。这种交替挖坑填数的过程实现了元素的单向移动,避免了显式的交换操作。

输入格式

​ 第一行一个正整数 n,表示数字个数。 ​ 第二行 n 个整数,每个数在 int 范围内。

输出格式

​ 一行,输出排序后的 n 个整数,相邻数字用空格隔开。

输入输出样例

5
3 1 2 1 3
1 1 2 3 3

数据规模与约定

​ 1 ≤ n ≤ 5000

​ 数值范围:-10^9 ≤xi x_i ≤ 10^9

​ 时间限制:1 秒(快速排序平均 O(n log n),n=5000 时远快于 O(n^2) 算法,可轻松通过)

提示

​ 代码提示:

int a[5005];  // 全局数组,方便递归访问
int n;
void qsort(int l, int r) {
    if (l >= r) {
        return;  // 子区间长度不超过1,无需排序
    }
    int i = l, j = r;
    int pivot = a[l];  // 选择左端元素作为基准,即第一个坑位

    while (i < j) {
        // 从右向左移动 j,找第一个小于 pivot 的元素,填入左侧坑位 a[i]
        // TODO: while(i < j && a[j] >= pivot) j--;
        // TODO: a[i] = a[j];  // 将 a[j] 填到左侧坑,a[j] 成为新坑

        // 从左向右移动 i,找第一个大于 pivot 的元素,填入右侧坑位 a[j]
        // TODO: while(i < j && a[i] <= pivot) i++;
        // TODO: a[j] = a[i];  // 将 a[i] 填到右侧坑,a[i] 成为新坑
    }
    // 基准归位,填入最后一个坑
    a[i] = pivot;

    // 递归排序左右子区间
    qsort(l, i - 1);
    qsort(i + 1, r);
}

int main() {
    //输入数据
    qsort(1, n);
    //输出数据
    return 0;
}

​ 运用提示:

​ 快速排序的分区操作本质上是“挖坑填数”:基准位置被挖坑,然后从右侧找小元素填左坑,左侧找大元素填右坑,交替进行,直到左右指针相遇,最后将基准填入最后一个坑。

​ 注意内层循环的边界条件 i < j,以及比较时使用 >= 和 <= 确保重复元素不会死循环。

​ 递归调用时,基准元素已经归位,因此左右子区间分别排除 i。

​ 数组下标从 1 开始,调用 qsort(1, n) 时需确保 n ≥ 1。