c++ - 如何计算快速排序算法中的比较次数？

Question

我有以下快速排序算法：

int quicksort(int data[], size_t n, int &counter)
// Library facilities used: cstdlib
{
    
    size_t pivot_index; // Array index for the pivot element
    size_t n1;          // Number of elements before the pivot element
    size_t n2;          // Number of elements after the pivot element

    if (n > 1)
    {
        // Partition the array, and set the pivot index.
        partition(data, n, pivot_index, counter);
        

        // Compute the sizes of the subarrays.
        n1 = pivot_index;
        n2 = n - n1 - 1;

        // Recursive calls will now sort the subarrays.
        quicksort(data, n1, counter);
        quicksort((data + pivot_index + 1), n2, counter);
    }

    return counter; 
}
void partition(int data[], size_t n, size_t& pivot_index, int &counter){
    
    int pivot = data[0]; 
    size_t too_big_index = 1;
    size_t too_small_index = n - 1;

    while (too_big_index <= too_small_index)
    {
        
        while (++counter && (too_big_index < n) && (data[too_big_index] <= pivot)) too_big_index++;
     
        while (++counter && data[too_small_index] > pivot  ) too_small_index--;
       
        counter++;
        if (too_big_index < too_small_index) swap(data[too_big_index], data[too_small_index]);
    };

    pivot_index = too_small_index;
    data[0] = data[pivot_index];
    data[pivot_index] = pivot;

    
}

我在分区函数中添加了三个计数器增量，但是当使用 8000 个元素的排序数组时，计数器的值是 32019997，我使用的是最左边元素的枢轴（我知道这给了我一个就排序数组而言是最坏的情况），除非我不正确，否则最坏的情况不应该是 n^2 即 64000000 吗？所以我认为我计算比较的方式是错误的，但我不确定如何。

标签： c++