计算快速排序比较

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）行为。