八大排序——快速排序

效率：快速排序的效率要比冒泡排序高2倍多；

原理：为每个基准数据，即每次拿出来用作比较值的数据，找到他排好序之后应该在的索引位置；

本人理解：

1. 每次任取一个数值作为基准数据（一般取尚未好序的数值中的第一个）
2. 定义两个索引 left 和 right 分别表示“首索引” 和 “尾索引”，key 表示“基准值”；
3. 然后从“尾索引”往“首索引”方向扫描，直到找到第一个比基准数据小的数据，然后将他索引更换成“首索引”；
4. 然后再从“首索引”往“尾索引”方向扫描，直到找到第一个比基准数据大的数据，然后将他索引更换成“尾索引”；
5. 如果在扫描判断时发现“尾索引”等于“首索引”，则代表这一次排序结束，所以将基准数据替换给“首索引”对应的值；
6. 然后进行下一次分区，不过这时分成了两个区，之前基准数据左边的数据[0, left-1],和基准数据右边的数据[right+1, array.length-1];
   (此时left == right)
7. 然后每一个分区都重复步骤2~6，直到所有分区中的记录都有序。

通俗点，就是每次排序都让基准值的左边数比他小，右边的数比他大；

    public static void main(String[] args) {
    	int[] arr = {33, 52, 16, 90, 23, 85}
    	quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int[] arr, int leftIndex, int rightIndex) {
        if (leftIndex >= rightIndex) {
            return;
        }

        int left = leftIndex;
        int right = rightIndex;
        // 设置基准值，待排序的左侧第一个元素作为基准值
        int key = arr[left];

        // 从左右两边交替扫描，直到left = right
        while (left < right) {
            // 从右往左扫描，找到第一个比基准值小的元素，
            while (left < right && arr[right] >= key) {
                right--;
            }
            // 找到这种元素将arr[right]放入arr[left]中
            arr[left] = arr[right];

            while (left < right && arr[left] <= key) {
                // 从左往右扫描，找到第一个比基准值大的元素
                left++;
            }
            // 找到这种元素将arr[left]放入arr[right]中
            arr[right] = arr[left];
        }
        // 基准值归位
        arr[left] = key;
        // 对基准值左边的元素进行递归排序；leftIndex代表左区开始的索引，而此时的left为基准值的索引，所以left-1为左区结束的索引
        quickSort(arr, leftIndex, left - 1);
        // 对基准值右边的元素进行递归排序；此时right等于left，所以right此时也是基准值的索引,所以right+1为右区的开始索引，rightIndex为右区的结束索引
        quickSort(arr, right + 1, rightIndex);
    }