python排序算法-（5）歸并排序
歸并排序算法的時(shí)間復(fù)雜度為O(nlogn)，是一種高效的排序算法。 合并排序算法的核心思想是將一個(gè)大的數(shù)組分成兩個(gè)較小的數(shù)組，遞歸地對(duì)這兩個(gè)較小的數(shù)組進(jìn)行排序，最后合并回原來的數(shù)組。
import random
# 歸并函數(shù)
def merge(arr, l, m, r):
? ?# 創(chuàng)建兩個(gè)零數(shù)組
? ?n1 = m - l + 1
? ?n2 = r - m
? ?L = [0] * (n1)
? ?R = [0] * (n2)
? ?# 復(fù)制數(shù)組元素
? ?for i in range(0, n1):
? ? ? ?L[i] = arr[l + i]
? ?for j in range(0, n2):
? ? ? ?R[j] = arr[m + 1 + j]
? ?# 合并子數(shù)組
? ?i = 0 ?# 第一個(gè)子數(shù)組的初始索引
? ?j = 0 ?# 第二個(gè)子數(shù)組的初始索引
? ?k = l ?# 合并后的子數(shù)組的初始索引
? ?while i < n1 and j < n2:
? ? ? ?if L[i] <= R[j]:
? ? ? ? ? ?arr[k] = L[i]
? ? ? ? ? ?i += 1
? ? ? ?else:
? ? ? ? ? ?arr[k] = R[j]
? ? ? ? ? ?j += 1
? ? ? ?k += 1
? ?# 復(fù)制L剩余的元素（如果有）
? ?while i < n1:
? ? ? ?arr[k] = L[i]
? ? ? ?i += 1
? ? ? ?k += 1
? ?# 復(fù)制R剩余的元素（如果有）
? ?while j < n2:
? ? ? ?arr[k] = R[j]
? ? ? ?j += 1
? ? ? ?k += 1
# 歸并排序函數(shù)
def mergeSort(arr, l, r):
? ?if l < r:
? ? ? ?m = (l+r)//2
? ? ? ?# 對(duì)左右兩個(gè)子數(shù)組進(jìn)行遞歸排序
? ? ? ?mergeSort(arr, l, m)
? ? ? ?mergeSort(arr, m + 1, r)
? ? ? ?# 合并左右兩個(gè)有序子數(shù)組
? ? ? ?merge(arr, l, m, r)
# 測(cè)試
array=random.sample(range(0, 100), 50)
print("原始數(shù)組為:")
print(array)
size = len(array)
mergeSort(array,0,size-1)
print('歸并排序后的數(shù)組為:')
print(array)運(yùn)行環(huán)境：python3.8
運(yùn)行結(jié)果：
原始數(shù)組為:
[97, 11, 56, 36, 31, 48, 98, 34, 1, 55, 91, 58, 63, 46, 26, 68, 96, 10, 65, 72, 77, 6, 86, 92, 99, 51, 89, 64, 67, 87, 23, 21, 9, 70, 57, 2, 61, 75, 37, 74, 30, 20, 8, 41, 94, 15, 53, 33, 12, 44]
歸并排序后的數(shù)組為:
[1, 2, 6, 8, 9, 10, 11, 12, 15, 20, 21, 23, 26, 30, 31, 33, 34, 36, 37, 41, 44, 46, 48, 51, 53, 55, 56, 57, 58, 61, 63, 64, 65, 67, 68, 70, 72, 74, 75, 77, 86, 87, 89, 91, 92, 94, 96, 97, 98, 99]
