zhengrenzhe's blog   About

快速排序

快速排序的核心步骤是:

JavaScript实现为:

function sort (arr, camp, left, right){
  // arr为被排序数组,camp控制排序是从大到小还是从小到大
  // left,right为分区的边界位置
  if(left > right){
    return ;
  }
  // 在第一次调用函数时,分区边界为整个数组
  left  = left  || 0;
  right = right || arr.length -1;

  // 获取基准元素位置,进行一次分区操作
  var index = sort.p(arr, camp, left, right);
  // 递归完成基准左边的元素
  sort(arr, camp, left, index -1);
  // 递归完成基准右边的元素
  sort(arr, camp, index +1 ,right);
}

// 交换两元素的位置
sort.s = function(arr, sleft, sright){
  var temp = arr[sright];
  arr[sright] = arr[sleft];
  arr[sleft]  = temp;
}

// 分区操作
sort.p = function(arr, camp, left, right){
  // 定义顺序存储变量index,为此分区最左边的元素
  // 定义基准元素为此分区最左边的元素
  var index = left,
      pivot = arr[index];

  // 将index的值与分区最后一个元素的位置交换
  sort.s(arr, index, right);

  // 遍历分区内的每个元素,遇到符合排序规则的元素则将它与index位置交换,index自增
  for(var i=left;i<right;i++){
    if(camp(arr[i],pivot)){
      sort.s(arr, i, index);
      index++;
    }
  }

  // 交换最后一个元素与index元素,此时index的位置就是基准元素最终的位置
  sort.s(arr, right, index);
  // 返回当前index,作为下一次递归的边界之一
  return index;
};

var arr = [1,0,2,9,3,8,4,7,5,6];
sort(arr, function(a, b){return a > b});
console.log(arr);

Chrome extensions开发-1 →