1. 合併排序
    1. 概念
    2. 範例
    3. 例題

合併排序

最後更新: 作者: 字数: 341 预计阅读时间: 1min

合併排序

python

概念

簡單來說就是透過遞迴等我們前面學到的東西，不斷的去做切割，再一步一步的比大小後拼湊回去，先從一個對一個，再從兩個對兩個，一值排下去。

範例

將[5, 9, 4, 8, 7]這一段數字進行排序，他順序將會是->[5], [9], [4], [8], [7]->[5, 9], [4, 8], [7]->[4, 5, 8, 9], [7]->[4, 5, 7, 8, 9]:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))


def merge(left, right):
    i = 0
    j = 0
    ans = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            ans.append(left[i])
            i += 1
        else:
            ans.append(right[j])
            j += 1
    while i < len(left):
        ans.append(left[i])
        i += 1
    while j < len(right):
        ans.append(right[j])
        j += 1
    return ans


arr = [5, 9, 4, 8, 7]

排序過程by AI

例題

題目
看起來我們可以直接用合併排序來完成，並且不像氣泡排序依樣會超時:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def merge_sort(arr):
            if len(arr) <= 1:
                return arr
            mid = len(arr) // 2
            return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))


        def merge(left, right):
            i = 0
            j = 0
            ans = []
            while i < len(left) and j < len(right):
                if left[i] <= right[j]:
                    ans.append(left[i])
                    i += 1
                else:
                    ans.append(right[j])
                    j += 1
            while i < len(left):
                ans.append(left[i])
                i += 1
            while j < len(right):
                ans.append(right[j])
                j += 1
            return ans
        return merge_sort(nums)