请求实现YouTube视频中的特殊快速排序算法（Java）

你提到的视频里的快速排序采用的是直观的左右指针交换式划分，和你现有的Lomuto划分标准快排不同，它的划分过程会产生更多交换操作，因此效率更低。以下是对应实现：

完整代码 #

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

static int partition(int[] arr, int low, int high) {
    // 选取子数组首个元素作为枢轴（视频中采用的选择方式）
    int pivot = arr[low];
    int left = low;
    int right = high;

    while (left < right) {
        // 左指针右移，找到第一个大于枢轴的元素
        while (left <= high && arr[left] <= pivot) {
            left++;
        }
        // 右指针左移，找到第一个小于枢轴的元素
        while (right >= low && arr[right] > pivot) {
            right--;
        }
        // 交换两个元素，直到指针相遇
        if (left < right) {
            swap(arr, left, right);
        }
    }
    // 将枢轴放到正确位置
    swap(arr, low, right);
    return right;
}

static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivotPos = partition(arr, low, high);
        // 递归处理枢轴左右的子数组
        quickSort(arr, low, pivotPos - 1);
        quickSort(arr, pivotPos + 1, high);
    }
}

速度较慢的原因 #

• 交换操作频繁：标准Lomuto划分一次遍历仅完成必要的元素归位，而这个版本在左右指针移动过程中会多次交换元素
• 枢轴选择无优化：固定选首个元素当枢轴，若数组已有序，递归深度会达到O(n)，时间复杂度退化为O(n²)
• 重复元素处理低效：没有将等于枢轴的元素批量归位，导致重复元素分散在左右子数组，增加后续递归的比较开销

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