java学习笔记-快速排序

思路：首先在数组中选取一个标杆 （一般是开始元素 末尾元素 中间元素）

每一次递归以第一个数为基准数，找到数组中所有比基准数小的，再找到所有比基准数大的。小的全部放在左边，大的全部放在右边，确定基准数的正确位置

1. 从右边开始找比标杆小的  
2. 从左边开始找比标杆大的
3. 将两个数字交换位置
4. 左右两边的指针继续找，直到两个箭头指向同一个索引为止
5. 标杆归位  将标杆数字与箭头所指向的数字进行交换，相当于找到标杆数字最后的位置，左边的数字全部比他小，右边的数字全部比他大，但是左右两边的数字不一定有序。

package com.ustc.test9;

public class quickSort1 {

    public static void main(String[] args) {

        int[] arr = {6,1,3,2,4,5,6,75,76,76412,1};
        quickSort11(arr,0,arr.length - 1);


        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i] + " ");
        }


    }

    private static void quickSort11(int[] arr, int left, int right) {

        //递归的停止条件
        if(left > right)
        {
            return;
        }

        int left0 = left;
        int right0 = right;
        int baseNUmber = arr[left0];  //选取最左边的数字作为基准数

        while(left != right)
        {
            //从右边开始找比基准数小的数字   并且 right > left
            while(arr[right] >= baseNUmber  && right > left)
            {
                right--;
            }

            //从左边开始找比基准数大的数字   并且 right > left
            while(arr[left] <= baseNUmber && right > left)
            {
                left++;
            }

            //交换两个数字位置
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }

        //基准数归位
        int temp = arr[left];
        arr[left] = arr[left0];
        arr[left0] = temp;

        //由于左右两边的数字还没有进行排序  所以递归进行
        //保存left0  right0 为了记录起始位置
        quickSort11(arr,left0,left - 1);
        quickSort11(arr,left + 1,right0);
    }
}