<快速排序算法>
簡(jiǎn)單介紹:
給定一個(gè)無序數(shù)組揪利，從中選出一個(gè)數(shù)作為哨兵位 (pivot)
Step1: 從最后一位 (high) 開始遍歷數(shù)組态兴，若小于pivot，則繼續(xù)往前疟位，發(fā)現(xiàn)大于哨兵位的數(shù) (j) 則停止瞻润。
Step2: 從數(shù)組的最前 (low) 往后遍歷，若小于pivot則繼續(xù)甜刻，若大于哨兵位的數(shù)則停止 (i) , high敢订、low、 i罢吃、j均為數(shù)組下標(biāo)楚午。
Step3: 交換i、j位置上的數(shù)尿招，直到 low=high矾柜。
Step4: 遞歸。
※ 快速排序的核心思想是通過哨兵位就谜，從而將數(shù)組一次一次分為兩部分怪蔑，即左邊<哨兵位；右邊>哨兵位丧荐，從而遞歸實(shí)現(xiàn)最終的排序結(jié)果
圖片來源及詳細(xì)說明https://www.cnblogs.com/redbear/p/8891730.html
function QuickSort(arr) {
? ? let low =0;
? ? let high = arr.length-1;
//設(shè)定樞軸 (pivot) , 即哨兵位 缆瓣。這里使用第一個(gè)元素作為哨兵
let pivot = arr[0];
? ? if(arr.length<2){
return arr;
? ? }
while(low<high){
while (arr[high] >= pivot && high > low){
high--;
? ? ? ? }
while (arr[low] <= pivot && high > low){
low++;
? ? ? ? }
if(low==high){
let mid = arr[high];
? ? ? ? ? ? arr[high] = arr[0];
? ? ? ? ? ? arr[0] = mid;
? ? ? ? ? ? break;
? ? ? ? }else{
? ? ? ? let tem = arr[high];
? ? ? ? arr[high] = arr[low];
? ? ? ? arr[low] = tem;
? ? ? ? }
}
//Note: slice()函數(shù)的兩個(gè)參數(shù)start和end，end數(shù)組下標(biāo)-1!
? ? let res =QuickSort(arr.slice(0,low)).concat(arr[low]).concat(QuickSort(arr.slice(low+1)));
??? return res;
}
