Selection Sort（选择排序）求和公式推导及结果含义咨询

1. 求和式化简与n-i-1项推导 #

先结合选择排序的执行逻辑拆解：

• 选择排序的核心流程是逐轮确定未排序区间的最小值，放到已排序区间的末尾。如果采用0基数组下标，外层循环变量i代表当前已完成排序的前缀长度，本轮要确定下标i位置的最终值。
• 本轮的未排序区间范围是下标i+1到下标n-1，要找到这个区间的最小值，必须将下标i的元素和区间内所有元素逐一比较，比较次数等于区间内的元素总数。计算区间元素数：末项下标减首项下标加1，也就是(n-1) - (i+1) + 1 = n - i - 1，这就是求和式中n-i-1项的来源。
• 总比较次数的求和式为外层循环遍历所有需要排序的轮次：i从0到n-2（最后剩余1个元素时无需比较，天然有序），累加每轮比较次数：

S(n) = Σ(i=0 → i=n-2) (n - i - 1)

做变量替换，令k = n - i -1，当i=0时k = n-1，当i=n-2时k=1，求和顺序反转不影响结果，因此式子可以化简为从1累加到n-1的等差数列：

S(n) = 1 + 2 + 3 + ... + (n-1) = n(n-1)/2

2. n=8时展开式的实际意义 #

当数组长度n=8时，展开式(8-1)+(8-2)+(8-3)+…是逐轮比较次数的直接枚举：

• 第1轮：全数组未排序，找最小值需要做7次比较，对应8-1=7
• 第2轮：剩余7个未排序元素，找最小值需要做6次比较，对应8-2=6
• 第3轮：剩余6个未排序元素，找最小值需要做5次比较，对应8-3=5
• ……
• 倒数第2轮：剩余2个未排序元素，找最小值需要做1次比较
• 最后1轮：仅剩1个元素，无需比较

累加所有轮次的结果为7+6+5+4+3+2+1=28，和等差数列公式计算结果8*7/2=28完全一致。

这个结果的实际含义是：对长度为8的数组执行选择排序，无论数组初始的有序程度如何，排序全程都需要完成28次元素比较。比较次数和输入序列的初始状态无关，是选择排序区别于冒泡、插入排序的典型特征，对应其稳定的O(n²)时间复杂度。

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