JavaScript 实现快速排序算法详解

function quickSort(arr){
    //如果数组只有一个数，就直接返回；
    if(arr.length<1){
      return arr;  
    } 
    //找到中间的那个数的索引值；如果是浮点数，就向下取整
    var centerIndex = Math.floor(arr.length/2);
    //根据这个中间的数的索引值，找到这个数的值；
    var centerNum = arr.splice(centerIndex,1);
    //存放左边的数
    var arrLeft = [];
    //存放右边的数
    var arrRight = [];
    for(i=0;i<arr.length;i++){
      if(arr[i]<centerNum){
        arrLeft.push(arr[i])
      }else if(arr[i]>centerNum){
        arrRight.push(arr[i])
      }
    }
    return quickSort(arrLeft).concat(centerNum,quickSort(arrRight));    
  };
  var arrSort = [33,18,2,40,16,63,27];
  var arr1 = quickSort(arrSort);
  console.log(arr1);

快速排序原理概述

本内容源自“妙味课堂”的一期视频教学。

快速排序的核心原理包含三个关键步骤：确定基准点、创建两个数组分别存储元素，以及进行递归处理。

基准点的选取是指从数组中找出位于中间位置的一个数值。

建立两个数组用于存储数据：以选定的基准点为界，将小于基准点的数值存入左侧新数组，大于基准点的数值存入右侧新数组。

递归是指在函数定义内部调用函数自身的过程。

递归实现注意事项

在使用递归实现排序时，需要注意以下几点：

第一，必须设置判断条件并返回一个值，否则会导致死循环。

第二，在内部调用自身函数时，传入的参数应为内部定义的某个变量，且该变量与初次传入的参数存在关联。

第三，当需要执行相同的工作逻辑时，可以考虑采用递归方式。

排序过程示例解析

以第一次执行函数为例，中间数为 40。根据循环中的判断条件，小于 40 的数值被存入 arrLeft，大于 40 的数值被存入 arrRight，具体过程如下图所示。

接下来进行第二次函数调用。

当代码执行到 return quickSort(arrLeft).concat(centerNum,quickSort(arrRight)); 这一行时，

quickSort(arrLeft) 会再次调用函数，此时传入的参数为 [33,18,2,16,27]。

在此轮调用中，中间数为 2，比 2 小的数值放入左侧 arrLeft，比 2 大的数值放入右侧 arrRight。

随后继续调用 quickSort(arrRight)。

后续过程类似，通过循环不断调用自身，直到传入参数的长度小于 1，此时直接返回该传入参数。

以上内容为本文的全部讲解，希望能为读者提供帮助，感谢对本站的支持！