c++ - 计算快速排序中的比较次数

Question

我有一个作业，需要使用三种分区策略实现快速排序，并计算每种策略的比较次数。

为了简单起见，每次对长度为 m 的数组进行递归调用时，我们都会被要求将 m-1 添加到计数中。

我的代码总是返回负数，这不是整数溢出问题。
我用了long long int，现在还保留着它，而且比较次数不可能增长那么多，所以我的计数方式有问题。

在调用我的实现后，我使用 is_sorted 在 100000 个元素数组上测试了代码，并且通过了，因此排序是正确的
这是我的代码:

long quick_sort (vector <int>& A, int l , int r){
    static  long count = 0;
    if ( r<= l)
        return 0;

    //partition
    int i = partition(A, l, r);

    //quicksort left
    int amount = ( ((i -1) -l) >= 0 ?
                            ((i-1) -l) :
                                    0);
    count += amount;
    quick_sort (A,l, i-1);

    //quicksort right
    amount = ((r - (i +1)) >= 0 ?
                        (r - (i +1)) :
                                  0);
    count += amount;
    quick_sort (A,i+1, r);

    return count;

}

Answer 1

更改测试值以保持正确的表达式:

count += ( (i-1)-l >= 0 ? (i-1)-l : 0 )
quick_sort (A,l, i-1);

和

count += ( r-(i+1) >= 0 ? ...
quick_sort (A,i+1, r);