已知数组洗牌方式，能否预判排序算法的交换次数或其上限？

一、基于算法特性直接计算交换次数（或上限） #

不同排序算法的交换次数和输入数组的逆序数、元素分布强相关，既然数组是你自己均匀随机洗牌的，直接用算法的理论特性就能推导：

• 冒泡排序

  • 精确交换次数：等于数组中的逆序数（每交换一次减少一个逆序对）。随机洗牌数组的逆序数期望值是 n*(n-1)/4（n为数组规模），可以直接拿这个当M的估算值。
  • 上限：最坏情况（完全逆序）下，交换次数是 n*(n-1)/2，这是绝对上限，不管数组怎么洗牌都不会超过。

• 选择排序

  • 精确交换次数：等于数组中不在正确位置的元素数减去循环节的数量，随机洗牌数组的期望值约为 n - H_n（H_n是第n个调和数，近似ln(n)+0.577）。
  • 上限：最坏情况（每个元素都不在原位）下，交换次数固定为 n-1。

• 插入排序

  • 精确交换次数：同样等于数组的逆序数，随机洗牌数组的期望值是 n*(n-1)/4，上限是 n*(n-1)/2（完全逆序）。

• 快速排序（Lomuto分区）

  • 精确交换次数：和分区策略有关，随机洗牌数组的期望值约为 n ln n。最坏情况（每次分区选到极值）下上限是 n*(n-1)/2，但随机洗牌后这种概率极低，实际可以用 2n ln n 当保守上限。

二、动态调整快照间隔的单次排序实现 #

如果不想依赖理论值，也能在单次排序过程中动态搞定，不用预跑：

1. 初始化交换计数器swap_count，用算法的期望值或上限当初始expected_m，算出初始N=ceil(expected_m/K)。
2. 每完成一次交换，swap_count加1，当达到N时拍快照，然后根据当前交换进度修正expected_m：
   • 比如冒泡排序，每轮遍历后统计已减少的逆序对比例，更新expected_m，再重新计算剩余需要的快照间隔，调整下一次的N值。
3. 全程只跑一次排序，就能完成所有快照拍摄。

三、百万级数组的额外优化建议 #

• 冒泡排序这类O(n²)算法本身就不适合百万级规模，优先换用O(n log n)的算法（比如快速排序、归并排序），它们的交换次数理论值更稳定，上限也低很多，快照逻辑更容易实现。
• 如果必须用冒泡排序，直接拿最坏情况上限n*(n-1)/2计算N就行，虽然前期快照间隔会略大，但省掉了预跑的额外耗时。对于随机洗牌的数组，实际交换次数接近期望值，后期可以微调N补拍几次快照。

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