Java快速排序

记录一下自己学习快速排序的过程，以及遇到的问题

快速排序思想：找到一个基准值(常从最左侧头开始)，遍历所有数据，将比基准值小的，都放到基准值左侧，比基准值大的放到基准值右侧，第一次循环完成，然后递归调用该方法即可。

通过下面的例子，说明一下快速排序的过程，现在有一个原数据12 3 11 21 34 6 22进行快速排序：

步骤一：

首先取出一个基准（pivot）一般为第0位上的元素也就是：12
取出后，此时的0位变为一个空位。

注：下图的 i ：从左向右查找 j：从右向左查找

步骤1.png

步骤二：

此时 i 为空位，需要找 j 要一个数据来填满，j 需要从右向左找一个比12小的数据，也就是下面的6。

步骤二.png 交换之后的位置.png

步骤三：

步骤三.png

步骤四：

步骤四.png

注：当 i j 相遇的时候，就停止。此时左侧都是比基准 12 小的，右侧都是比基准12 大的，然后递归继续进行排序!

Java 代码实现

public class QuickSort {


    public static void quickSort(int[] arr, int start, int end) {
        if (start>end) return ;

        int left = start;
        int right = end;
        int pivot = arr[start];//基准

        while (left < right) {
            //从右向左，找到比基准小的数据
            while (left < right && arr[right] >= pivot) {
                right--;
            }

            //从左向右找到比基准大的数据
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            
            //位置交换
            int tem = arr[left];
            arr[left] = arr[right];
            arr[right] = tem;
        }

        //将left 和 right 相遇的位置，和基准值进行交换
        arr[start] = arr[left];
        arr[left] = pivot;

        //此时不需要再讲基准位置写进去
        quickSort2(arr, start, left - 1);

        quickSort2(arr, right + 1, end);
    }

    //主方法
    public static void main(String[] args) {
        int[] arr= {12, 3, 11, 21, 34, 6, 22};
        // 调用快速排序方法
        quickSort(arr, 0, arr.length - 1);

         System.out.println(Arrays.toString(arr));
    }
}

输出结果：

排序结果.png

为什么快速排序必须要从右侧开始？

回头来复习快速排序的时候，本人习惯性的从左侧开始，发现运行结果不对发现了这个坑，原因如下：

• 快速排序思想是，找到基准，左侧值都比基准小，右侧值都比基准大
• 如果你先从左侧开始，从左侧开始查找比 基准小的值，此时遇到比基准大的值会继续往右查找，会影响从右向左找比基准小的值的过程 违背了快速排序的思想