亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定

【九月打卡】第8天 歸并排序、快速排序

標簽:
JavaScript

课程名称:JavaScript版数据结构与算法
课程章节:第11章 进阶算法之“搜索排序”
主讲老师:lewis

课程内容:

今天学习的内容包括:
11-5 JavaScript 实现:归并排序——使用先分后合实现排序功能。
11-6 JavaScript 实现:快速排序——。

课程收获:

归并排序

归并排序的思路
  • 分:把数组劈成两半,在递归低对子数组进行"分"操作,直到分成一个个单独的数。
  • 合:把两个数合并为有序数组,在对有序数组进行合并,直到全部子数组合并为一个完整数组。
合并两个有序数组
  • 新建一个空数组res,用于存放最终排序后的数组。
  • 比较两个有序数组的头部,较小者出队并推入 res 中。
  • 如果两个数组还有值,就重复第二步。
let mid = Math.floor(arr.length / 2)
let left = arr.slice(0, mid)
let right = arr.slice(mid, arr.length)
let orderLeft = rec(left)
let orderRight = rec(right)
let res = []
while (orderLeft?.length || orderRight?.length) {
   res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())
}
归并排序的时间复杂度
  • 分的时间复杂度是O(logN)。
  • 合的时间复杂度是O(n)。
  • 时间复杂度:O(n*logN)。

快速排序

快速排序排序的思路
  • 分区:从数组中任意选择一个“基准”,所有比基准小的元素放在基准前面,比基准大的元素放在基准的后面。
  • 递归:递归地对基准前后的子数组进行分区。
 for (let i = 1; i < arr.length; i++) {
   if(arr[i] < mid){
     left.push(arr[i])
   }else{
     right.push(arr[i])
   }
 }
    
return [...rec(left),mid,...rec(right)]
快速排序的时间复杂度
  • 递归的时间复杂度是O(logN)。
  • 分区操作的时间复杂度是O(n)。
  • 时间复杂度:O(n*logN)。

今天学习了 归并排序、快速排序,这两个在实际工作中有很多的应用场景,这两个时间复杂度都是O(n*logN),在代码书写过程中,遇到了不少问题,也都一一解决了,跟课程中遇到的还是有些不同的。对自己说一句,加油😀~

坚持打卡,坚持学习!明天见💪~



https://img1.sycdn.imooc.com//631e93900001fbb719200902.jpg

https://img1.sycdn.imooc.com//631e93bb00017ab019200902.jpg

點擊查看更多內容
TA 點贊

若覺得本文不錯,就分享一下吧!

評論

作者其他優質文章

正在加載中
  • 推薦
  • 評論
  • 收藏
  • 共同學習,寫下你的評論
感謝您的支持,我會繼續努力的~
掃碼打賞,你說多少就多少
贊賞金額會直接到老師賬戶
支付方式
打開微信掃一掃,即可進行掃碼打賞哦
今天注冊有機會得

100積分直接送

付費專欄免費學

大額優惠券免費領

立即參與 放棄機會
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號

舉報

0/150
提交
取消