數(shù)組排序算組之歸并排序
??歸并排序（Merge Sort）是數(shù)組排序算法中一種常見的算法，其主要思想為經(jīng)典的“分治思想”。本文將介紹數(shù)組排序算法中的歸并排序，并介紹其相關(guān)應(yīng)用。
??本文的文章結(jié)構(gòu)分布如下：
從合并兩個有序數(shù)組講起
數(shù)組歸并排序
合并K個有序數(shù)組
歸并排序的應(yīng)用
首先，我們從合并兩個有序數(shù)組開始，這是歸并排序的基礎(chǔ)。
從合并兩個有序數(shù)組講起
??假設(shè)我們有兩個已經(jīng)排好序（不妨假設(shè)為升序）的數(shù)組nums1和nums2，如何將這兩個數(shù)組合并起來呢？其實想法是比較簡單的，就是用雙指針法。用兩個指針分別指向這兩個數(shù)組，然后分別從頭到尾遍歷，需要注意比較兩個指針指向的數(shù)字大小，具體算法如下：
假設(shè)合并后的數(shù)字為
sorted，初始化為空數(shù)組；如果指向數(shù)組
nums1的指針已經(jīng)達到數(shù)組nums1的末尾，則將數(shù)組nums2中的剩余元素依次添加至sorted中；如果指向數(shù)組
nums2的指針已經(jīng)達到數(shù)組nums2的末尾，則將數(shù)組nums1中的剩余元素依次添加至sorted中；如果兩個指針都沒有達到數(shù)組的結(jié)尾，則比較該指針指向的數(shù)字，數(shù)字小的添加至
sorted中，同時該指針向后移動一位。
??我們以數(shù)組[1,2, 3]和[2,5,6]為例，其合并過程如下圖：
兩個有序數(shù)組的合并 ??該算法的Python程序如下：
def merge(nums1, nums2):
result = []
m, n = len(nums1), len(nums2)
p1, p2 = 0, 0
while p1 < m or p2 < n:
if p1 == m:
result.append(nums2[p2])
p2 += 1
elif p2 == n:
result.append(nums1[p1])
p1 += 1
elif nums1[p1] < nums2[p2]:
result.append(nums1[p1])
p1 += 1
else:
result.append(nums2[p2])
p2 += 1
return result
if __name__ == '__main__':
a = [1, 2, 3]
b = [2, 5, 6]
sol = merge(a, b)
print('arrays: {} and {}, merge: {}'.format(a, b, sol))
a = [1, 2]
b = [2, 5, 6]
sol = merge(a, b)
print('arrays: {} and {}, merge: {}'.format(a, b, sol))
a = [1, 2, 3, 4]
b = [2, 5, 6]
sol = merge(a, b)
print('arrays: {} and {}, merge: {}'.format(a, b, sol))
運行結(jié)果如下：
arrays: [1, 2, 3] and [2, 5, 6], merge: [1, 2, 2, 3, 5, 6]
arrays: [1, 2] and [2, 5, 6], merge: [1, 2, 2, 5, 6]
arrays: [1, 2, 3, 4] and [2, 5, 6], merge: [1, 2, 2, 3, 4, 5, 6]
數(shù)組歸并排序
??經(jīng)過上述介紹，我們已經(jīng)知曉如何合并兩個有序數(shù)組了。接下來，我們討論如何對數(shù)組進行排序。利用“分而治之”的想法，我們將原始數(shù)組result分為兩部分left和right，兩部分長度盡可能接近。如果left和right已經(jīng)排好序了，那么將這兩個排序數(shù)組合并即可。問題就變?yōu)槿绾螌?code style="font-size: inherit;line-height: inherit;overflow-wrap: break-word;padding: 2px 4px;border-radius: 4px;margin-right: 2px;margin-left: 2px;color: rgb(248, 35, 117);background: rgb(248, 248, 248);">left和right排序？但此時，我們發(fā)現(xiàn)left和right的長度大約為原始元素result的一半，因此我們可以不停地left和right拆分，直到它們的長度為0或者1，那么此時這兩個數(shù)組已經(jīng)排好序了，最后我們再將分拆后的數(shù)組自下而上地進行合并結(jié)果即可。
??我們以數(shù)組[6,5,12,10,9,1]為例，具體演示該過程：
??歸并排序的Python實現(xiàn)代碼如下（merge函數(shù)參考前面代碼）：
def merge_sort(lst):
if len(lst) <= 1:
return lst # 從遞歸中返回長度為1的序列
middle = len(lst) // 2
left = merge_sort(lst[:middle]) # 通過不斷遞歸，將原始序列拆分成n個小序列
right = merge_sort(lst[middle:])
return merge(left, right)
if __name__ == '__main__':
a = [6, 5, 12, 10, 9, 1]
result = merge_sort(a)
print('array: {}, after merge sort: {}'.format(a, result))
a = [6, 5, 12, 10]
result = merge_sort(a)
print('array: {}, after merge sort: {}'.format(a, result))
a = [1, 2, 3, 2, 5, 6]
result = merge_sort(a)
print('array: {}, after merge sort: {}'.format(a, result))
運行結(jié)果如下：
array: [6, 5, 12, 10, 9, 1], after merge sort: [1, 5, 6, 9, 10, 12]
array: [6, 5, 12, 10], after merge sort: [5, 6, 10, 12]
array: [1, 2, 3, 2, 5, 6], after merge sort: [1, 2, 2, 3, 5, 6]
??數(shù)組的歸并排序算法的時間復(fù)雜度為O(n*log n), 空間復(fù)雜度為O(n)，其中n代表數(shù)組的長度，并且歸并排序算法是穩(wěn)定的。
合并K個有序數(shù)組
??假如我們將合并兩個有序數(shù)組擴展成K個有序數(shù)組（不妨假設(shè)都是升序排列）的情形呢？其實，我們也可以借鑒數(shù)組的歸并排序的思想。
??我們將長度為K的有序數(shù)組列表，按中間數(shù)組分成長度大致相同的兩個數(shù)組列表，利用分拆、合并的辦法可以將這兩個數(shù)組列表合并（此時問題的數(shù)組列表規(guī)模大致為原先的一半），再合并生成的這兩個列表即可。
??具體實現(xiàn)的Python代碼如下：
def merge_k_sort(lists):
n = len(lists)
if n == 0:
return []
elif n == 1:
return lists[0]
else:
middle = n // 2
left = merge_k_sort(lists[:middle])
right = merge_k_sort(lists[middle:])
return merge(left, right)
if __name__ == '__main__':
lists = [[1, 2], [3, 5], [7, 9]]
result = merge_k_sort(lists)
print('lists: {}, after merge: {}'.format(lists, result))
lists = [[1, 2], [3, 5], [7, 9], [4, 10]]
result = merge_k_sort(lists)
print('lists: {}, after merge: {}'.format(lists, result))
lists = [[1, 2], [3, 5], [7, 9], [4, 10], [6, 8, 12]]
result = merge_k_sort(lists)
print('lists: {}, after merge: {}'.format(lists, result))
運行結(jié)果如下：
lists: [[1, 2], [3, 5], [7, 9]], after merge: [1, 2, 3, 5, 7, 9]
lists: [[1, 2], [3, 5], [7, 9], [4, 10]], after merge: [1, 2, 3, 4, 5, 7, 9, 10]
lists: [[1, 2], [3, 5], [7, 9], [4, 10], [6, 8, 12]], after merge: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12]
??其實，我們可以將數(shù)組的排序轉(zhuǎn)化為合并K個數(shù)組問題。我們只需要將數(shù)組的每個元素單獨組成一個列表，長度為1，則合并這些長度為1的列表即可，因為它們已經(jīng)排好序了！
if __name__ == '__main__':
nums = [6, 5, 12, 10, 9, 1]
lists = [[x] for x in nums]
result = merge_k_sort(lists)
print('array: {}, result: {}'.format(nums, result))
歸并排序的應(yīng)用
??該部分將介紹歸并排序的應(yīng)用，主要介紹數(shù)組的逆序?qū)栴}。歸并排序的應(yīng)用主要如下：
鏈表排序
數(shù)組的逆序?qū)?shù)量問題
外部排序（External Sorting）
??其中鏈表排序也可以用歸并排序思想實現(xiàn)，其大致思路差不多，主要是鏈表本身與數(shù)組的數(shù)據(jù)結(jié)構(gòu)上的差異，其基礎(chǔ)仍然是合并兩個有序鏈表。
??重點介紹數(shù)組的逆序?qū)?shù)量問題。所謂數(shù)組的逆序?qū)Γ傅氖菍τ跀?shù)組a的兩個下標位置i和j，滿足i
數(shù)組[8,4,2,1]，其逆序?qū)?shù)量為6；
數(shù)組[1, 20, 6, 4, 5]，其逆序?qū)?shù)量為5；
??我們也用歸并排序思想也解決數(shù)組的逆序?qū)?shù)量問題。我們考慮以下情況：
對于數(shù)組a，將其拆分成inv1和inv2，那么數(shù)組a的逆序?qū)?shù)量，應(yīng)該是inv1的逆序?qū)?shù)量加上inv2的逆序?qū)?shù)量以及inv1和inv2按升序排列后合并時產(chǎn)生的逆序?qū)?shù)量。
??將inv1和inv2升序排列，可以用歸并排序思想。那么為什么要對inv1和inv2按升序排列呢？這是因為，如果將inv1和inv2升序排序后，如果inv1中的位置i和inv2中的位置j滿足inv1[i]>inv2[j],那么inv1在i后面的元素都大于inv2[j]，這樣就方便計算了。
??數(shù)組的逆序?qū)?shù)量問題的Python實現(xiàn)代碼如下：
# Function to Use Inversion Count
def mergeSort(arr, n):
temp_arr = [0] * n
return _mergeSort(arr, temp_arr, 0, n - 1)
# This Function will use MergeSort to count inversions
def _mergeSort(arr, temp_arr, left, right):
inv_count = 0
if left < right:
mid = (left + right) // 2
inv_count += _mergeSort(arr, temp_arr, left, mid)
inv_count += _mergeSort(arr, temp_arr, mid + 1, right)
inv_count += merge(arr, temp_arr, left, mid, right)
return inv_count
# This function will merge two subarrays in a single sorted subarray
def merge(arr, temp_arr, left, mid, right):
i = left # Starting index of left subarray
j = mid + 1 # Starting index of right subarray
k = left # Starting index of to be sorted subarray
inv_count = 0
while i <= mid and j <= right:
if arr[i] <= arr[j]:
temp_arr[k] = arr[i]
k += 1
i += 1
else:
temp_arr[k] = arr[j]
inv_count += (mid - i + 1)
k += 1
j += 1
# Copy the remaining elements of left subarray into temporary array
while i <= mid:
temp_arr[k] = arr[i]
k += 1
i += 1
# Copy the remaining elements of right subarray into temporary array
while j <= right:
temp_arr[k] = arr[j]
k += 1
j += 1
# Copy the sorted subarray into Original array
for loop_var in range(left, right + 1):
arr[loop_var] = temp_arr[loop_var]
return inv_count
if __name__ == '__main__':
arr = [1, 20, 6, 4, 5]
# arr = [8, 4, 2, 1]
n = len(arr)
result = mergeSort(arr, n)
print("Number of inversions are", result)
總結(jié)
??本文主要介紹了數(shù)組排序中的歸并排序思想及其在數(shù)組逆序?qū)χ械膽?yīng)用。
??歡迎大家訪問我的CSDN博客：https://blog.csdn.net/jclian91，后續(xù)我的文章將全部在上面展示，個人的微信公眾號將另作他用，屆時將不會在該公眾號上發(fā)布技術(shù)文章。
參考網(wǎng)址：
合并兩個有序數(shù)組: https://leetcode.cn/problems/merge-sorted-array/description/
劍指 Offer 51. 數(shù)組中的逆序?qū)? https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/
Merge Sort Algorithm: https://www.geeksforgeeks.org/merge-sort/
Inversion count in Array using Merge Sort: https://www.geeksforgeeks.org/inversion-count-in-array-using-merge-sort/
Merge Sort Algorithm: https://www.programiz.com/dsa/merge-sort