// 快速排序
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]; // 取第一個數作為基準
  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; // 返回基準(一開始選擇的最左邊的數)的位置，基準左邊的所有數比它小，右邊的所有數比它大
}
// 測試用
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)化選取樞軸

三數取中法：即取三個關鍵字先進行排序，一般是取左端、右端和中間三個數，將中間數作為樞軸

2. 優(yōu)化不必要的交換

將樞紐保存為中間變量temp，將交換操作改為替換操作，最后才將最后位置的數改為temp的值

選自《大話數據結構》

3. 優(yōu)化小數組時的排序方案

加一個判斷條件，如果數組長度非常小，使用直接插入排序(直接插入是簡單排序中性能最好的)