algorithm - 对 n 个值进行排序所需的比较次数？

Question

我正在研究修改后的选择排序算法，以便在每次传递时都能在数组的未排序部分 中找到最大值和最小值。然后，排序通过交换数组条目将这些值中的每一个移动到其正确位置。

我的问题是 - 对 n 个值进行排序需要进行多少次比较？

在正常的选择排序中，它是 O(n) 次比较，所以我不确定在这种情况下会发生什么？

Answer 1

正常选择排序需要 O(n^2) 比较。

在每次运行时，它都会进行 K 次比较，其中 K 是 n-1, n-2, n-3...1，并且这个算术级数的总和是 (n*( n-1)/2)

您的方法(如果您使用优化的最小/最大选择方案)每次运行使用 3/2*K 比较，其中运行长度 K 是 n, n-2, n- 4...1

a(1)=1,a(n/2)=n,d=2的等差数列和为3/2乘数是

 3/2 * 1/2 * (n+1) * n/2 = 3/8 * n*(n+1) = O(n^2)

所以复杂度仍然是二次的(并且因子非常接近标准)