[聚合文章] 快速排序——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()的默认实现，实际编码中直接调用即可。

注：本文内容来自互联网，旨在为开发者提供分享、交流的平台。如有涉及文章版权等事宜，请你联系站长进行处理。