java - 计算快速排序比较

Question

我实现了一个简单的快速排序(下面的代码)来计算快速排序所做的平均比较和最差比较。我声明了一个全局变量来保存用于比较的计数器。我在不同的位置放置了 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++;(你需要独立地递增计数器比较结果)。

然后是您比较哪些理论值的问题。快速排序有不同的实现，它们使用的比较次数略有不同。特别是，您对枢轴的选择不会试图避免极值，因此此实现很容易退化为 O(n^2) 行为。