快速排序双指针分区终止条件为何用while(L<=R)？能否改为while(L<R)？

先明确本次实现的前提：

• 取基准点索引 pivot_idx = (low + high) // 2，分区前先将基准元素与数组末尾元素交换
• L指针从low开始，R指针从high - 1开始
• L指针递增，直到找到大于基准值的元素；R指针递减，直到找到小于等于基准值的元素

两种循环条件的差异 #

1. 使用while(l < r)的逻辑 #

当外层循环条件为l < r时，最后一轮迭代中，L会一直移动到与R相遇的位置。由于上一步已经完成了arr[l]和arr[r]的交换，此时R指向的元素必然大于基准值，因此将基准元素放到L的位置时，能保证左边元素都<=基准值，右边元素都>基准值，完成正确分区。

2. 使用while(l <= r)的实现与逻辑 #

以下是基于while(l <= r)实现的分区函数（函数签名：partition(int[] arr, int low, int high)）：

int pivotIdx = (low + high) / 2;
int pivotElem = arr[pivotIdx];

int r = high - 1;
int l = low;
// 交换基准元素与数组末尾元素
arr[pivotIdx] = arr[high];
arr[high] = pivotElem;

while (l <= r) {
    // 找到左侧第一个大于基准值的元素
    while (l <= r && arr[l] <= pivotElem) {
        l++;
    }
    // 找到右侧第一个小于等于基准值的元素
    while (l <= r && arr[r] > pivotElem) {
        r--;
    }
    // 仅当l < r时交换，避免相遇时无意义交换
    if (l < r) {
        int tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;
    }
}
// 将基准元素放到正确位置
arr[high] = arr[l];
arr[l] = pivotElem;

这种条件的优势在于：

• 外层循环用l <= r，能确保所有元素都被遍历检查，不会遗漏L和R相遇时的元素判断
• 内层循环的l <= r边界判断，能有效防止数组越界
• 最终L的位置就是基准元素的正确落点，此时左边所有元素都<=基准值，右边都>基准值

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