有学有练才叫学习:学而不思则罔,思而不学则殆:学而不习,纸上谈兵,习而不进,画地为牢!

快速排序 js(快速排序的JS实现(JavaScript))

javascript 炮渣日记 3周前 (11-17) 18次浏览 已收录 0个评论 扫描二维码

1、原理:

在数据集之中,选择一个元素作为”基准”,这里取数组中间的值。所有小于”基准”的元素,都移到”基准”的左边;所有大于”基准”的元素,都移到”基准”的右边。对”基准”左边和右边的两个子集,递归重复第一步和第二步,直到所有子集只剩下0个或者1个元素为止。最后返回左边子集,基准,右边子集的结合数组。

2.实现:

取第一个,中间,最后一个,来算基准数
// 三数取中
function getMedian(left, middle, right) {
  var temp = [left];
  middle > left ? temp.push(middle) : temp.unshift(middle);
  if (right > temp[1]) {
    temp.push(right);
  } else if (right < temp[0]) {
    temp.unshift(right);
  } else {
    temp.splice(1, 0, right); //方法向/从数组中添加/删除项目,然后返回被删除的项目。
  }
  return temp[1];
}

#在计算过程中,保留相同的
function quicksort(arr) {
  // 如果子集只剩下一个元素,或者没有元素,就直接返回该数组
  if (arr.length <= 1) {
    return arr;
  }
  var middleIdx = Math.floor(arr.length / 2);
  // 三数取中
  var pivot = getMedian(arr[0], arr[middleIdx], arr[arr.length - 1]);

  // 定义左子集和右子集和与基准相同的集
  var left = [];
  var right = [];
  var same = [];
  // 遍历,小于基准的元素移到基准的左边,大于基准的元素移到基准的右边,相同的暂存起来不需要再排序
  for (var i = 0, j = arr.length; i < j; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else if (arr[i] > pivot) {
      right.push(arr[i]);
    } else {
      same.push(arr[i]);
    }
  }
  // 最后返回左边子集,基准,右边子集的结合数组
  return quicksort(left).concat(same, quicksort(right));
}

3.总结

getMedian主要是优化,在(1,2,3,4,5,6,7,8) 选择了 8 的时候,进行优化。减少排序操作

喜欢 (0)
炮渣日记
关于作者:
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址