如何移除快速排序while循环中的if语句以降低复杂度？

嘿，我完全理解你想简化快速排序、移除while循环内if语句的诉求——减少分支判断不仅能让代码更简洁，还能在一定程度上提升执行效率。咱们结合你提到的Smaller和Bigger索引逻辑，一步步调整分区实现：

先梳理你当前的核心逻辑 #

你目前的分区思路是：用双指针遍历数组，遇到大于pivot的元素就交换，最终Bigger停在分界点。原代码大概类似这样（带if分支的版本）：

public int partition(int[] sortArray, int low, int high) {
    int pivot = sortArray[high];
    int smaller = low - 1;
    int bigger = low;
    while (bigger < high) {
        // 这里的if是你想移除的分支
        if (sortArray[bigger] <= pivot) {
            smaller++;
            swap(sortArray, smaller, bigger);
        }
        bigger++;
    }
    swap(sortArray, smaller + 1, high);
    return smaller + 1;
}

移除while循环内if的实现方案 #

我们可以把分支判断整合到指针移动的循环条件中，用两个独立的do-while分别定位需要交换的元素，这样外层while循环内就不需要额外的if判断了：

public int partition(int[] sortArray, int low, int high) {
    // 选中间位置作为pivot，避免极端情况导致的性能退化
    int pivot = sortArray[(low + high) / 2];
    int smaller = low;
    int bigger = high;

    while (smaller < bigger) {
        // 从左向右找第一个大于等于pivot的元素
        do {
            smaller++;
        } while (sortArray[smaller] < pivot);
        
        // 从右向左找第一个小于等于pivot的元素
        do {
            bigger--;
        } while (sortArray[bigger] > pivot);
        
        // 外层while保证smaller < bigger，直接交换即可，无需if判断
        swap(sortArray, smaller, bigger);
    }

    return bigger;
}

逻辑说明 #

1. 把原本在while内的if判断，拆分成两个do-while循环：分别负责定位左半区第一个大于pivot的元素，和右半区第一个小于pivot的元素。
2. 外层的while(smaller < bigger)保证了两个指针还未交叉，所以每次进入循环都可以直接交换元素，不需要额外的分支判断。
3. 最终bigger会停在分区的分界点，直接返回即可用于后续的递归排序。

这个方案既保留了快速排序的O(n log n)平均时间复杂度，又完全移除了while循环内的if语句，代码逻辑也更清晰易读。你可以把这个分区函数替换到你的QuickSort实现中，就能达到简化算法的目标啦。

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