快速排序：分區分析

我正在學習算法第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

快速排序：分區分析

回答

相關問題