JS算法之快速排序法

  • 更新时间:5年零206天前
  • 浏览量:1197
  • 发布人:思过崖

“快速排序”的思想:

(1)在数据集之中,选择一个元素作为”基准”(pivot)。
(2)所有小于”基准”的元素,都移到”基准”的左边;所有大于”基准”的元素,都移到”基准”的右边。
(3)对”基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

问题:

给定一个数据集{85, 24, 63, 45, 17, 31, 96, 50},通过快速排序算法实现对数组从小到大的排序

  1. function quickSort(arr){
  2. //获取数组长度,如果数组元素为1,直接返回;
  3. var length=arr.length;
  4. if(arr.length<=1){
  5. return arr;
  6. }
  7. var midIndex=parseInt((arr.length)/2);
  8. //不能将arr.splice(midIndex,1)[0]写成是arr[midIndex];
  9. //向splice函数传递两个参数具有删除的作用,会不断减少数组元素的个数
  10. //arr[midIndex]会导致算法陷入死循环
  11. var midValue=arr.splice(midIndex, 1)[0];
  12. var leftArray=[];
  13. var rightArray=[];
  14. for(var i=0;i<arr.length;i++){
  15. if(arr[i]<midValue){
  16. leftArray.push(arr[i]);
  17. }else{
  18. rightArray.push(arr[i]);
  19. }
  20. }
  21. //concat的时候加上midValue也是将上述注释中删除的进行补上
  22. return quickSort(leftArray).concat(midValue,quickSort(rightArray));
  23. }
  24. var arr=[85, 24, 63, 45, 17, 31, 96, 50];
  25. console.log(quickSort(arr));//[17, 24, 31, 45, 50, 63, 85, 96]