下面是一個用Python實現歸并排序的示例代碼:
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
left = merge_sort(left)
right = merge_sort(right)
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# 將剩余的元素添加到結果中
result.extend(left[i:])
result.extend(right[j:])
return result
# 示例用法
arr = [5, 3, 8, 6, 2, 7, 1, 4]
sorted_arr = merge_sort(arr)
print(sorted_arr)
這段代碼定義了兩個函數:merge_sort
和merge
。merge_sort
函數使用遞歸將數組分成兩半,并分別對左右兩半進行歸并排序。最后,通過調用merge
函數將左右兩半合并成一個有序數組。merge
函數比較左右兩個有序數組的元素,將較小的元素添加到結果中,直到其中一個數組的元素全部添加完畢。然后,將剩余的元素添加到結果中。最后,返回合并后的有序數組。在示例用法中,我們定義了一個未排序的數組arr,并使用merge_sort函數對其進行排序,然后打印排序后的結果。