快速排序的原理荡含，首先選取一個基點竖般，基點的位置隨意（一般選中間點或者開始位置為基點）甚垦。在這里我用js實現(xiàn)的是以數(shù)組的開始位置為起始點，然后規(guī)定兩個指針，一個位于數(shù)組的開始位置艰亮，一個位于數(shù)組的結束位置闭翩，先從后和基準值比較，比基準值大迄埃，則右指針減一男杈，反之，將右指針指向的值賦值給左指針调俘；開始從左和基準值比較，如果小于等于基準值旺垒，則左指針加一彩库，反之，將左指針指向的值賦值給右指針先蒋，直到兩個指針指向同一位置,則結束比較骇钦，此時會形成兩個區(qū)間，在基準值的左邊都是小于等于基準值的竞漾，在基準值的右邊都是大于基準值的眯搭，再分別對兩邊區(qū)間選取基準值，重復以上步驟业岁，直到區(qū)間只剩一個值結束排序鳞仙。
- 以數(shù)組的開始位置為起始點，用pivot表示笔时，用left表示數(shù)組的開始位置棍好，用right表示數(shù)組的結束位置；
- 先用right指針指向的值和pivot比較允耿，如果比pivot大借笙，則right減1;
- 當right指針指向的值小于等于pivot時，把right指針指向的值賦值給left指針较锡；
- 然后在用left指針指向的值和pivot比較业稼，如果小于等于pivot，則left加1蚂蕴；
- 當left指針指向的值大于pivot時低散，把left指針指向的值賦值給right指針;
- 直到left指針和right指針相遇，則把pivot值放在他們相遇位置掂墓；
- 然后把poivot左邊的數(shù)組和右邊的數(shù)組重復以上步驟谦纱；
- 直到區(qū)間只有一個值結束所有操作。
下面是我根據(jù)自己的理解君编，寫的算法實現(xiàn)跨嘉，如有更好的可以一起分享哈～
var quicksort=function(arr){
let len=arr.length;
if(len<=1){return arr;}
var mid = arr[0];//基準值
var i=0,j=len-1;
let flag=true; // true表示從右開始和基準值比較，false表示從左開始和基準值比較
while(i!=j){
if(flag){
if(arr[j]>mid){
j--;
}else{
arr[i]=arr[j];
i++;
flag=false
}
}else{
if(arr[i]<=mid){
i++;
}else{
arr[j]=arr[i];
j--;
flag=true
}
}
}
return quicksort(arr.slice(0,i)).concat([mid],quicksort(arr.slice(i+1)));
}
