原理

    1. 根据基准值，找出小于基准值和大于基准值的两个数组，然后排序，采用分而治之的思想
    1.   private static void quickSort(int[] arr,int left, int right){
    2.     if(left>=right){
    3.       return;
    4.     }
    5.     //以第一个元素为初始基准值
    6.     int low = left;
    7.     int high = right;
    8.     int basic = arr[low];
    9.     System.out.println("basic="+basic);
    10.     System.out.println("origin arr="+Arrays.toString(arr));
    11.     while (low<high){
    12.       //从右边开始移动，直到找到第一小于基准值的数，然后和low进行交换，并开始从左边开始
    13.       for (;;high--){
    14.         if(high<=low){
    15.           break;
    16.         }
    17.         if(basic>arr[high]){
    18.           arr[low] = arr[high];
    19.           System.out.println("swap high="+high+", arr="+Arrays.toString(arr));
    21.           break;
    22.         }
    23.       }
    24.       //从左边开始移动，直到找到第一大于基准值的数，然后和high进行交换，并开始从右边开始
    25.       for (;;low++){
    26.         if(low>=high){
    27.           break;
    28.         }
    29.         if(basic<arr[low]){
    30.           arr[high] = arr[low];
    31.           System.out.println("swap low="+low+", arr="+Arrays.toString(arr));
    32.           break;
    33.         }
    34.     }
    36. }
    37.     //直到low和high碰撞时，这里就是基准值应该在的位置
    38.     if(arr[low] == arr[high]){
    39.       arr[low]  = basic;
    40.       System.out.println("一次分区完成，low="+low+", high="+high +", arr="+Arrays.toString(arr));
    41.     }
    42.     //分而治之
    43.     quickSort(arr,left,low-1);
    44.     quickSort(arr,low+1,right);
    46.   }
    48. public static void main(String[] args) {
    49.     int[] arr = {6,2,4,9,4,3,6,1};
    50.     quickSort(arr, 0, arr.length-1);
    51.   }