P4642 排身高（基础）

解题思路

这一题要用「快速排序」把身高从小到大排列。快速排序的思想很像给一排小朋友按个子高低重新排队，用「选基准、分两边」的方法一步步把队伍理顺。

**第一步，读懂题意。**读入 n 个身高，从小到大排序后，用空格隔开输出，最后换行。数组大小开 1000，因为 n 最大是 1000。

**第二步，理解快速排序的分治思想。**先随便找一个小朋友当「基准」，代码里选中间位置的身高。让所有比基准矮的小朋友站到基准左边，所有比基准高的小朋友站到基准右边。这样基准就把队伍分成了左右两半，然后对左半边和右半边各自再重复同样的过程，直到每个区间只剩下一个小朋友，整队就排好了。

**第三步，用双指针实现分组。**指针 i 从左边往右走，凡是比基准矮的就跳过，直到遇到一个不比基准矮的；指针 j 从右边往左走，凡是比基准高的就跳过，直到遇到一个不比基准高的。如果此时 i 还在 j 的左边，就说明这两个位置站反了，交换它们，然后继续往中间走。如此反复，直到 i 和 j 交错，一次「分区」就完成了，这个过程叫 partition。

**第四步，递归处理左右两边。**分区完成后，基准左边的身高都不比它大，右边的都不比它小。对左半部分和右半部分分别递归调用快速排序，直到区间里只剩一个数。

**第五步，确认边界。**当区间里只有一个数（left >= right）时已经有序，直接返回，这是递归的出口。快速排序平均很快，虽然最坏情况可能慢一些，但本题数据规模只有 1000，完全不用担心。

参考代码

// 使用快速排序把小动物身高从低到高输出
#include <iostream>
using namespace std;

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

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

复杂度分析

快速排序每次把区间分成两半，递归深度大约为 log n，每一层所有数都会被比较一次，所以平均时间复杂度是 O(n log n)。当 n=1000 时，大约只需要几千次比较。递归需要用到系统栈，深度约为 log n，所以空间复杂度是 O(log n)。