算法：选择排序（以排队为例）

举个栗子🌰：体育课排队

假设体育老师要按身高从高到矮给10个同学排队（降序排序），老师会这样做：

1. 第1轮：找全班最高的同学，让他站在第1个位置
2. 第2轮：在剩下的9人中找最高的，站到第2个位置
3. 第3轮：在剩下的8人中找最高的，站到第3个位置
   ......
   直到所有人排好队

代码对应的现实操作

①形参是数组名

void sort(int x[], int n) {
    int i, j, k, t;
    for (i=0; i<n-1; i++) {       // 老师指挥排第i个位置
        k = i;                    // 老师用手指着当前最左边同学："假设你是现在最高的"
        for (j=i+1; j<n; j++)     // 从下一个同学开始比较
            if (x[j] > x[k])      // 发现更高的同学
                k = j;            // 老师立刻改指这个更高的同学："你才是最高的！"
        if (k != i) {             // 如果最高同学不在当前位置
            t = x[i];             // 让最高同学和当前位置的同学
            x[i] = x[k];          // 交换位置（矮的去后面）
            x[k] = t;             
        }
    }
}

动画演示：数组 [5,3,8,1] 的排序过程

关键比喻解释

• 变量k：老师手里的激光笔，专门指着当前找到的最高同学
• 外层循环i：老师正在安排第几个位置（从第1个到倒数第2个）
• 内层循环j：老师挨个检查后面的同学有没有更高的
• 交换操作：让更高的同学和当前位置的同学换位置

为什么叫选择排序？

因为每一轮都在 选择 当前未排序部分的最大值（就像老师选最高的同学），放到已排序部分的末尾。

常见疑问解答

Q1：为什么外层循环到n-1就停止？

因为排好前n-1个后，最后一个位置自然就确定了，不需要再处理。

Q2：k变量有什么用？

k像书签一样标记着当前找到的最大值位置，避免频繁交换。

Q3：时间复杂度为什么是O(n²)？

假设有n个元素：

• 第1轮比较n-1次
• 第2轮比较n-2次
• ...
• 总比较次数 = (n-1)+(n-2)+...+1 = n(n-1)/2 ≈ n²

②形参是指针变量 

终极比喻：排队游戏

假设你有一队学生 [4, 2, 7, 1]（数字代表身高），你要按身高从高到低重新排队。选择排序的玩法是：

第1轮：选全场最高的当排头

1. 你站在队伍最前面（位置0），喊：“谁比我高？出列！”
   • 第1个学生（4）自己先当排头。
   • 第2个学生（2）没他高 → 不动。
   • 第3个学生（7）更高 → 排头换成他！
   • 第4个学生（1）更矮 → 不动。
2. 交换位置：把7和4的位置交换 → 队伍变成 [7, 2, 4, 1]。

第2轮：在剩下的人里选最高的

现在前1个位置（7）已经固定，不管了。你站到第2个位置（位置1），喊：“剩下的人里谁比我高？”

• 当前排头是位置1的2。
• 位置2的4更高 → 排头换成他！
• 位置3的1更矮 → 不动。
• 交换位置：4和2交换 → 队伍变成 [7, 4, 2, 1]。

第3轮：继续缩小范围

现在前2个位置（7,4）固定。你站到第3个位置（位置2），喊：“剩下的人里谁比我高？”

• 当前位置2的值是2，剩下的只有位置3的1 → 没人更高。
• 不用交换，保持不动。

代码对应关系

• i：你当前站的位置（从0开始）。
• k：临时记录的“最高者位置”。
• j：用来遍历剩下的人，找更高的。
• t：交换时的临时工具人（比如一张椅子，用来暂时放人）。

再拆解代码关键行

c复制代码

if (*(x + j) > *(x + k)) k = j;  // 发现更高的人，更新k

👉 等价于：
“如果第j个人的身高 > 当前记录的k位置的身高，就让k记住j的位置！”

终极总结

代码的每一轮都在做三件事：
1️⃣ 定位：确定当前要排的位置 i。
2️⃣ 找人：在剩下的范围里找到最大值的下标 k。
3️⃣ 交换：把最大值扔到 i 的位置。