C++ 快速排序比较次数计算错误：修正代码实现

#include #include

using namespace std;

int quickSortComparisons(vector& arr, int start, int end) { if (start >= end) { return 0; }

int comparisons = 0;
int pivot = arr[start];
int i = start + 1;
int j = end;

while (i <= j) {
    while (i <= j && arr[i] <= pivot) {
        i++;
        comparisons++;
    }

    while (i <= j && arr[j] > pivot) {
        j--;
        comparisons++;
    }

    if (i < j) {
        swap(arr[i], arr[j]);
        comparisons += 2; // 加上交换的比较次数
    }
}

swap(arr[start], arr[j]);
comparisons += 2; // 加上交换的比较次数

comparisons += quickSortComparisons(arr, start, j - 1);
comparisons += quickSortComparisons(arr, j + 1, end);

return comparisons;

}

int main() { int n; cin >> n;

vector<int> arr(n);
for (int i = 0; i < n; i++) {
    cin >> arr[i];
}

int comparisons = quickSortComparisons(arr, 0, n - 1);
cout << comparisons << endl;

return 0;

}

这段代码的问题在于在交换元素时没有记录比较次数。因此，在交换元素时需要将比较次数加上2而不是1。修改后的代码如下：

int quickSortComparisons(vector<int>& arr, int start, int end) {
    if (start >= end) {
        return 0;
    }

    int comparisons = 0;
    int pivot = arr[start];
    int i = start + 1;
    int j = end;

    while (i <= j) {
        while (i <= j && arr[i] <= pivot) {
            i++;
            comparisons++;
        }

        while (i <= j && arr[j] > pivot) {
            j--;
            comparisons++;
        }

        if (i < j) {
            swap(arr[i], arr[j]);
            comparisons += 2; // 加上交换的比较次数
        }
    }

    swap(arr[start], arr[j]);
    comparisons += 2; // 加上交换的比较次数

    comparisons += quickSortComparisons(arr, start, j - 1);
    comparisons += quickSortComparisons(arr, j + 1, end);

    return comparisons;
}