归并排序

Python 中的数据结构与算法

Miriam Antona

Software engineer

归并排序

遵循分治法
- 分解
  - 将问题拆成更小的子问题
- 解决
  - 递归地求解子问题
- 合并
  - 合并子问题解以得到最终结果

归并排序 - 演示

一个包含未排序数字的列表示意图。

归并排序 - 演示

一个包含未排序数字的列表示意图。该列表被分成两部分。

归并排序 - 演示

一个包含未排序数字的列表示意图。列表被分成两部分。出现两个新列表：左半部分和右半部分。

归并排序 - 演示

一个包含未排序数字的列表示意图。新列表被分成两部分。

归并排序 - 演示

一个包含未排序数字的列表示意图。显示对上一步列表继续划分得到的新列表。

归并排序 - 演示

一个包含未排序数字的列表示意图。新列表被分成两部分。

归并排序 - 演示

一个包含未排序数字的列表示意图。显示对上一步列表继续划分得到的新列表。

归并排序 - 演示

一个包含未排序数字的列表示意图。新列表被分成两部分。

归并排序 - 演示

一个包含未排序数字的列表示意图。新列表被分成两部分。

归并排序 - 演示

一个包含未排序数字的列表示意图。最后划分的列表中的元素已各自排序。

归并排序 - 演示

一个包含未排序数字的列表示意图。最后划分的列表已合并并排序。

归并排序 - 演示

一个包含未排序数字的列表示意图。最后划分的列表已合并并排序。

归并排序 - 演示

一个包含未排序数字的列表示意图。最后划分的列表已合并并排序。所有元素已排序。

归并排序 - 实现

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]

归并排序 - 复杂度

最坏情况：$O(n\log{}n)$
- 比冒泡、选择、插入排序显著更优
- 适合大列表排序
平均情况：$\Theta(n\log{}n)$
最好情况：$\Omega(n\log{}n)$
- 其他算法（如冒泡、插入）最好情况更好
空间复杂度：$O(n)$
- 比 $O(1)$ 空间的算法更差
其他变体可降低空间占用

Passons à la pratique !

Python 中的数据结构与算法