JavaScript 快速排序算法实现与递归原理详解

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);

快速排序原理与递归要点

快速排序的核心原理包含三个步骤：确定基准点、建立两个数组分别存储分割后的元素、以及进行递归调用。

基准点：即选取数组中间的一个数值作为比较标准；

建立两个数组分别存储：以该基准点为界，将小于和大于该值的元素分别存入两个新定义的数组中；

递归：在函数内部调用函数自身；

在此总结使用递归时的关键点：

1. 必须包含判断条件并返回一个值，否则会导致死循环；

2. 在内部调用自身时，传递的参数应是内部定义的某个变量，且该变量与初始传入的参数存在关联；

3. 若需执行相同的工作逻辑，可考虑采用递归方式；

递归执行过程详解

首次执行函数时的变量状态：中间数为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，即返回该传入的参数。