P4644 渐变（基础）

解题思路

有 n 个亮度不同的日光灯泡，为了点亮时能产生由暗到亮的渐变效果，要把亮度从小到大排好。这又是一道快速排序题，排序规则是升序。

**第一步，读懂题意。**读入 n 个灯泡亮度，从小到大排序，用空格隔开输出。n 最大 1000，数组开 1000 足够，亮度范围是 1 到 100，用 int 保存没有问题。

**第二步，理解快速排序的分治思想。**快速排序就像给一摞卡片按数字重排：先挑中间的一张当「基准」，把比它小的全部放到左边，比它大的全部放到右边，基准就回到了正确的位置；然后左边一堆和右边一堆各自再按同样的办法排。

第三步，用双指针实现分组。sortUp 函数用两个指针 i 和 j 从两头往中间扫描：i 跳过所有比基准小的，j 跳过所有比基准大的。一旦发现 i 指的数不小、j 指的数不大，就说明这两个数站错了位置，交换它们。两个指针交错时本次分区结束，再递归处理左右两个区间。

**第四步，对照样例理解。**样例是 12 5 3 15 6。取中间的 3 当基准，比 3 小的没有，比 3 大的都放右边，3 排到最前面；继续递归，最终得到 3 5 6 12 15。这样一排灯泡的亮度就是从小到大的渐变顺序了。

**第五步，确认边界。**只有一个灯泡时已经排好，直接输出。递归出口是 left >= right，即区间里只剩一个数时返回，然后依次向上合并出整个有序序列。本题灯泡亮度各不相同，不存在并列情况，排序规则很干净。

参考代码

// 使用快速排序把灯泡亮度从小到大输出
#include <iostream>
using namespace std;

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

int main() {
    int n; // 灯泡数量
    cin >> n; // 读入灯泡数量
    int brightness[1000]; // 保存所有灯泡亮度
    for (int i = 0; i < n; i++) { // 依次读入亮度
        cin >> brightness[i]; // 读入一个亮度
    }
    sortUp(brightness, 0, n - 1); // 调用快速排序
    for (int i = 0; i < n; i++) { // 依次输出排好序的亮度
        if (i > 0) { // 不是第一个数时输出空格
            cout << ' '; // 输出分隔空格
        }
        cout << brightness[i]; // 输出当前亮度
    }
    cout << '\n'; // 输出换行
    return 0; // 程序结束
}

复杂度分析

快速排序平均时间复杂度是 O(n log n)，最坏是 O(n²)。本题 n≤1000，即使是最坏情况也只需要约 100 万次比较，完全可以通过。递归调用产生的栈深度约 log n，空间复杂度是 O(log n)。