iT邦幫忙

2021 iThome 鐵人賽

DAY 7
1
自我挑戰組

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

【第七天 - Bubble Sort 題目分析】

先簡單回顧一下,今天預計分析的題目:

  • 題目敘述
  • 題目I/O

如何利用 Bubble sort 進行排序?

  1. 我們要將下圖六個數字進行從小到大的排序
    • 原始資料
  2. 我們現在要把最大的放到最後一個位置(第六個位置),所以我們會比較六個數字,兩兩做比較,逐漸將最大值向後移
    • max
  3. 我們現在要把第二大的放到第五個位置,所以我們會比較剩下的五個數字,兩兩做比較,逐漸將最二大值向後移
    • sec max
  4. 我們現在要把第三大的放到第四個位置,所以我們會比較剩下的四個數字,兩兩做比較,逐漸將第三大值向後移,以此類推,直到將全部的數字排列完成
    • thi max
  5. 我們就會發現有N個數字
    • 我們就要比較 N-1 輪,才能把全部數字排列完
    • 我們要把數字放到正確的第 j 個位置,我們就會比較剩下的 j 個數字
  6. 最終排序過程如下
  • python 實作 bubble sort 如下
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
#       若有 N 個數字要排序,則要執行 N-1 輪
        for i in range(len(nums)-1,0,-1):
#           每次比較會從 0 ~ i-1 個做比較,每次會把最大的數字丟到最後面 
            for j in range(i):
#               若第 j 筆資料 大於 第 j+1 筆資料,則兩兩交換
                if nums[j] > nums[j+1]:
                    t = nums[j]
                    nums[j] = nums[j+1]
                    nums[j+1] = t
        return nums
  • 不過你可以看見,Bubble Sort 基本上需要兩個迴圈執行,才能排序完成,加上需要不斷交換位置,才能將數字排序到正確的位置,在面對多筆資料需要排序的情況下,Bubble Sort 排序效率太低,當資料量變多,便容易造成 Time Limit Exceeded 的情況
  • 由於 Bubble Sort 過程容易理解與實作,是排序的基本算法,也是面試常考的算法之一,故在此系列文章提出來做介紹
  • 明天我們將介紹 Quick Sort,能夠減少排序時間,並且解決 912. Sort an Array 題目

上一篇
【第六天 - Bubble Sort 介紹】
下一篇
【第八天 - Quick Sort 介紹】
系列文
【帶你輕鬆入門演算法-Leetcode】30

尚未有邦友留言

立即登入留言