选择排序的时间复杂度为什么不是n!（n阶乘）？

核心原因是你混淆了「总操作数的计算逻辑是加法还是乘法」，两者的量级天差地别：

• 选择排序每一轮的比较操作是累加计数的：你提到的迭代n次，每轮比较次数依次是n、n-1、n-2...1，总比较次数是等差数列求和：
  n + (n-1) + (n-2) + ... + 1 = n*(n+1)/2
  这个式子展开后是 (n² + n)/2，大O时间复杂度会忽略低阶项n和常数系数1/2，最终只保留最高阶的n²项，所以复杂度是O(n²)。
• n!是阶乘，对应的是操作数相乘的场景：比如穷举n个元素的全排列，第1层有n种选择、第2层有n-1种选择...最后1层有1种选择，总路径数是n * (n-1) * ... *1 = n!，这种乘法逻辑才会得到n!的量级，和选择排序的加法计算逻辑完全不同。

内容的提问来源于stack exchange，提问作者Loïc Rutabana