// 快速排序
function quickSort(arr){
quick(arr,0,arr.length-1)
}
function quick(arr,left,right){
if(left<right){
let index = partition(arr,left,right);
quick(arr,left,index-1);
quick(arr,index+1,right);
}
}
// 劃分操作
function partition(arr,left,right){
let i = left,j=right;
let p = arr[left]; // 取第一個數(shù)作為基準
while(i<j){
while(arr[j]>p){
j--;
}
if(i<j){
[arr[i],arr[j]]=[arr[j],arr[i]];
i++;
}
while(arr[i]<p){
i++;
}
if(i<j){
[arr[i],arr[j]]=[arr[j],arr[i]];
j--;
}
}
return i; // 返回基準(一開始選擇的最左邊的數(shù))的位置峻黍，基準左邊的所有數(shù)比它小血巍，右邊的所有數(shù)比它大
}
// 測試用
let array = []
for(let i=0;i<10000;i++){
array.push(Math.floor(Math.random()*10000))
}
console.time('快速排序耗時:');
quickSort(array)
console.timeEnd('快速排序耗時:');
console.log(array)
快速排序優(yōu)化
1. 優(yōu)化選取樞軸
三數(shù)取中法：即取三個關(guān)鍵字先進行排序，一般是取左端、右端和中間三個數(shù)犁柜，將中間數(shù)作為樞軸
2. 優(yōu)化不必要的交換
將樞紐保存為中間變量temp剖毯，將交換操作改為替換操作圾笨，最后才將最后位置的數(shù)改為temp的值
選自《大話數(shù)據(jù)結(jié)構(gòu)》
3. 優(yōu)化小數(shù)組時的排序方案
加一個判斷條件，如果數(shù)組長度非常小逊谋，使用直接插入排序(直接插入是簡單排序中性能最好的)
