這次我們介紹一下歸并排序
一.歸并排序
歸并排序很好的體現(xiàn)了分治法的應(yīng)用谦炬，排序的大致思路如下：
- 將數(shù)組切片為相同長度的兩部分鞋囊，一個(gè)是 nums[0...LEN/2] 另一個(gè)是 nums[LEN/2+1...LEN]
- 遞歸的對(duì)兩個(gè)部分進(jìn)行相同的切片操作，直到數(shù)組長度為1
- 對(duì)已經(jīng)排好序的兩個(gè)切片進(jìn)行合并操作
簡單解釋一下上述思路，由于 1 的操作尘分，我們已經(jīng)將原數(shù)組切片為兩個(gè)子數(shù)組，通過遞歸使用歸并排序方法童番，子數(shù)組均已排序完成崩瓤，我們接下來只需要將兩個(gè)已經(jīng)排好序的子數(shù)組進(jìn)行合并即可
func merge_sort(start int, end int, nums string) string {
// 如何 start == end，也就是 nums 長度為1们衙，直接返回該元素
// 我們可以認(rèn)為長度為1的數(shù)組是已經(jīng)排序好了的
if start == end {
return string(nums[start])
}
// 劃分兩個(gè)子數(shù)組
mid := (start + end) / 2
// 將低位數(shù)組排序
str1 := merge_sort(start, mid, nums)
// 將高位數(shù)組排序
str2 := merge_sort(mid+1, end, nums)
// 將兩個(gè)有序數(shù)組合并
return merge(str1, str2)
}
func merge(str1 string, str2 string) string {
newString := ""
i := 0
j := 0
for i < len(str1) && j < len(str2) {
if str1[i] < str2[j] {
newString += string(str1[i])
i++
} else {
newString += string(str2[j])
j++
}
}
if i == len(str1) {
newString += string(str2[j:])
}
if j == len(str2) {
newString += string(str1[i:])
}
return newString
}
初次使用遞歸钾怔，會(huì)對(duì)遞歸的過程感到疑惑
我們可以追溯一下整個(gè)排序的過程
整個(gè) nums長度為16，劃分為兩個(gè)數(shù)組 0~7和 8~15蒙挑。
我們繼續(xù)劃分宗侦，將 0~7劃分為 0~3和 4~7。 將 0~3繼續(xù)劃分為 0~1 和 2~3
如果我們繼續(xù)劃分忆蚀，則最后的數(shù)組被劃分為 0和 1
根據(jù)我們的代碼和思路矾利，此時(shí)直接返回單個(gè)元素
接著，我們合并兩個(gè)單元素馋袜，也就是排序了的 M和 E男旗，將其合并為 E和 M
同理，我們可以排序 R和 G欣鳖，將其合并為 G和 R
接著察皇，我們將 EM和GR進(jìn)行合并，合并為 EGMR泽台。此時(shí) 0~3的過程已經(jīng)排序完成
回顧整個(gè)排序過程让网，我們將整個(gè)數(shù)組細(xì)分為一個(gè)一個(gè)的數(shù)字，然后兩兩之間進(jìn)行合并师痕，然后繼續(xù)往上合并溃睹，最后將整個(gè)數(shù)組合并。合并過程就是我們的排序過程
接下來我們探討一下歸并排序的時(shí)間復(fù)雜度和穩(wěn)定性
歸并排序的過程主要消耗在將兩個(gè)有序數(shù)組合并的過程上胰坟，整個(gè)歸并排序的時(shí)間復(fù)雜度為 O(nlgn)因篇，歸并排序本身也是穩(wěn)定的泞辐。
本次我們使用的是二路歸并，幾路歸并取決于我們劃分?jǐn)?shù)組的數(shù)量竞滓，在本次介紹中咐吼，我們每次都將數(shù)組劃分為兩個(gè)子數(shù)組，所以叫做二路歸并
參考文獻(xiàn)：
Dynamic Connectivity - 普林斯頓大學(xué) | Coursera
