arrays - 选择排序数组比较

Question

嗨 Stack Overflow 的用户，

我试图找出如何计算出一个方法中发生了多少数组比较。arrayMaxPos 函数进行 n-1 次比较以找到大小为 n 的数组中的最大元素。

我只是想弄清楚这一点。

public static void SelectSort(int [] a, int n)
  {
    for (int i = n; i> 1; i--)
    {
      int maxPos = arrayMaxPos(a, i);
      swop(a, maxPos, i-1);
    }
  }

非常感谢。

Answer 1

我认为那将是 ((N-1)^2)/2 比较。

Answer 2

您可以通过调试代码或简单地将打印语句放在中间来分析您自己的代码。并为您的答案-选择排序采用n(n − 1) / 2对数组进行排序

Answer 3

您的外部循环正在进行 n-1 次迭代。您的内部循环 (arrayMaxPos(...)) 从 n 变为 1，因此为 n/2。

因此，正如已经解释过的其他一些答案：n(n-1)/2