企业官网建设流程全解析

1. 引言

上篇博客我们聊了插入排序，那种像打扑克牌一样，把新牌一张张插到合适位置的感觉，相信大家还记忆犹新。今天，我们换个思路，来聊聊另一种同样经典的基础排序算法——选择排序。

如果说插入排序是"边摸牌边整理"，那选择排序更像是"挑最顺眼的先拿走"。它的思路非常直观：每一轮都从剩下的元素里挑出最小的那个，放到前面去。就像我们在宿舍里整理书架，每次都从乱堆里挑出最薄的一本书放到最左边，一本一本排好。

2. 选择排序的基本思想

选择排序的核心思想可以用一句话概括：每一轮从未排序区间中选出最小值，放到已排序区间的末尾。

具体来说，假设我们有一个长度为 n 的数组，排序过程分为 n-1 轮：

• 第 1 轮：在全部 n 个元素中找出最小值，与第 1 个位置交换；
• 第 2 轮：在剩下的 n-1 个元素中找出最小值，与第 2 个位置交换；
• 第 3 轮：在剩下的 n-2 个元素中找出最小值，与第 3 个位置交换；
• ……
• 第 n-1 轮：在剩下的 2 个元素中找出最小值，与第 n-1 个位置交换。

经过 n-1 轮之后，最后一个元素自然就是最大值，排序完成。

2.1 一个直观的比喻

想象你在整理一摞试卷，要从乱序的卷子里按分数从低到高排好：

1. 先扫一遍所有试卷，找出分数最低的那张，放到最上面；
2. 再从剩下的试卷里找出分数最低的，放到第二张的位置；
3. 重复这个过程，直到所有试卷排好。

这个过程就是选择排序的生动写照——每次只做一件事：找到当前最小的，放到它该去的位置。

2.2 动图

3. 图解选择排序过程

为了让大家看得更清楚，我们用一个具体例子来走一遍完整流程。

假设数组为：[5, 3, 8, 1, 2]，长度为 5，需要 4 轮排序。

第 1 轮：在[5, 3, 8, 1, 2]中找最小值1，与第 1 个元素5交换：

[1, 3, 8, 5, 2]

第 2 轮：在[3, 8, 5, 2]中找最小值2，与第 2 个元素3交换：

[1, 2, 8, 5, 3]

第 3 轮：在[8, 5, 3]中找最小值3，与第 3 个元素8交换：

[1, 2, 3, 5, 8]

第 4 轮：在[5, 8]中找最小值5，与第 4 个元素5交换（位置不变）：

[1, 2, 3, 5, 8]

排序完成！可以看到，每一轮结束后，前面就多了一个已经排好序的元素。

下面是整个过程的流程图：

4. 代码实现

voidSwap(int*x,int*y)//交换两数据位置{inttemp=*x;*x=*y;*y=temp;}voidSelectSort(int*arr,intn)//简单选择排序{if(arr==NULL||n<=1)return;//1.核心思想是在未排序数据中选出最大/小的值，并与待交换数据交换位置，与插入排序的差别之一就是，插入排序比较过程中需要将元素后移，直到遇到合适位置插入// 选择排序是先比较完，然后将单趟最值与某值交换位置，因此同样需要区分已排序和未排序区域for(inti=0;i<n-1;i++)//同样的，防止越界{intmin=i;//2.定义当前最小值的位置for(intj=i+1;j<n;j++)//3.寻找未排序数据中的最小值{if(arr[j]<arr[min]){min=j;//4.如果有，就定义新的最小值的位置}}//5.比完以后得到本次最小值的位置，与原本的最小值交换位置if(min!=i){Swap(&arr[min],&arr[i]);}}}

4.3 代码要点总结

• 外层循环i表示已排序区间的末尾位置，从 0 到 n-2；
• 内层循环j负责在未排序区间中扫描，记录最小值下标min；
• 每一轮最多交换一次，这是选择排序与冒泡排序的重要区别（冒泡可能一轮交换多次）。

5. 复杂度分析

5.1 时间复杂度

• 最好情况：O(n²)。即使数组已经有序，内层循环依然要完整扫描未排序区间，无法提前终止。
• 最坏情况：O(n²)。无论数据怎么分布，比较次数都是固定的。
• 平均情况：O(n²)。

具体来说，比较次数恒为n(n-1)/2，与数据初始顺序无关；交换次数最多为n-1次（每轮最多一次）。

5.2 空间复杂度

• 空间复杂度：O(1)，只需要一个临时变量用于交换，属于原地排序算法。

5.3 稳定性分析

选择排序是不稳定的。举个例子：数组[5a, 5b, 1]（两个 5 用 a、b 区分），第一轮找到最小值1与第一个5a交换，得到[1, 5b, 5a]，此时两个 5 的相对顺序发生了改变。这一点在面试中经常被问到，大家要特别注意。

有同学会问：如果把内层循环的比较条件从<改成<=，能否让选择排序变稳定？

答案是不能。选择排序的不稳定性根源在于交换操作，而不是比较条件。即使你用<=让内层循环在遇到相等元素时也更新min下标，也只是改变了"选哪个相等元素"的策略，但交换本身依然可能破坏相对顺序。

