Java lomuto分区方案实现快速排序（递归）

快速排序描述

• 1，每一轮排序选择一个基准点（pivot）进行分区。
  – 1.1让小于基准点的元素进入一个分区，大于基准点的元素进入另一个分区。
  – 1.2 当分区完成时，基准点元素的位置就是其最终位置。
• 2，在子分区内重复以上过程，直至子分区元素个数少于等于1，这体现的是分而治之的思想。

单边循环快排（lomuto分区方案）

• 1，选择最右元素作为基准点。
• 2，i指针维护小于基准点元素的边界，也是每次交换的目标索引。
• 3，j指针负责找到比基准点小的元素，一旦找到则与i进行交换。
• 4，最后基准点与i交换，i即为分区位置。

代码实现

public static void main(String[] args) {
        int[] a = {1, 3, 2, 5, 4, 6, 8, 9};
        quick(a,0, a.length-1);
        System.out.println(Arrays.toString(a));
    }

    /**
     *
     * @param a 数组
     * @param l 左边边界
     * @param h 右边边界
     */
    public static void quick(int[] a, int l, int h){
        if(l >= h){
            return ;
        }
        int p = partition(a, l, h);
        quick(a, l, p-1);//左边分区的范围确定
        quick(a, p + 1, h);//右边分区的范围确定
    }

    /**
     *
     * @param a 数组
     * @param l 左边边界
     * @param h 右边边界
     * @return 基准点排序后坐标
     */
    private static int partition(int[] a, int l, int h){
        int pv = a[h]; // 基准点元素
        int i = l; // 小于基准点元素的边界
        for(int j = l; j< h; j++){
            if(a[j] < pv){
                swap(a, i, j);
                i++;
            }
        }
        swap(a, h, i);
        return i;//返回值代表了基准点元素所在的正确索引，用它确定下一轮分区的边界。
    }