排序n个值所需的比较数?

正常选择排序要求 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

算术级数之和(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)

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

在您的选择排序版本中,首先必须选择两个元素作为 minimum 和 maximum ,并且在最坏的情况下,可以将未排序数组中的所有剩余元素与这两个元素进行比较。

让我们假设 k 元素保留在未排序的数组中,假设您选取前两个元素并相应地将它们分配给 最低限度 和 最大限度 (1比较),然后迭代 k-2 元素,每个元素可以产生两个比较。

因此,此迭代的总比较将是 = 1 + 2*(k-2) = 2*k - 3 比较。

在这里 K 将值作为 n, n-2, n-4, ... 因为在每次迭代中,两个元素都进入了正确的位置。求和的结果大约是 O(n^2) 比较。