以数组[5, 6, 5, 0, 2, 0, 3]为例，给相同元素编号：[5a, 6, 5b, 0a, 2, 0b, 3]：

• 第 1 轮：找最小值0a，与第 1 个元素5a交换，得到[0a, 6, 5b, 5a, 2, 0b, 3]。此时5a被换到了5b的后面，两个 5 的相对顺序已被破坏；而这一轮0a和0b的相对顺序反而保住了。
• 第 2 轮：在[6, 5b, 5a, 2, 0b, 3]中找最小值0b，与第 2 个元素6交换，得到[0a, 0b, 5b, 5a, 2, 6, 3]。这一轮0b又被换到了0a的后面，两个 0 的相对顺序也被破坏了。

可以看到：即使能保证某一组相同元素的相对顺序，也无法同时保证所有组的相对顺序。因为每一轮交换都会把"当前最小值"从后面直接"跨越"到前面，跨越过程中会越过所有其他元素——包括与它值相同的元素。

• 用<时，相等元素不会被选中，相对顺序靠"运气"；
• 用<=时，相等元素会被选中（选最后一个），虽然可能保住某一组的顺序，但其他组的顺序照样会被交换破坏。

所以，只要选择排序采用"交换"来实现，它就注定不稳定。要让选择排序变稳定，必须改用"插入"的方式（把最小值前面的元素整体后移，再把最小值放进去），而不是交换——但那样它就不再是经典的选择排序了。

用循环不变量再证一遍

上面的例子已经足够直观，但如果你想让论证更严谨，可以用循环不变量来证明：无论比较条件用<还是<=，选择排序都不可能是稳定的。

先回顾一下选择排序外层循环的不变量：

循环不变量：在第i轮开始前（即i次交换完成后），数组的前i个位置已经排好序，且它们恰好是原数组中最小的i个元素；剩余n-i个元素仍在未排序区间[i, n-1]中。

这个不变量在初始化（i=0时前 0 个元素自然有序）、保持（每轮把未排序区间的最小值放到i位置）、终止（i=n-1时前n-1个元素有序，最后一个自然最大）三个阶段都成立，所以它保证了排序的正确性。

但注意：这个不变量只约束了"哪些值"被放到了前面，完全没有约束"相同值的相对顺序"。它只保证前i个位置是"最小的 i 个元素"，至于这些相等元素谁先谁后，不变量一概不管。

现在我们来证明不稳定。考虑任意一轮i，设未排序区间[i, n-1]中存在两个相等的元素x和y，且x在y的前面（x的下标更小）。这一轮要选出的最小值记为m，分两种情况：

• 情况一：m就是x或y本身。假设选中的是y（即y是未排序区间的最小值，且x与它相等）。交换后y被放到位置i，而x留在原地。由于x原本在y前面，交换后y跑到了x的前面，两者相对顺序被破坏。
• 情况二：m是另一个更小的元素。此时m会被交换到位置i，而x、y的相对位置在这一轮保持不变。但注意：这一轮没有破坏它们，不代表后面不会破坏。在后续某一轮i'，当x或y成为未排序区间的最小值被选中并交换到前面时，就会发生情况一，破坏它们的相对顺序。

换句话说：只要存在两个相等的元素，且它们不是同一轮被同时选中（选择排序每轮只选一个最小值，永远不可能同时选中两个），那么迟早有一轮会把其中一个"跨越"到另一个的前面。这正是选择排序"交换"实现的本质缺陷。

所以结论是：循环不变量只能证明选择排序"排对了"，却无法证明它"排得稳"。稳定性需要的是"相等元素相对顺序不变"这一条额外约束，而选择排序的交换操作天然无法保证这一点。这也解释了为什么面试中"稳定性"和"正确性"是两个独立的问题——一个算法可以正确但不稳定。

6. 选择排序 vs 插入排序

上篇我们学了插入排序，这里把两者放在一起对比，方便大家记忆：

小贴士：如果交换两个元素的代价很大（比如元素是复杂对象），选择排序的交换次数少，反而可能比插入排序更合适；但如果数据基本有序，插入排序凭借提前终止的优势会快很多。

7. 常见面试考点

选择排序虽然简单，但面试官经常从它入手考察基础功底：

1. 手写代码：要求在白板上写出完整实现，注意边界条件i < n-1和j < n。
2. 稳定性判断：能举出反例说明它不稳定。
3. 复杂度推导：能说出比较次数恒为n(n-1)/2。
4. 优化思路：能否想到"同时找最大值和最小值"的优化版本（每轮找最大和最小，可减少一半轮次）。
5. 与其它排序对比：能清晰说出选择、插入、冒泡三者的区别。

8. 总结

选择排序是算法入门路上绕不开的一块基石。它的思想朴素而优雅——每次只做一件最简单的事，重复 n-1 次，就能完成整个排序。

回顾一下今天的关键点：

• 核心思想：每轮从未排序区间选最小值，放到已排序区间末尾；
• 时间复杂度：无论好坏都是 O(n²)；
• 空间复杂度：O(1)，原地排序；
• 稳定性：不稳定；
• 与插入排序相比，交换次数更少，但无法利用数据的有序性。

下篇博客，我打算写冒泡排序，把这三个 O(n²) 的基础排序放在一起做个对比