P4635 排序（基础）

解题思路

这道题要把 n 个整数从小到大排序后输出，是最经典的快速排序入门题。快速排序就像给小朋友按身高排队，用「选基准、分两边」的办法一步步把队伍理顺。

**第一步，读懂题意。**读入一个整数 n 和 n 个整数，从小到大排序后，用空格隔开输出，第一个数前面没有空格，最后要换行。

**第二步，理解快速排序的思想。**想象一队小朋友要按身高从矮到高排。我们先从队伍中间随便拉一个人当「基准」，比如小红。然后让所有比小红矮的站到小红左边，所有比小红高的站到小红右边，这样小红的位置就固定了。接下来，左边的这一堆和右边的这一堆，各自再用同样的办法继续整理，直到每一堆都只剩一个人，整队就排好了。这种「一分为二、两边各自再来」的做法叫分治。

**第三步，用双指针实现分组。**代码里用指针 i 从左边往右走，找到第一个「不小于基准」的数；指针 j 从右边往左走，找到第一个「不大于基准」的数。这两个数都站错了位置，把它们交换。i 和 j 继续往中间靠，重复这个过程，直到两个指针交错，一次分组就完成了。

**第四步，递归处理左右区间。**分组完成后，基准左边的数都不大于它，右边的数都不小于它。我们再递归处理左边的区间和右边的区间。当区间里只剩一个数（left >= right）时，说明已经有序，直接返回，这就是递归的出口。

**第五步，处理边界与细节。**分界值选中间位置的数 numbers[(left + right) / 2]，不管数据有序还是乱序，划分都比较均匀。交换两个数时用一个临时变量 temp 暂存。如果所有数都相等，两个 while 循环不会移动指针，程序会通过交换让 i 和 j 继续向中间靠拢，最终也能正确结束。

参考代码

// 使用快速排序把整数从小到大排列并输出。
#include <iostream>
using namespace std;

// 对区间[left,right]进行快速排序。
void quickSort(int numbers[], int left, int right) {
    if (left >= right) return; // 区间只有一个或没有数字时已经有序。
    int i = left; // 从左边开始寻找位置不对的数字。
    int j = right; // 从右边开始寻找位置不对的数字。
    int pivot = numbers[(left + right) / 2]; // 选择中间位置的数字作为分界值。
    while (i <= j) { // 两个指针没有相遇时继续处理。
        while (numbers[i] < pivot) i++; // 左边小于分界值的数字可以保留。
        while (numbers[j] > pivot) j--; // 右边大于分界值的数字可以保留。
        if (i <= j) { // 找到一对需要交换的数字。
            int temp = numbers[i]; // 暂存左边数字。
            numbers[i] = numbers[j]; // 把右边数字放到左边。
            numbers[j] = temp; // 把左边数字放到右边。
            i++; // 左指针向右移动。
            j--; // 右指针向左移动。
        }
    }
    if (left < j) quickSort(numbers, left, j); // 排序分界值左边的区间。
    if (i < right) quickSort(numbers, i, right); // 排序分界值右边的区间。
}

int main() {
    int n; // 整数的个数。
    cin >> n; // 读入整数个数。
    int *numbers = new int[n]; // 动态申请保存整数的数组。
    int i; // 外层循环变量。
    for (i = 0; i < n; i++) { // 读入所有整数。
        cin >> numbers[i]; // 读入一个整数。
    }
    quickSort(numbers, 0, n - 1); // 对整个数组进行快速排序。
    for (i = 0; i < n; i++) { // 输出排好序的数组。
        if (i > 0) cout << ' '; // 数字之间输出一个空格。
        cout << numbers[i]; // 输出当前数字。
    }
    cout << '\n'; // 输出换行。
    delete[] numbers; // 释放申请的数组空间。
    return 0; // 程序正常结束。
}

复杂度分析

快速排序每次把区间大致分成两半，递归深度约为 log2(n)，每一层对所有元素做一次扫描，所以平均时间复杂度是 O(n log n)。在 n 为十万左右的数据量下，这个速度非常快。不过最坏情况下（比如每次基准都是最大值或最小值），划分不均匀，时间复杂度会退化为 O(n²)，但题目数据通常不会刻意构造这种情况。空间上，递归调用会占用栈空间，平均深度是 O(log n)，最坏是 O(n)，我们用动态数组存放数据，额外空间为 O(n)。