一文详解快速排序详细到极致

 快速排序的步骤：

1. 确定分割点（也可以说为对比点）
2. 调整范围，将小于对比点的数据放到对比点左侧，大于则放到右侧
3. 递归处理左右两端

从上面步骤来看来快速排序理解起来还是比较简单的，下面我们将举一个例子说明

【第一步】确定分割点，我们选取重点,我们定义左指针为l，右指针为r，那么x = l + （r - l）/ 2;

这样定义的好处可以防止越界。

也可以这样定义x = l + ((r - l)/>>1);>>的效率高于/，但是要注意运算符的先后顺序。

【第二步】进行指针移动使得的对比点x的左侧数据小于等于x，右侧数据大于等于x。

直到 l > = r 成立，则停止。此时我们可以观察到已经拍好顺序 

 【第三步】递归处理左右两端，此时需要注意边界问题

// 左递归
quickSort(arr,l,j);
// 右递归
quickSort(arr,j+1,r);

【处理右侧】

【第一步】此时l = 3；r = 4。其中 x = 3

 【第二步】调整范围

 【第三步】再次进行递归，此时我们发现很容易判断递归结束的条件，当l >= r时就结束，因此

l == r说明只有只有一个元素可以不用排序。

【处理左侧】

【第一步】此时l = 0，r = 2，x 参考点可以计算出为1

 【第二步】调整数据

 【第三步】递归

【提示】递归的三要素

• 参数列表
• 返回值
• 单层逻辑

只要把握好这三个方面递归是很好写出来的。

详细代码如下：

#1处代码：是递归结束条件，如果递归到底层只有一个元素时候肯定是有序的直接返回即可

 public static void quickSort(int[] arr, int l, int r) {
        if(l >= r) return; #1
        // 1、 找到参考点
        int x = arr[l + ((r - l)>>1)];
        
        // 1、定义指针
        int i = l - 1;
        int j = r + 1;
        // 2、保证x的左侧数据小于等于x ，右侧数据大于等于x
        while(i < j) {
            do i++; while(arr[i] < x);
            do j--; while(arr[j] > x);
            // 交换
            if(i < j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // 3、处理左边
        quickSort(arr,l,j);
        // 4、处理左边
        quickSort(arr,j + 1,r);
    }