import java.util.Arrays;


public class BinarySearch01 {

     /*
      * 【第一次分割结果为使mid的左边<mid，右边>mid】
      *
      * 选首字段array[0]为目标中间字段mid，首字段array[0]=array[left]为空位
      *
      * 用mid先从右边最高位right比较，如果a[right]>mid,则right-1,继续，直到a[right-n]<mid时，将a[right-n]移到左空位
      * 此时a[right-n]为空位，此后，用mid从左边最低位left比较，找到a[left+n]>mid时,将其移到空位
      *
      *
      * 例一：


    4 3 5 9 2 6

      3 5 9 2 6   4
    2 3 5 9   6   4
    2 3   9 5  6  4
    2 3 4 9 5  6  


    4 5 1 9 2 6

      5 1 9 2 6   4
    2 5 1 9   6   4
    2   1 9 5 6   4
    2 1   9 5 6   4
    2 1 4 9 5 6 



         
         
          例二：
         
          [4, 5, 1, 0, 2, 3]
          [3, 2, 1, 0, 4, 5]
         
         
      */
     public static void main(String[] args) {

          int[] a={4,5,1,0,2,3};
          System.out.println(Arrays.toString(a));
          getStr(a,0,a.length-1);
          System.out.println(Arrays.toString(a));
         
     }

     /*
      *
      */
     static void getStr(int[] a, int left, int right) {
          if(left >= right) return;
          int iLeft = left;
          int iRihgt = right;
          int mid = a[left];
          while (left < right) {
               /*
                * 高位从右向左移
                */
               while (left < right && mid < a[right]) {
                    right--;
               }
               ;
               a[left] = a[right];
               /*
                * 低位从左向右移
                */
               while (left < right && mid > a[left]) {
                    left++;
               }
               ;
               a[right] = a[left];
          }
          ;
          a[left] = mid;
          System.out.println(iLeft+":"+left+":"+iRihgt);
          System.out.println(Arrays.toString(a));
          getStr(a, iLeft, left - 1);
          getStr(a, left + 1, iRihgt);
     }

}

1、快速排序的基本思想：

快速排序使用分治的思想，通过一趟排序将待排序列分割成两部分，其中一部分记录的关键字均比另一部分记录的关键字小。之后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

2、快速排序的三个步骤：

(1)选择基准：在待排序列中，按照某种方式挑出一个元素，作为 "基准"（pivot）
(2)分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比该基准小，在基准右边的元素都比基准大
(3)递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。

3、选择基准的方式

方法(1)：固定位置
思想：取序列的第一个或最后一个元素作为基准

方法(2)：随机选取基准
引入的原因：在待排序列是部分有序时，固定选取枢轴使快排效率底下，要缓解这种情况，就引入了随机选取枢轴

方法(3)：三数取中（median-of-three）
引入的原因：虽然随机选取枢轴时，减少出现不好分割的几率，但是还是最坏情况下还是O(n^2），要缓解这种情况，就引入了三数取中选取枢轴

三数取中法：
当不幸的选择出最大或最小元素作为枢纽元素，那么递归深度将变成n，则时间复杂度变成了O(n2)，会退化为冒泡；所以
每趟快排前，先将数组开始位置，中间位置，以及结尾位置的三个元素进行比较，选择其中的中间大的数做为枢纽元素。