深入理解与修正：Java递归实现快速排序的常见陷阱与最佳实践

public class QuickSort {

    public static void quickSort(int[] s) {
        if (s == null || s.length < 2) { // 处理空数组或单元素数组的边界情况
            return;
        }
        quickSortSub(s, 0, s.length - 1);
    }
    // ... 其他方法
}

    private static void quickSortSub(int[] s, int a, int b) {
        // 递归基准条件：当子数组至少包含两个元素时才进行分区和递归
        // b - a >= 1 表示子数组长度至少为2 (b - a + 1 >= 2)
        if (b - a >= 1) { 
            int point = partition(s, a, b); // 执行分区操作，获取枢轴的最终位置

            // 递归排序左子数组
            // 只有当左子数组至少包含两个元素时才递归，避免对单元素或空数组进行不必要的递归调用
            if (point > a) { // point > a 意味着左子数组至少有一个元素
                quickSortSub(s, a, point - 1);
            }

            // 递归排序右子数组
            // 只有当右子数组至少包含两个元素时才递归
            if (point < b) { // point < b 意味着右子数组至少有一个元素
                quickSortSub(s, point + 1, b);
            }
        }
    }

    private static int partition(int[] s, int a, int b) {
        int pivot = s[b]; // 选择最右边的元素作为枢轴
        int left = a;      // 左指针，从子数组起始位置开始
        int right = b - 1; // 右指针，从枢轴左边一个位置开始

        while (left <= right) { // 循环直到左右指针相遇或交叉
            // 移动左指针，直到找到一个大于或等于枢轴的元素
            while (left <= right && s[left] < pivot) {
                left++;
            }
            // 移动右指针，直到找到一个小于或等于枢轴的元素
            while (left <= right && s[right] > pivot) {
                right--;
            }

            // 如果左右指针尚未相遇或交叉，则交换它们指向的元素
            if (left <= right) {
                int tmp = s[left];
                s[left] = s[right];
                s[right] = tmp;
                // 交换后，指针继续向内移动
                left++;
                right--;
            }
        }

        // 循环结束后，left 指针指向第一个大于或等于枢轴的元素的位置
        // 将枢轴放到其最终位置
        int tmp = s[left];
        s[left] = s[b]; // 将枢轴（s[b]）与 s[left] 交换
        s[b] = tmp;

        return left; // 返回枢轴的最终位置
    }

public class QuickSort {

    public static void quickSort(int[] s) {
        if (s == null || s.length < 2) {
            return;
        }
        quickSortSub(s, 0, s.length - 1);
    }

    private static void quickSortSub(int[] s, int a, int b) {
        if (b - a >= 1) { // 确保子数组至少包含两个元素
            int point = partition(s, a, b); // 执行分区操作

            // 递归排序左子数组
            if (point > a) { // 确保左子数组不为空
                quickSortSub(s, a, point - 1);
            }
            // 递归排序右子数组
            if (point < b) { // 确保右子数组不为空
                quickSortSub(s, point + 1, b);
            }
        }
    }

    private static int partition(int[] s, int a, int b) {
        int pivot = s[b]; // 选择最右边的元素作为枢轴
        int left = a;      // 左指针
        int right = b - 1; // 右指针

        while (left <= right) { // 循环直到左右指针相遇或交叉
            // 移动左指针
            while (left <= right && s[left] < pivot) {
                left++;
            }
            // 移动右指针
            while (left <= right && s[right] > pivot) {
                right--;
            }

            // 如果指针未交叉，则交换元素
            if (left <= right) {
                int tmp = s[left];
                s[left] = s[right];
                s[right] = tmp;
                left++;
                right--;
            }
        }

        // 将枢轴归位
        int tmp = s[left];
        s[left] = s[b];
        s[b] = tmp;

        return left; // 返回枢轴的最终位置
    }

    public static void main(String[] args) {
        int[] arr = {85, 10, 24, 63, 45, 27, 100, 31, 96, 50, 40, 23, 49, 96, 120, 105, 13, 5, 42, 69, 22, 12};
        System.out.println("原始数组:");
        for (int i : arr) System.out.print(i + ", ");
        System.out.println("\n");

        quickSort(arr);

        System.out.println("排序后数组:");
        for (int i : arr) System.out.print(i + ", ");
        System.out.println("");
    }
}

原始数组:
85, 10, 24, 63, 45, 27, 100, 31, 96, 50, 40, 23, 49, 96, 120, 105, 13, 5, 42, 69, 22, 12, 

排序后数组:
5, 10, 12, 13, 22, 23, 24, 27, 31, 40, 42, 45, 49, 50, 63, 69, 85, 96, 96, 100, 105, 120,