iT邦幫忙

2021 iThome 鐵人賽

DAY 6
1
自我挑戰組

【帶你輕鬆入門演算法-Leetcode】系列 第 6

【第六天 - Bubble Sort 介紹】

Q1. Bubble Sort 是什麼?

  • 一種排序方式,bubble sort 是透過兩兩相比,將正確順序逐漸往後/往前放。每次跑完一次全部數字比對,就會有一個正確的順序被固定下來,可能是最大、最小值。

  • 以由小到大的排序為例,逐漸將最大的往後排(如動畫顯示)
    bubble 先找最大
    (動畫來源於 https://pjchender.blogspot.com/2017/09/bubble-sort.html )

  • 由小到大的排序為例,除了如上動畫將最大逐漸往後排,他也可以從後往前,先將最小值逐漸往前排(如動畫顯示)

  • bubble 先找最小
    (動畫來源於 https://www.itread01.com/content/1544409122.html )

  • bubble sort 動畫:https://visualgo.net/zh/sorting

    • 課間小Q&A: 要從大到小排序,使用 bubble sort 概念可以套用嗎?
      • ANS: 可以,一樣透過兩兩相比,將最小值逐漸往後面放,或者是透過兩兩相比,將最大值逐漸往前放

Q2. 學會 Bubble Sort 概念可以做什麼 ?

  • 生活中時常會需要使用到排序好的資料,例如
    • 班級上分數從低到高排序
    • 線上撲克牌遊戲,牌面由 A~K 排序
  • 常見排序方法有許多種,bubble sort 算是比較基礎、直觀的,還有選擇排序、插入排序、快速排序等,每一種排序算法所需的時間都不同,詳細可以參考:https://www.runoob.com/w3cnote/ten-sorting-algorithm.html
  • 接下來第8天,我們將介紹 Quick Sort

Lab. 明天要解的題目:912. Sort an Array

  • 題目連結:https://leetcode.com/problems/sort-an-array/

  • 題目敘述:

    • 會有一個 nums 變數,裡面儲存著要排序的內容,我們要將內容由小到大進行排序
      題目敘述
  • 會拿到 nums 的變數,須回傳排序好的資料
    題目I/O

  • 題目的條件:

    • 可能會有 1~ 50000 個數字要進行排序
    • 每個數字會在 - 0.0005 ~ 50000 之間
      題目限制
  • 看完題目你需要思考的是:

    • 依照此題的 nums 長度,bubble sort 這個算法,會不會可能造成超時? 是不是有其他算法?

上一篇
【第五天 - Queue 題目分析】
下一篇
【第七天 - Bubble Sort 題目分析】
系列文
【帶你輕鬆入門演算法-Leetcode】30

尚未有邦友留言

立即登入留言