计数快速排序比较

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