快速排序：分区分析

我正在学习算法第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; 
}

我想知道Ť比较的数量（n）的代码，如上所述。（对比）

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

原因是因为它需要N比较i从左向右移动，并且j分别从已经排序的数组（例如数组（A，B，C，D，E， F，G，H）。

比较少=（）

来源

2017-03-18 progresivoJS

你是什么意思'数组中的比较数？ – lsof

是'number of compare'被引用'if（i> = j）break;'statement？ – lsof

@RajasubaSubramanian只有'less（）'。那么比较的数量是多少？ – progresivoJS

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

来源

2017-03-19 04:56:52

在波浪符号（包括常量）中，T（n）是什么？ – progresivoJS

由于n比较需要〜N。 –

是的，这是我的错误。 – progresivoJS

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

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

所以，它需要〜N比较。

来源

2017-03-19 05:07:00 progresivoJS

快速排序：分区分析

回答

相关问题