P4647 整理书架（入门）

解题思路

书架上有 n 本书，每本书的页数都不一样，要求按页数从多到少（从大到小）整理。n 最大只有 30，是一个很小的数字，但题目希望我们用快速排序的思路来做。

**第一步，读懂题意。**读入 n 本书的页数，按从大到小输出，页数之间用空格隔开。因为每本书页数都不同，不存在并列的情况，排序规则很干净。

**第二步，理解降序快速排序。**快速排序「选基准、分两边」的方法和前面几题一样，只是这一题要把「大的放左边、小的放右边」，也就是降序。代码里 sortDown 函数：左指针 i 跳过所有比基准页数大的书，右指针 j 跳过所有比基准页数小的书，遇到站错位置的就交换，两个指针交错后，再对左右两个区间递归排序。

**第三步，理解分区的意义。**每次分区后，基准都回到它最终该待的位置。递归结束后，整个数组就排好了。也就是说，我们并不需要一次把所有书排好，而是每次确定一本书的最终位置，分而治之。

**第四步，对照样例理解。**样例是 30 100 45 215 15 89。取中间的 45 当基准，比 45 大的都放左边，比 45 小的放右边，45 回到自己的位置；继续递归，最终得到 215 100 89 45 30 15。可以看到页数最多的书排到了最前面，像垒书一样从厚到薄摆放。

**第五步，确认边界。**只有一本书时不用排，直接输出；页数在 1 到 400 之间，用 int 保存完全没问题。递归出口是 left >= right，即区间里只剩一个数时返回。

参考代码

// 使用快速排序把书的页数从大到小输出
#include <iostream>
using namespace std;

void sortDown(int pages[], int left, int right) {
    int i = left; // 左边扫描位置
    int j = right; // 右边扫描位置
    int pivot = pages[(left + right) / 2]; // 选取中间位置的数作为基准
    while (i <= j) { // 两个扫描位置没有交错时继续
        while (pages[i] > pivot) { // 跳过比基准大的数
            i++; // 左边位置向右移动
        }
        while (pages[j] < pivot) { // 跳过比基准小的数
            j--; // 右边位置向左移动
        }
        if (i <= j) { // 找到一对放错位置的数
            int temp = pages[i]; // 暂存左边的页数
            pages[i] = pages[j]; // 把右边页数放到左边
            pages[j] = temp; // 把暂存页数放到右边
            i++; // 左扫描继续向右
            j--; // 右扫描继续向左
        }
    }
    if (left < j) { // 左半部分还有数时继续排序
        sortDown(pages, left, j); // 排序左半部分
    }
    if (i < right) { // 右半部分还有数时继续排序
        sortDown(pages, i, right); // 排序右半部分
    }
}

int main() {
    int n; // 书的数量
    cin >> n; // 读入书的数量
    int pages[30]; // 保存每本书的页数
    for (int i = 0; i < n; i++) { // 依次读入页数
        cin >> pages[i]; // 读入一本书的页数
    }
    sortDown(pages, 0, n - 1); // 调用快速排序
    for (int i = 0; i < n; i++) { // 依次输出排好序的页数
        if (i > 0) { // 不是第一个数时输出空格
            cout << ' '; // 输出分隔空格
        }
        cout << pages[i]; // 输出当前页数
    }
    cout << '\n'; // 输出换行
    return 0; // 程序结束
}

复杂度分析

快速排序平均时间复杂度是 O(n log n)，最坏是 O(n²)。本题 n≤30，即使是平方级也只需要几百次比较，几乎瞬间完成。递归深度约 log n，空间复杂度是 O(log n)。