問(wèn)題

排序 [30, 24, 5, 58, 18, 36, 12, 42, 39]

歸并排序

歸并排序采用分治法，將序列分成若干子序列，每個(gè)子序列有序后再合并成有序的完整序列。

在數(shù)組排序中，如果只有一個(gè)數(shù)，那么它本身就是有序的。如果有兩個(gè)數(shù)，只需要進(jìn)行一次比較就可以完成排序。也就是說(shuō)，數(shù)越少，排序越容易。那么，如果有一個(gè)由大量數(shù)據(jù)組成的序列，可以考慮將其不斷分解，直到只剩一個(gè)數(shù)時(shí)，本身已經(jīng)有序，再將這些有序的數(shù)組合并在一起，從而完成排序。

圖解

1. 將待排序元素分成大小大致相同的兩個(gè)序列
2. 對(duì)兩個(gè)序列分別進(jìn)行歸并排序
3. 將排好序的有序子序列進(jìn)行合并，得到最終的有序序列
   

代碼

# 合并, 將兩個(gè)有序的子序列合并成一個(gè)序列
def merge(nums, low, mid, high):i, j = low, mid + 1k = 0temp = [0] * (high - low + 1)while i <= mid and j <= high:if nums[i] <= nums[j]:temp[k] = nums[i]i += 1else:temp[k] = nums[j]j += 1k += 1if i <= mid:temp[k:] = nums[i:mid+1]if j <= high:temp[k:] = nums[j:high+1]nums[low:high+1] = tempreturn numsdef merge_sort(nums, low = 0, high = len(nums)-1):if low < high:					# low = high時(shí)分解到只剩一個(gè)數(shù)，不用合并直接返回mid = low + (high - low) // 2merge_sort(nums, low, mid)			# 對(duì)左半部分進(jìn)行歸并排序merge_sort(nums, mid+1, high)		# 對(duì)右半部分進(jìn)行歸并排序return merge(nums, low, mid, high)	# 合并為有序子序列else:return nums

時(shí)間復(fù)雜度

歸并算法的時(shí)間復(fù)雜度為 O(nlogn)

• 分解：這一步僅僅是計(jì)算出子序列的中間位置，需要常數(shù)時(shí)間 O(1)
• 解決子問(wèn)題：遞歸求解兩個(gè)規(guī)模為 n/2 的子問(wèn)題，所需時(shí)間為 2T(n/2)
• 合并：合并算法可以在 O(n) 時(shí)間內(nèi)完成

所以總運(yùn)行時(shí)間為：

當(dāng) n>1 時(shí)，可以遞推求解：

遞推最終的規(guī)模為 1， 令 2^x = n，則 x = log n，那么