合併排序

Data Structures and Algorithms in Python

Miriam Antona

Software engineer

合併排序

  • 採用 分而治之
    • 分解
      • 將問題切成較小的子問題
    • 征服
      • 遞迴解各子問題
    • 合併
      • 合併子問題解答得到最終結果
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 merge_sort(my_list):
  if len(my_list) > 1:

    mid = len(my_list)//2
    left_half = my_list[:mid]
    right_half = my_list[mid:]

    merge_sort(left_half)
    merge_sort(right_half)


    i = j = k = 0

    while i < len(left_half) and j < len(right_half):

      if left_half[i] < right_half[j]:

        my_list[k] = left_half[i]

        i += 1

      else:

        my_list[k] = right_half[j]

        j += 1

      k += 1

    while i < len(left_half):

      my_list[k] = left_half[i]
      i += 1
      k += 1


    while j < len(right_half):
      my_list[k] = right_half[j]
      j += 1
      k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)

[1, 4, 20, 22, 30, 35, 40, 50, 90]
Data Structures and Algorithms in Python

合併排序：複雜度

  • 最差情況：$O(n\log{}n)$
    • 比 bubble sort、selection sort、insertion sort 明顯更好
    • 適合大型清單排序
  • 平均情況：$\Theta(n\log{}n)$
  • 最佳情況：$\Omega(n\log{}n)$
    • 其他演算法（如 bubble sort、insertion sort）最佳情況更優
  • 空間複雜度：$O(n)$
    • 低於 $O(1)$ 空間的其他演算法
  • 也有變體可降低空間需求
Data Structures and Algorithms in Python

一起來練習吧！

Data Structures and Algorithms in Python

Preparing Video For Download...