“野牛程序员·少儿编程算法启蒙课”之——快速排序，像忍者一样分身排序！

? 什么是快速排序？

快速排序，全名：快得很的排序（开玩笑?）

它是一种“分而治之”的策略，像切蛋糕一样，把数据一切再切，左边的比中间这个小，右边的比中间这个大，然后——递归地各自再去切！

就像一个忍者，把一堆人分成左边（低年级），右边（高年级），然后左边自己再分，右边也自己再分……最后自动就排好了队！

? 举个例子来理解：

假设有这样一组数字：

[7, 3, 9, 4, 6, 2]

Step 1：选一个“基准值”（pivot）
比如选第一个：7

Step 2：把比 7 小的放左边，比 7 大的放右边：
→ [3, 4, 6, 2]（左边）7 [9]（右边）

Step 3：左边 [3, 4, 6, 2] 再来一次快速排序！选 3：
→ [2] 3 [4, 6]

继续拆下去……

最后就拼起来啦：
[2, 3, 4, 6] + 7 + [9] → 排好了！

?‍? C++ 代码来了：

#include <iostream>
using namespace std;

void quickSort(int arr[], int left, int right) {
    if (left >= right) return;

    int pivot = arr[left];  // 选第一个当基准
    int i = left, j = right;

    while (i < j) {
        // 从右边找第一个比 pivot 小的
        while (i < j && arr[j] >= pivot) j--;
        // 从左边找第一个比 pivot 大的
        while (i < j && arr[i] <= pivot) i++;

        if (i < j) {
            swap(arr[i], arr[j]);
        }
    }

    // 基准归位
    swap(arr[left], arr[i]);

    // 递归处理左边和右边
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {7, 3, 9, 4, 6, 2};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "排序前：";
    printArray(arr, size);

    quickSort(arr, 0, size - 1);

    cout << "排序后：";
    printArray(arr, size);

    return 0;
}

? 快速排序的亮点：

✨ 平均时间复杂度是 O(n log n)，比冒泡、选择、插入快多了
✨ 思维训练非常棒，能让孩子理解“递归”、“分治”这些计算机里超重要的概念
✨ 排序速度快到像忍者一样，一刀两断！

? 小贴士（写给小朋友）：

• 快速排序不是看谁速度快，而是分组分得妙！

• 每次都找个“中间人”（pivot）当小组长

• 小组长左边的都比它小，右边的都比它大

• 然后大家继续自己选小组长，分分分！

? 小小挑战题：

动手把 [10, 7, 8, 9, 1, 5] 用快速排序排一排~
写代码前，先在纸上模拟一遍，看看分成了哪几组，最后拼成啥样？