如何正确统计快速排序（quicksort）算法执行过程中的比较次数？

核心问题定位 #

你代码里的count++放置逻辑存在缩进语法错误：Java中没有用花括号包裹的循环/分支结构，仅会将紧接的第一行代码识别为循环体，你写的两个比较搜索循环的count++都不属于循环内部，无论单次循环做了多少次元素比较，最终只会各累加1次，自然统计结果远低于实际值。

你当前的写法等价于以下逻辑：

// 搜索大于基准值的元素
while (left < right && data[left] <= partitionelement) {
    left++;
}
count++; // 仅在循环退出时计数1次，而非每次比较都计数

// 搜索小于基准值的元素
while (data[right] > partitionelement) {
    right--;
}
count++; // 同上仅计数1次

修复方案 #

给两个搜索循环加上花括号，将count++移动到循环内部，每次元素比较时就累加计数。如果只统计待排序元素之间的比较次数（索引大小比较不计入），修改后的循环代码如下：

while (left < right) {
    // 搜索大于基准值的元素
    while (left < right) {
        count++; // 每次元素比较计数+1
        if (data[left] <= partitionelement) {
            left++;
        } else {
            break;
        }
    }
    // 搜索小于等于基准值的元素
    while (true) {
        count++; // 每次元素比较计数+1
        if (data[right] > partitionelement) {
            right--;
        } else {
            break;
        }
    }
    // 交换元素
    if (left < right) 
        swap(data, left, right);
}

效果验证 #

快速排序的平均比较次数约为1.39nlog₂n，80个元素的平均比较次数约为700次左右，受基准值选择、数组有序性影响会在1000上下浮动，修改计数逻辑后统计结果就会匹配预期。

内容的提问来源于stack exchange，提问作者mFuchs