氣泡排序

Data Structures and Algorithms in Python

Miriam Antona

Software engineer

排序演算法

  • 深入研究
  • 解決如何將未排序集合依遞增/遞減排序
  • 可降低問題複雜度
  • 常見排序演算法：
    • bubble sort
    • selection sort
    • insertion sort
    • merge sort
    • quicksort
Data Structures and Algorithms in Python

氣泡排序

未排序數列的示意圖。有一個指標指向第一個元素，另一個指標指向第二個元素。

  • 第一個值大於第二個值
Data Structures and Algorithms in Python

氣泡排序

未排序數列的示意圖。有一個指標指向第一個元素，另一個指標指向第二個元素。第一與第二個元素已互換。

  • 第一個值大於第二個值
    • 交換
  • 第二個值大於第一個值
    • 無動作
Data Structures and Algorithms in Python

氣泡排序

未排序數列的示意圖。有一個指標指向第二個元素，另一個指標指向第三個元素。

  • 第一個值大於第二個值
    • 交換
  • 第二個值大於第一個值
    • 無動作
Data Structures and Algorithms in Python

氣泡排序

未排序數列的示意圖。有一個指標指向第三個元素，另一個指標指向第四個元素。

  • 第一個值大於第二個值
    • 交換
  • 第二個值大於第一個值
    • 無動作
Data Structures and Algorithms in Python

氣泡排序

未排序數列的示意圖。有一個指標指向第三個元素，另一個指標指向第四個元素。第三與第四個元素已互換。

  • 第一個值大於第二個值
    • 交換
  • 第二個值大於第一個值
    • 無動作
Data Structures and Algorithms in Python

氣泡排序

未排序數列的示意圖。有一個指標指向第四個元素，另一個指標指向第五個元素。

  • 第一個值大於第二個值
    • 交換
  • 第二個值大於第一個值
    • 無動作
Data Structures and Algorithms in Python

氣泡排序

未排序數列的示意圖。有一個指標指向第四個元素，另一個指標指向第五個元素。第四與第五個元素已互換。

  • 第一個值大於第二個值
    • 交換
  • 第二個值大於第一個值
    • 無動作
Data Structures and Algorithms in Python

氣泡排序

未排序數列的示意圖。有一個指標指向第四個元素，另一個指標指向第五個元素。第五個元素因已就位而標成藍色。

  • 第一個值大於第二個值
    • 交換
  • 第二個值大於第一個值
    • 無動作
Data Structures and Algorithms in Python

氣泡排序

未排序數列的示意圖。有一個指標指向第一個元素，另一個指標指向第二個元素。最後一個元素是藍色。

  • 第一個值大於第二個值
    • 交換
  • 第二個值大於第一個值
    • 無動作
Data Structures and Algorithms in Python

氣泡排序

未排序數列的示意圖。有一個指標指向第二個元素，另一個指標指向第三個元素。最後一個元素是藍色。

  • 第一個值大於第二個值
    • 交換
  • 第二個值大於第一個值
    • 無動作
Data Structures and Algorithms in Python

氣泡排序

未排序數列的示意圖。有一個指標指向第二個元素，另一個指標指向第三個元素。第二與第三個元素已互換。最後一個元素是藍色。

  • 第一個值大於第二個值
    • 交換
  • 第二個值大於第一個值
    • 無動作
Data Structures and Algorithms in Python

氣泡排序

未排序數列的示意圖。有一個指標指向第三個元素，另一個指標指向第四個元素。最後一個元素是藍色。

  • 第一個值大於第二個值
    • 交換
  • 第二個值大於第一個值
    • 無動作
Data Structures and Algorithms in Python

氣泡排序

未排序數列的示意圖。有一個指標指向第三個元素，另一個指標指向第四個元素。最後兩個元素是藍色。

  • 第一個值大於第二個值
    • 交換
  • 第二個值大於第一個值
    • 無動作
Data Structures and Algorithms in Python

氣泡排序

未排序數列的示意圖。有一個指標指向第一個元素，另一個指標指向第二個元素。最後兩個元素是藍色。

  • 第一個值大於第二個值
    • 交換
  • 第二個值大於第一個值
    • 無動作
Data Structures and Algorithms in Python

氣泡排序

未排序數列的示意圖。有一個指標指向第一個元素，另一個指標指向第二個元素。第一與第二個元素已互換。最後兩個元素是藍色。

  • 第一個值大於第二個值
    • 交換
  • 第二個值大於第一個值
    • 無動作
Data Structures and Algorithms in Python

氣泡排序

未排序數列的示意圖。有一個指標指向第二個元素，另一個指標指向第三個元素。最後兩個元素是藍色。

  • 第一個值大於第二個值
    • 交換
  • 第二個值大於第一個值
    • 無動作
Data Structures and Algorithms in Python

氣泡排序

未排序數列的示意圖。有一個指標指向第二個元素，另一個指標指向第三個元素。最後三個元素是藍色。

  • 第一個值大於第二個值
    • 交換
  • 第二個值大於第一個值
    • 無動作
Data Structures and Algorithms in Python

氣泡排序

未排序數列的示意圖。有一個指標指向第一個元素，另一個指標指向第二個元素。最後三個元素是藍色。

  • 第一個值大於第二個值
    • 交換
  • 第二個值大於第一個值
    • 無動作
Data Structures and Algorithms in Python

氣泡排序

未排序數列的示意圖。有一個指標指向第一個元素，另一個指標指向第二個元素。最後四個元素是藍色。

  • 第一個值大於第二個值
    • 交換
  • 第二個值大於第一個值
    • 無動作
Data Structures and Algorithms in Python

氣泡排序

未排序數列的示意圖。有一個指標指向第一個元素，另一個指標指向第二個元素。所有元素都是藍色。

  • 第一個值大於第二個值
    • 交換
  • 第二個值大於第一個值
    • 無動作
Data Structures and Algorithms in Python

氣泡排序－實作

def bubble_sort(my_list):
  list_length = len(my_list)
  for i in range(list_length-1):
    for j in range(list_length-1-i):

      if my_list[j] > my_list[j+1]:

        my_list[j] , my_list[j+1] = my_list[j+1] , my_list[j]

  return my_list

print(bubble_sort([4,3,7,1,5]))

[1, 3, 4, 5, 7]
Data Structures and Algorithms in Python

氣泡排序－實作

def bubble_sort(my_list):
  list_length = len(my_list)
  is_sorted = False

  while not is_sorted:

    is_sorted = True

    for i in range(list_length-1):

      if my_list[i] > my_list[i+1]:

        my_list[i] , my_list[i+1] = my_list[i+1] , my_list[i]

        is_sorted = False

    list_length -= 1

  return my_list
Data Structures and Algorithms in Python

氣泡排序－複雜度

  • 最差情況：$O(n^2)$
  • 最佳情況－未改良版：$\Omega(n^2)$
  • 最佳情況－改良版：$\Omega(n)$
  • 平均情況：$\Theta(n^2)$
  • 對高度未排序且很大的清單表現不佳
  • 表現良好於：
    • 很大且已排序/幾乎已排序的清單
    • 小型清單
Data Structures and Algorithms in Python

一起來練習吧！

Data Structures and Algorithms in Python

Preparing Video For Download...