混合快速排序实现：分区大小调整后统计值异常问题求助

核心问题梳理 #

1. 分区判断逻辑完全写反 #

原代码里判断是否继续快排的条件是(lowIndex - highIndex) >= 100，但lowIndex永远小于等于highIndex，这个差值是负数，根本不可能满足>=100。这意味着不管数组多大，你的算法从头到尾只执行插入排序，调整阈值自然不会影响比较/交换次数。

正确的逻辑应该是：当当前分区的元素数量（highIndex - lowIndex + 1）≥阈值时，继续快排；否则用插入排序处理当前分区。

2. 插入排序错误地排序整个数组 #

原insertionSort方法直接对整个数组排序，但混合快排应该只处理当前递归的子分区（lowIndex到highIndex）。每次调用insertionSort(array)都会重新排一遍整个数组，既打乱了之前快排的结果，也让计数统计完全失真。

3. 分区函数漏处理最后一个元素 #

partition里的循环条件是j < highIndex，这会跳过highIndex位置的元素，可能导致排序错误（你当前没发现只是运气好）。正确的边界应该是j <= highIndex，确保所有元素都参与分区。

4. 插入排序的比较计数有遗漏 #

insertionSort的while循环里，key < array[j]这个比较只有在条件成立进入循环体时才计数。如果key >= array[j]，这次比较没被统计，导致比较次数少算。

修正后的代码 #

public class QuickSort100 {

    int comparisonCount = 0;
    int swapCount = 0;

    public void quicksort(int[] array, int lowIndex, int highIndex) {
        // 计算当前分区大小，判断是否继续快排
        int partitionSize = highIndex - lowIndex + 1;
        if (partitionSize >= 100) {
            int index = partition(array, lowIndex, highIndex);
            if (lowIndex < index - 1) {
                quicksort(array, lowIndex, index - 1);
            }
            if (index < highIndex) {
                quicksort(array, index, highIndex);
            }
        } else {
            // 仅对当前子分区执行插入排序
            insertionSort(array, lowIndex, highIndex);
        }
    }

    // 插入排序改为处理指定区间
    public void insertionSort(int[] array, int low, int high) {
        int i, j, key, temp;
        // 从分区的第二个元素开始遍历
        for (i = low + 1; i <= high; i++) {
            key = array[i];
            j = i - 1;
            // 修正计数逻辑：每次比较都统计
            while (j >= low) {
                comparisonCount++;
                if (key < array[j]) {
                    // 交换元素
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    j--;
                    swapCount++;
                } else {
                    // 不需要交换，直接退出循环
                    break;
                }
            }
        }
    }

    public int partition(int[] array, int lowIndex, int highIndex) {
        int pivot = array[lowIndex];
        int i = lowIndex + 1;

        // 修正循环边界，处理到highIndex的元素
        for (int j = lowIndex + 1; j <= highIndex; j++) {
            comparisonCount++;
            if (array[j] < pivot) {
                swap(array, i, j);
                swapCount++;
                i++;
            }
        }
        swap(array, lowIndex, i - 1);
        swapCount++;
        return i;
    }

    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    // 新增重置计数方法，方便多次测试
    public void resetCounts() {
        comparisonCount = 0;
        swapCount = 0;
    }
}

测试注意事项 #

1. 修正后，调整阈值（比如改成50或200），比较和交换次数会随阈值变化：阈值越小，插入排序用得越多，比较次数会增加但交换次数可能减少（插入排序在接近有序的数组上交换少）。
2. 每次测试前调用resetCounts()，避免多次测试的计数累加。
3. 现在插入排序只处理当前子分区，不会打乱之前快排的结果，计数统计也更准确。

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