首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >图解算法-读后感-快速排序

图解算法-读后感-快速排序

作者头像
吴文周
发布2022-04-15 17:29:37
4260
发布2022-04-15 17:29:37
举报
文章被收录于专栏:吴文周的专栏吴文周的专栏

这我的的github地址:github,这是我的b站直播间每天都会直播写代码:前端自习室,期待关注!!!

有时候我们做一件事不因为它容易,而是因为它困难

看书都有半途而废的冲动,更何况是生活。看着算法导论,看着编译原理,哪些晦涩难懂的数学表达式,就是因为它难,所以我才更要学。

我的文章是没有多少点赞,我的视频是没有多少播放。有时候也在难,搞个噱头,做个什么40k前端面试指南,搞个程序员人生解惑?

这是我的长期主义吗?

我学习的目的是什么?单纯为了好的面试表现,我觉得不是,我觉得哪些是有意义的,传播知识,传播方法论可以,做自己的开源项目可以。坚持下去,与君共勉!!!!

分治法

所有的问题都很复杂,我经常在想,我这么牛逼,搞个项目,找个人哪怕做外包都比南京百分之90公司强,我为什么没有做起来? 我没有销售,没有人际。

所有问题混在一起看,都很复杂,都很繁琐。解决问题的第一步就拆分问题,第二步就是细化问题。

一个算法问题,首先就应该是划分类型,在这个类型里面去细化场景与实现。

分治法核心我个人觉得是把一个复杂的问题拆解成多个相同的小问题。

里面两个关键点,第一需要拆解成小问题,第二个变成相同的问题。

核心思想是归纳法

快速排序

实现

let array = new Set();
for (let i = 1; i <= 10; i++) {
array.add(parseInt(Math.random() * 100));
}
const targetList = Array.from(array);
console.log("targetList", targetList);
function quickSort(targetList) {
if (targetList.length <= 1) {
  return targetList;
}
const pivot = targetList[0];
const left = [];
const right = [];
for (let i = 1; i < targetList.length; i++) {
  if (targetList[i] < pivot) {
    left.push(targetList[i]);
  } else {
    right.push(targetList[i]);
  }
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
console.log("res", quickSort(targetList));

原理

小结

最差和平均

结束

是不是一个二分法的衍生熟悉的场景,\log_2(n),是我们的执行层数,每一层执n次,显然结果出来是:n*\log_2(n)

有时候最好就是平均,每次的数据都是随机的,我们的大部分执行结果去趋近这个最好状态的。

优化

正因为上面的情况,数据有本身的特殊性,可能本身数据就是一个有序的数组,算法里面开始也没有进行有序性的校验,再我们执行的过程中就会出现最差的情况。

怎么去避免呢?随机化,每次比较的值都是不确定的,也不一定取第一个。 在有序数据的场景下面,随机化能带来巨大的收益。

代码对比

let array = [];
const count = 1000;
for (let i = 1; i <= count; i++) {
// array.add(parseInt(Math.random() * count));
// array.push(parseInt(Math.random() * count));
array.push(i);
}
// const targetList = Array.from(array);
const targetList = array;
// console.log("targetList", targetList);
// 普通快排
function quickSort(list) {
const targetList = [...list];
if (targetList.length <= 1) {
  return targetList;
}
const pivot = targetList[0];
const left = [];
const right = [];
for (let i = 1; i < targetList.length; i++) {
  if (targetList[i] < pivot) {
    left.push(targetList[i]);
  } else {
    right.push(targetList[i]);
  }
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
// console.log("res", quickSort(targetList));
console.time("quickSort");
// console.log("quickSort", quickSort(targetList));
quickSort(targetList);
console.timeEnd("quickSort");
// 随机快排
function randomQuickSort(list) {
const targetList = [...list];
if (targetList.length <= 1) {
  return targetList;
}
const random = Math.floor(targetList.length * Math.random());
// console.log("random", random, "length", targetList.length);
// const random = Math.floor(targetList.length / 2);
const pivot = targetList[random];
const left = [];
const right = [];
for (let i = 0; i < targetList.length; i++) {
  if (i === random) {
    continue;
  }
  if (targetList[i] < pivot) {
    left.push(targetList[i]);
  } else {
    right.push(targetList[i]);
  }
}
return [...randomQuickSort(left), pivot, ...randomQuickSort(right)];
}
console.time("randomQuickSort");
// console.log("randomQuickSort", randomQuickSort(targetList));
randomQuickSort(targetList);
console.timeEnd("randomQuickSort");

结论

  • 都是随机数据,随机快排和普通快排的收益并不明显,因为随机本身就有部分性能损坏
  • 如果是有序数据,随机快排性能爆炸,完全是 n\log_2(n),大家可以试一试。
  • 如果是有序数据不能太大,在递归调用时,如果是普通快排,会导致堆栈溢出,而随机快排不会
  • 建议在递归场景下面使用随机快排,效果明显,堆栈溢出概率低

总结

  1. 坚持长期主义。我的年薪百万一定是在我读完,编译原理,算法导论,深入理解计算机系统 这三本书之后。
  2. 大问题拆成小问题,再去解决小问题。
  3. 人的一生不应该有太多的目标,每个兔子都去跑过去追两下,兔子很多,我们追着追着自己就累了。
  4. 先实现,再优化,代码如此,人生也是如此。
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2022/04/12 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 分治法
  • 快速排序
    • 实现
      • 原理
        • 小结
      • 优化
        • 代码对比
        • 总结
        相关产品与服务
        云直播
        云直播(Cloud Streaming Services,CSS)为您提供极速、稳定、专业的云端直播处理服务,根据业务的不同直播场景需求,云直播提供了标准直播、快直播、云导播台三种服务,分别针对大规模实时观看、超低延时直播、便捷云端导播的场景,配合腾讯云视立方·直播 SDK,为您提供一站式的音视频直播解决方案。
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档