javascript 递归之 快速排序

1. 快速排序思想

  (1)在数据集之中,选择一个元素作为"基准"(pivot)。

  (2)所有小于"基准"的元素,都移到"基准"的左边;所有大于"基准"的元素,都移到"基准"的右边。

  (3)对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

2. 数字数组排序步骤分析

  (1) 原始数组  [23,4,16,49,34,86,801]  

  (2) 确定中间位置,将原数组一分为二后  [23,4,16,34] 49  [86,801]

  (3) 对左半部分和右半部分数组分别进行上述操作  4 [23,16,34]  49  86 [801]

  (4) 重复第三部分  4 16 [23,34] 49 86 801

  (5) 4 16 23 [34] 49 86 801

  (6) 4 16 23 34 49 86 801

3.基于递归思想的javascript实现

function quickSort(arr){
if(arr.length <= 1){ //长度小于1直接返回
return arr;
}
var pivotIndex = Math.floor(arr.length/2); //向上取整,取中间位置
var pivot = arr[pivotIndex ];  //取中间值
var less = Array(), greater = Array();
for (var i = 0; i < arr.length; i++){
if(i !=pivotIndex ){
    if (arr[i] >= pivot ) {
greater .push(arr[i]);  //右半部分
    }else {
less .push(arr[i]);  //左半部分
    }
}
 }
return quickSort(less).concat([pivot],quickSort(greater));  //递归调用
}

  操作javascript数组也可去除中间元素后直接去掉中间元素,遍历的时候可少进行一次判断

var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];

  

for (var i = 0; i < arr.length; i++){
    if (arr[i] >= pivot ) {
greater .push(arr[i]);  //右半部分
    }else {
less .push(arr[i]);  //左半部分
    }
 }

  

上一篇:Android开发 - 掌握ConstraintLayout(七)辅助线(Guideline)


下一篇:jQuery效果之隐藏与显示、淡入淡出、滑动、回调