快速排序

算法思想：

1.分治法：比大小，再分区

2.从数组中取出一个数，作为基准数。

分区：将比这个数大或等于的数全放到他的右边，小于他的数

全放到他的左边。

3.再对左右区间重复第二步，直到各区间只有一个数。

实现思路

1.挖坑填数

2.将基准数挖出形成第一个坑。

3.由后向前找比他小的数，找到后挖出此数填到前一个坑中。

由前向后找比他大或等于的数，找到后也挖出此数填到前一个坑中。

4.再重复执行2，3两步骤。

public class QuickSort {
    //start 默认是0
    //end 是数组长度-1
    public void quickSort(int[] arr, int start, int end) {
        if (start < end) {
            //获取分区索引
            int index = getIndex(arr, start, end);
            //对左右两个分区 再进行同样的步骤 ，即是递归调用
            quickSort(arr, start, index - 1);//左半部分
            quickSort(arr, index + 1, end);//右半部分
        }
    }

    private int getIndex(int[] arr, int start, int end) {
        int i = start;
        int j = end;
        //定义基准数
        int x = arr[i];
        //循环
        while (i < j) {
            //从右往左比较
            while (i < j && arr[j] >= x) {
                j--;
            }
            //从右往左找到比基准数小的数了后，填坑
            if (i < j) {
                //把这个数填到上一个坑位
                arr[i] = arr[j];
                //让 i++;
                i++;

            }

            //从左往右找
            while (i < j && arr[i] < x) {
                i++;
            }
            // 找比基准数大的数，找到后填坑
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
        }
        //当上面的循环结束后把基准数填到最后一个坑位，也就一基准数为界，分成了左右两部分
        arr[i] = x; //把基准数填进去
        return i; //返回基准数所在位置的索引
    }

}