快速排序（JavaScript）

// 快速排序
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)

快速排序优化

1. 优化选取枢轴

三数取中法：即取三个关键字先进行排序，一般是取左端、右端和中间三个数，将中间数作为枢轴

2. 优化不必要的交换

将枢纽保存为中间变量temp，将交换操作改为替换操作，最后才将最后位置的数改为temp的值

选自《大话数据结构》

3. 优化小数组时的排序方案

加一个判断条件，如果数组长度非常小，使用直接插入排序(直接插入是简单排序中性能最好的)