快速排序——JS篇

快速排序使用分治法（Divide and conquer）策略来把一个序列分为两个子序列。

步骤为：

1. 从数列中挑出一个元素，称为"基准"（pivot），
2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

参考维基百科

let quickSort=function(list) {
  if(list.length<=1){
    return list;
  }else{
    let middle=list[0];
    let leftList=[];
    let rightList=[];
    //存放重复元素
    let middleList=[];
    list.forEach(node=>{
      if(node<middle){
        leftList.push(node);
      }else if(node>middle){
        rightList.push(node);
      }else{
        middleList.push(node);
      }
    });
    //递归调用，注意concat方法每次会返回新的子串，需要开辟额外的内存空间
    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);

上述实现平均时间复杂度为O(nlog n)，最坏的情况是排列一个已经有序的数组，时间复杂度会降级为n*n

快速排序是Array.prototype.sort()的默认实现，实际编码中直接调用即可。