P4643 整理文件（基础）

解题思路

地上的文件编号是 1 到 100 之间的整数，要求按编号从大到小整理。这一题和快速排序有关，但和普通升序不一样：这次要「从大到小」排，也就是编号大的文件排前面。

**第一步，读懂题意。**读入 n 个文件编号，按从大到小的顺序输出，编号之间用空格隔开。文件数不超过 100，数组开 100 个位置就够。

**第二步，理解降序快排的不同。**快速排序的思路还是「选基准、分左右」，只不过这次把「比基准大的数」放到基准左边，「比基准小的数」放到基准右边。代码里的 sortDown 函数就是「倒着来」的快排：左指针跳过所有比基准大的数，右指针跳过所有比基准小的数，遇到放反的就交换，直到两个指针交错，再分别对左右两半递归排序。函数名里的 Down 就表示降序。

**第三步，用双指针实现分组。**指针 i 从左边往右走，跳过所有比基准大的数；指针 j 从右边往左走，跳过所有比基准小的数。找到一对放错位置的数就交换，直到两个指针交错。

**第四步，对照样例理解。**样例是 6 1 9 2 7。先取中间的数 9 当基准，比 9 大的放左边（没有），比 9 小的放右边，于是 9 到了最前面；剩下的区间继续递归，最终得到 9 7 6 2 1。可以看到最大的数字像大泡泡一样不断跑到前面。

**第五步，确认边界。**文件数最少是 1，只有一个文件时不需要任何交换，直接输出即可；编号在 1 到 100 之间，用 int 保存没有问题。

参考代码

// 使用快速排序把文件编号从大到小输出
#include <iostream>
using namespace std;

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

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

复杂度分析

和普通快速排序一样，平均时间复杂度是 O(n log n)，最坏情况是 O(n²)。本题 n 最大只有 100，所以无论怎样都运行得飞快。递归深度大约为 log n，空间复杂度是 O(log n)。