快速排序分区方法中空体嵌套while循环的Big O时间复杂度疑问

我遇到了这样一个快速排序的分区实现，它采用嵌套循环结构，但内层循环为空体，特此咨询该实现的时间复杂度（Big O）是多少？

实现代码如下：

public static int partition(int[] arr, int start, int end) {
    int pivot = arr[start];
    int i = start;
    int j = end;
    while (i < j) {
        while (i < j && arr[--j] >= pivot) ;
        if (i < j) {
            arr[i] = arr[j];
        }
        while (i < j && arr[++i] <= pivot) ;
        if (i < j) {
            arr[j] = arr[i];
        }
    }
    arr[j] = pivot;
    return j;
}

回答 #

这个分区方法的时间复杂度是O(n)，其中n是当前分区内的元素总数（即end - start + 1），具体分析如下：

• 首先看两个空体的内层循环：第一个内层循环从j的位置向左移动指针，直到找到小于基准值pivot的元素，或者i >= j时停止；第二个内层循环则从i的位置向右移动指针，直到找到大于pivot的元素，或者i >= j时停止。
• 核心关键点是：每个元素最多会被遍历一次。j从右往左扫过的元素不会被重复扫描，i从左往右扫过的元素也不会回头处理。整个过程中，i和j的移动范围加起来覆盖了分区内的所有元素，没有重复遍历的情况。
• 外层的while循环会在i和j相遇时终止，每次外层循环迭代都会缩小i和j之间的距离，不会出现无限循环。
• 剩下的赋值操作都是O(1)的常数时间操作，不会对整体时间复杂度产生影响。

另外补充说明：这个实现本质上和经典的Hoare分区算法是完全一致的，只是把内层循环的执行体写成了空语句（依赖循环条件里的--j和++i来完成指针移动），核心逻辑没有变化，所以时间复杂度和经典Hoare分区算法保持一致，都是线性的O(n)。

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