快速排序

应用场景
快速排序 主要是数据量大并且是线性结构
短处
有大量重复数据的时候，性能不好
单向链式结构处理性能不好（一般来说，链式都不使用）
思路int[] arr={31,68,45,90,23,39,54,12,87.76}
其实思想是蛮简单的，就是通过第一遍的遍历（让low和high指针重合）来找到数组的切割点。
假设有
1、第一步：首先我们从数组的left位置取出该数（31）作为基准（base）参照物。

image.png

2、第二步：从数组的high位置向前找，一直找到比（base）小的数，
如果找到，将此数赋给low位置（也就是将12赋给31），
此时数组为：12,68,45,90,23,39,54,12,87.76
low和high指针分别为前后的12。

image.png
3、第三步 此时low角标要向前移动一位 移动到68位置上,high不变
image.png
4、第四步 从数组的low位置向后找，一直找到比（base）大的数，
如果找到，将此数赋给right的位置（也就是40赋给10），
此时数组为：12、68、45、90、23、39、54、68、87、76
low和hiigh指针分别为前后的68。
image.png

5、第五步 ：重复“第二,第三 第四“步骤，直到low和high指针重合，
最后low和high角标在45位置上重合
此时的数组为：12、23、45、90、45、39、54、68、87、76

image.png

6、基准（base）参照物值赋值给low和high重合的位置上

image.png

7、第七步、此时31已经潜入到数组的内部，20的左侧一组数都比31小，31的右侧作为一组数都比31大，
以31为切入点对左右两边数按照"第一，第二，第三，第四，第五，第六"步骤进行。就可以把整个数据给排序完成。

代码如下

    //快速排序     31  21  59  68  12  40
        //    x=31
        public static void quickSort(int[] array,int begin,int end){
            if(end-begin<=0) return;
            int x=array[begin];
            int low=begin;//0
            int high=end;//5
            //由于会从两头取数据，需要一个方向
            boolean direction=true;
            L1:
            while(low<high){
                if(direction){//从右往左找
                    for(int i=high;i>low;i--){
                        if(array[i]<=x){
                            array[low++]=array[i];
                            high=i;
                            direction=!direction;
                            continue L1;
                        }
                    }
                    high=low;//如果上面的if从未进入，让两个指针重合
                }else{
                    for(int i=low;i<high;i++){
                        if(array[i]>=x){
                            array[high--]=array[i];
                            low=i;
                            direction=!direction;
                            continue L1;
                        }
                    }
                    low=high;
                }
            }
            //把最后找到的值 放入中间位置
            array[low]=x;
            //开始完成左右两边的操作
            quickSort(array,begin,low-1);
            quickSort(array,low+1,end);
        }