选择排序随机平均情况低于预期，插入排序交换次数存疑

嘿，我来帮你拆解这个问题——你觉得随机数组的插入排序交换次数应该在0到400万之间波动，但实际测出来只有约4000次，这里面有两个核心点：一是你对「平均情况」的预期错了，二是你的测试结果大概率存在统计偏差。

首先，先明确插入排序里「交换次数」的定义：如果你的实现是通过相邻元素两两交换把当前元素挪到正确位置（比如每次把当前元素和前一个更大的元素交换，直到找到合适位置），那交换次数其实等于数组里的逆序对数量——每一次交换都会消除一个逆序对。

随机数组的逆序对预期值是多少？ #

对于包含n个不同元素的随机排列，逆序对的数学期望是 n*(n-1)/4。拿你说的2000个元素来算：

2000 * 1999 / 4 = 999500

也就是说，随机数组的平均交换次数应该接近100万次，而不是你测出来的4000次。这说明你的统计逻辑或者测试设置肯定出了问题。

为什么你的结果偏差这么大？ #

常见的几个坑：

• 你统计的不是真正的「交换次数」：如果你的插入排序是先把当前元素存起来，然后把前面比它大的元素向后移动（而不是两两交换），那你可能误把「插入操作的次数」当成了交换次数。比如2000个元素最多只会有2000次插入操作，但这和真正的相邻交换次数完全不是一个概念。
• 随机数组生成有问题：比如你生成的数组不是完全随机的排列，而是有大量有序片段，或者重复元素特别多（重复元素不会产生逆序对），这会大幅减少逆序对的数量。
• 统计代码有bug：比如计数器没有正确累加，或者在排序过程中被意外重置了。

怎么验证问题出在哪？ #

给你几个小测试思路：

1. 测最坏情况：拿一个完全逆序的2000元素数组跑排序，看看统计的交换次数是不是2000*1999/2 = 1999000（逆序数组的逆序对总数是这个数）。如果不是，那你的统计逻辑肯定错了。
2. 测极小数组：比如拿n=5的随机数组，手动数出逆序对数量，再和你的统计结果对比，看能不能对上。
3. 检查数组生成逻辑：确保你用的是真正的洗牌算法生成随机排列，而不是重复元素一堆的数组。

最后补充一句：随机数组的平均交换次数本来就远低于最坏情况——最坏情况是极端的逆序场景，而随机排列中大部分元素离正确位置都不远，逆序对的数量是平方级但系数很小（1/4），所以平均和最坏的差距大是正常的，只是你的测试结果明显偏离了理论值，得先排查统计问题。

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