應(yīng)用場景
快速排序 主要是數(shù)據(jù)量大并且是線性結(jié)構(gòu)
短處
有大量重復數(shù)據(jù)的時候，性能不好
單向鏈式結(jié)構(gòu)處理性能不好（一般來說，鏈式都不使用）
思路int[] arr={31,68,45,90,23,39,54,12,87.76}
其實思想是蠻簡單的，就是通過第一遍的遍歷（讓low和high指針重合）來找到數(shù)組的切割點。
假設(shè)有
1、第一步：首先我們從數(shù)組的left位置取出該數(shù)（31）作為基準（base）參照物。
image.png
2、第二步：從數(shù)組的high位置向前找，一直找到比（base）小的數(shù)，
如果找到，將此數(shù)賦給low位置（也就是將12賦給31），
此時數(shù)組為：12,68,45,90,23,39,54,12,87.76
low和high指針分別為前后的12。
image.png
3、第三步 此時low角標要向前移動一位 移動到68位置上,high不變
image.png
4、第四步 從數(shù)組的low位置向后找，一直找到比（base）大的數(shù)，
如果找到，將此數(shù)賦給right的位置（也就是40賦給10），
此時數(shù)組為：12、68、45、90、23、39、54、68、87、76
low和hiigh指針分別為前后的68。
image.png
5、第五步 ：重復“第二,第三 第四“步驟，直到low和high指針重合，
最后low和high角標在45位置上重合
此時的數(shù)組為：12、23、45、90、45、39、54、68、87、76
image.png
6、基準（base）參照物值賦值給low和high重合的位置上
image.png
7、第七步、此時31已經(jīng)潛入到數(shù)組的內(nèi)部，20的左側(cè)一組數(shù)都比31小，31的右側(cè)作為一組數(shù)都比31大，
以31為切入點對左右兩邊數(shù)按照"第一，第二，第三，第四，第五，第六"步驟進行。就可以把整個數(shù)據(jù)給排序完成。
代碼如下
//快速排序 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
//由于會從兩頭取數(shù)據(jù)，需要一個方向
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);
}
