計算快速排序比較

Question

我實現了一個簡單的快速排序（下面的代碼）來計算由quicksort進行的平均和最差比較。我宣佈了一個全局變量來存放用於比較的計數器。我將3個計數器置於不同的位置，我認爲會計算比較結果，問題是計數器總數與快速排序進行的比較總數的理論值不匹配。我試圖解決這個問題好幾個小時，但總結出來了。我非常感謝，如果你能指出我應該把櫃檯放在哪裏，爲什麼我應該把它們放在那裏。我假設一個櫃檯應該去哪裏進行比較。顯然我錯了。

public int[] quickSort(int[] array, int start, int end){ 


    if (start < end){ 
     counter++;//1st comparison here 
     int pivot; 

     pivot = Partition(array, start, end); 
     quickSort(array, start, pivot - 1); 
     quickSort(array, pivot + 1, end); 
    } 
return array; 
} 

private int Partition(int[] array, int start, int end) { 
    int pivot = array[end]; 
    int i = start - 1; 

    for(int j = start; j <= end - 1; j++){ 

     counter++;//2nd comparison here 


     if (array[j] <= pivot){ 
      counter++;//3rd comparison here 
      i = i + 1; 

      int temp = array[i]; 
      array[i] = array[j]; 
      array[j] = temp; 
     } 

    } 

    int temp = array[i+1]; 
    array[i+1] = array[end]; 
    array[end] = temp; 

    return i + 1; 
} 

Answer 1

對於理論，只有數組元素的比較都算，指數不攀比界限，所以你應該只留下第二counter++;（你需要獨立遞增的結果的計數器比較）。

然後就是你比較哪個理論值的問題。有不同的quicksort實現使用稍微不同數量的比較。特別是，你選擇的pivot不會避免極端的值，所以這個實現很容易降級到O（n^2）行爲。