iT邦幫忙

2021 iThome 鐵人賽

DAY 21
1
Software Development

資料結構與演算法,使用JavaScript與Python系列 第 21

【Day21】[演算法]-排序Sort & 氣泡排序法Bubble Sort

排序(Sorting)

排序(Sorting)在電腦領域中是非常普遍且重要工作,即是將一群不規格的資料按照某個規格來重新排列,讓排序過的資料容易閱讀、利於統計整理、和減少搜尋時間,假若資料只有10筆左右,還能以人工的方式排序,但若資料多到萬筆以上就會相當困難,因此,排序演算法就變得相當重要。


氣泡排序法(Bubble Sort)

氣泡排序法(Bubble Sort)又稱交換排序法,原理是從第一筆資料開始,逐一比較相鄰兩筆資料,如果兩筆大小順序有誤則做交換,反之則不動,接者再進行下一筆資料比較,所有資料比較完第1回合後,可以確保最後一筆資料是正確的位置。

下面利用40 30 60 50 20由小到大排序。
https://ithelp.ithome.com.tw/upload/images/20211002/20121027K4gjOElSjD.jpg


n=5
第1回合比較了4次,n-1次
第2回合比較了3次,n-2次
第3回合比較了2次,n-3次
第4回合比較了1次,n-4次
總共比較了4回合,n-1回合

(n-1) + (n-2) + .... + 1 = n(n-1) / 2
平均時間複雜度為: O(n²)


JavaScript

let data = [8,6,1,10,5,3,9,2,7,4]

function BubbleSort(array){
  let len = array.length
  while (len > 1) {
    len--
    for (let i = 0; i < len; i++) {
      // 如果前面的元素比後面的元素要大,則交換元素位置
      if (array[i] > array[i + 1]) {
        [array[i], array[i + 1]] = [array[i + 1], array[i]];
      }
    }
  }
  return array
}
console.log(BubbleSort(data))//[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Python

#Bubble Sort
data = [89, 34, 23, 78, 67, 100, 66, 29, 79, 55, 78, 88, 92, 96, 96, 23]

def BubbleSort(data):
    n = len(data)
    while n > 1:
        n-=1
        for i in range(n):        
            if data[i] > data[i+1]:  
                data[i], data[i+1] = data[i+1], data[i]
    return data

print(BubbleSort(data))
#[23, 23, 29, 34, 55, 66, 67, 78, 78, 79, 88, 89, 92, 96, 96, 100]

上一篇
【Day20】[資料結構]-圖Graph-實作
下一篇
【Day22】[演算法]-選擇排序法Selection Sort
系列文
資料結構與演算法,使用JavaScript與Python35
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言