快速排序使用分治法（Divide and conquer）策略來把一個(gè)序列分為兩個(gè)子序列。

步驟為：

1. 從數(shù)列中挑出一個(gè)元素，稱為"基準(zhǔn)"（pivot），
2. 重新排序數(shù)列，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（相同的數(shù)可以到任何一邊）。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作。
3. 遞歸地（recursively）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

遞歸到最底部時(shí)，數(shù)列的大小是零或一，也就是已經(jīng)排序好了。這個(gè)算法一定會(huì)結(jié)束，因?yàn)樵诿看蔚牡╥teration）中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。

參考維基百科

let quickSort=function(list) {
  if(list.length<=1){
    return list;
  }else{
    let middle=list[0];
    let leftList=[];
    let rightList=[];
    //存放重復(fù)元素
    let middleList=[];
    list.forEach(node=>{
      if(node<middle){
        leftList.push(node);
      }else if(node>middle){
        rightList.push(node);
      }else{
        middleList.push(node);
      }
    });
    //遞歸調(diào)用，注意concat方法每次會(huì)返回新的子串，需要開辟額外的內(nèi)存空間
    return [].concat(quickSort(leftList),middleList,quickSort(rightList));
  }
};

let randomList=function (size) {
  let list=[];
  for(let i=0;i<size;i++){
    list.push(Math.floor(Math.random()*100));
  }
  return list;
};

let sortList=quickSort(randomList(10));
console.log(sortList);

上述實(shí)現(xiàn)平均時(shí)間復(fù)雜度為O(nlog n)，最壞的情況是排列一個(gè)已經(jīng)有序的數(shù)組，時(shí)間復(fù)雜度會(huì)降級(jí)為n*n

快速排序是Array.prototype.sort()的默認(rèn)實(shí)現(xiàn)，實(shí)際編碼中直接調(diào)用即可。