哪种排序算法对数组扰动最小？相关考题疑问求解

你的判断完全正确，这道在线答题的题目选项设置存在明显疏漏，没有给出对应正确答案。

判定依据 #

首先明确题目语境下的「扰动人数」定义：排序全过程中被移动过位置、最终未留在初始座位的总人数，核心要求是让原本就处于正确位置的人尽可能不被挪动。
我们逐个对照四种算法的实际表现：

• 选择排序（selection sort）：是四个算法里唯一满足最少扰动要求的算法。它的核心逻辑是每轮遍历未排序区间定位目标元素，仅将目标元素和未排序区间首位做直接交换，所有已经处于正确位置的元素从始至终不会被触碰。如果序列中仅有k个位置错乱的元素，选择排序最多仅需k次交换，扰动总人数不会超过2k，是理论上扰动最少的排序方案之一，你的代码验证结论完全准确。
• 冒泡排序（bubble sort）：依赖相邻元素交换完成排序，当错位元素距离其正确位置较远时，交换过程会连带挪动大量原本处于正确位置的相邻元素，扰动人数远高于实际错乱人数，并不理想。
• 堆排序（heap sort）：建堆和排序阶段的下沉/上浮操作会对全范围元素做无差别调整，哪怕序列仅有极少数元素错乱，也会挪动绝大多数位置正确的元素，扰动规模极大，完全不符合需求。
• 归并排序（merge sort）：分治合并阶段需要对段内元素做整体搬运，哪怕是原地归并实现，也会在跨段合并时移动大量本就位置正确的元素，扰动人数远高于最优水平，并不理想。

举个简单的测试样例就能直观看到差异：初始序列为['A', 'D', 'C', 'B', 'E']，正确排序为['A','B','C','D','E']，实际位置错乱的只有B、D两个人：

1. 选择排序执行时，A在正确位置不动，第二轮找到B在索引3，和索引1的D交换后序列直接有序，全程只移动了B、D两个人，其余人全程未动。
2. 冒泡排序执行时，B从索引3移动到索引1的过程中，会先和C交换（原本在正确位置2的C被挪到索引3），后续D还要再和C交换回到索引3，全程B、D、C三个人都被移动，扰动人数更高。
3. 堆排序建堆阶段就会调整除A、E外的所有元素位置，扰动人数超过总人数的一半。
4. 归并排序合并子数组时，会对D、C、B三个元素做重新写入，原本位置正确的C也会被移动，扰动同样高于选择排序。

题目存在的问题 #

这道题的设问是问「哪种算法并不理想」，但实际不理想的算法包含冒泡排序、堆排序、归并排序三种，选项既没有给出这个正确组合，给出的「以上所有算法扰动的人数大致相当」选项也完全不符合算法的实际特性，属于题目设置错误。

内容的提问来源于stack exchange，提问作者anantdd