快速排序:分区分析

Question

我正在学习快速排序在算法4th的课程中，罗伯特·塞奇威克。

我想知道快速排序代码的以下分区是长度为 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比较。

原因是，在已经排序的数组(如数组 (A，B，C，D，E，F，G，H((中，i从左向右移动和j分别从右向左移动需要 N 比较。

比较 = 更少((

Answer 1

此分区函数的时间复杂度T(n) = O(n)

Answer 2

我的上帝，这是我在i迭代中的错误.

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

所以，它需要~n比较。