为何含1~n两副本的数组选择排序比较次数为n²而非4n²？

为什么你的4n²结论错误 #

选择排序的比较次数是固定值，和数组初始状态无关：对于长度为m的数组，每一轮会遍历未排序区间找最小值，第1轮比较m-1次，第2轮比较m-2次，直到最后1轮比较1次。总比较次数是等差数列求和：

(m-1)+(m-2)+...+1 = m(m-1)/2

你的问题中数组长度m=2n，代入后总比较次数为：

2n(2n-1)/2 = 2n² -n

你误以为是4n²，是错误地将每一轮的比较次数当成了2n次，再乘以2n轮，忽略了每一轮比较次数递减的事实，所以这个结论不成立。

关于“正确答案为n²”的解释 #

这里的n²是渐近复杂度的简化表述：

• 当n趋近于无穷大时，2n² -n中的主导项是2n²，低阶项-n可以忽略，因此该函数的渐近紧确界是Θ(n²)，日常表述中常简略为n²。
• 如果用波浪符号（~）表示渐近等价，严格来说应该是~2n²（因为lim(n→∞)(2n² -n)/2n²=1），但部分场景下会省略系数，只保留主导项的阶数，所以会被写成n²。

另外补充：这个特殊数组的交换次数是n次（每一对重复元素只需交换一次），但交换次数和比较次数是完全不同的概念，不要混淆。

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