快速排序：分区分析

Question

我正在学习算法 4 课程中的快速排序，Robert Sedgewick。

我想知道快速排序代码的以下分区在长度为N的数组中比较的次数。

private static int partition(Comparable[] a, int lo, int hi)
{
  int i = lo, j = hi+1;
  while (true)
  {
    while (less(a[++i], a[lo]))
      if (i == hi) break;

    while (less(a[lo], a[--j]))
      if (j == lo) break;

    if (i>= j) break;
    exch(a, i, j);
  }

  exch(a, lo, j);
  return j;
}

我想知道上面描述的代码的 T(n)。 （比较）

在我看来，需要~2N次比较。

原因是因为i从左到右移动需要N次比较，j从右到左移动分别需要N次比较在一个已经排序的数组如数组（A ,B,C,D,E,F,G,H).

compare = less()

Answer 1

这个配分函数的时间复杂度是T(n) = O(n)

Answer 2

我的天，我在i的迭代中失误了。

在寻找i停止的过程中，只需要1次比较。

所以，需要 ~N 次比较。