本文只是自己的筆記砚著，并不具備過多的指導(dǎo)意義。
為了理解很多都使用了遞歸茅撞，而不是自己通過while進(jìn)行壓棧處理帆卓。
代碼的初衷是便于理解，網(wǎng)上大神優(yōu)化過的代碼很多米丘，也不建議在項(xiàng)目中copy本文代碼剑令。
目錄
-
歸并排序
- 如何合并兩個(gè)有序數(shù)組
- 使兩端分別有序
- 最外側(cè)還有一個(gè)入口方法
- 圖解排序過程
-
遞歸時(shí)間復(fù)雜度的估算
- master公式
歸并排序
眾所周知，分治策略中使用遞歸來求解問題分為三步走拄查，分別為分解吁津、解決和合并。
所以歸并排序中心思想是通過二分的方式堕扶，將一個(gè)段數(shù)組拆分成左右兩端碍脏，然后進(jìn)行合并
-
如何合并兩個(gè)有序數(shù)組
通過將最小值依次外排的方式梭依，進(jìn)行合并
- 兩個(gè)指針
p1，p2指向兩個(gè)數(shù)組的首位置典尾，每次將較小的值外排進(jìn)輔助數(shù)組并且右移指針役拴。 - 當(dāng)一個(gè)
指針越界后，將另一個(gè)剩余的元素放入輔助數(shù)組钾埂。 - 最后的
輔助數(shù)組將是一個(gè)有序數(shù)組河闰。
/// 對(duì)一個(gè)數(shù)組的兩個(gè)有序分段進(jìn)行整合排序
///
/// - Parameters:
/// - arr: 數(shù)組
/// - left: 左側(cè)起點(diǎn)
/// - mid: 中心點(diǎn)，左側(cè)末尾
/// - right: 右側(cè)末尾
func merge(arr: inout [Int] ,left: Int ,mid: Int ,right:Int) {
var help : [Int] = [Int](repeating: 0, count: right-left+1) //輔助數(shù)組
var p1 = left//左側(cè)指針
var p2 = mid+1 //右側(cè)指針
var i = 0 //容器指針位置
while p1<=mid && p2<=right {
if arr[p1] <= arr[p2] {//左側(cè)指針位置小于等于右側(cè)指針位置
help[i] = arr[p1] //將左側(cè)指針位置放入輔助數(shù)組
p1 = p1+1 //左側(cè)指針右移
}else {//右側(cè)指針大于左側(cè)指針位置
help[i] = arr[p2] //將右側(cè)指針位置放入輔助數(shù)組
p2 = p2+1 //左側(cè)指針右移
}
i = i+1 //容器指針右移
}
//到這里褥紫，p1,p2之中已經(jīng)有一個(gè)指針越界了
//沒有越界的那個(gè)淤击，重復(fù)上面的操作寫入輔助數(shù)組
while p1<=mid {
help[i] = arr[p1]
p1 = p1+1
i = i+1
}
while p2<=right {
help[i] = arr[p2]
p2 = p2+1
i = i+1
}
//寫入完畢，用輔助數(shù)組替換進(jìn)原數(shù)組
i = 0
for index in left...right { //left,left+1...right-1,right
arr[index] = help[i]
i = i+1
}
}
之所以先說這個(gè)故源，是因?yàn)檫@個(gè)方法是核心方法，并且寫完滯后直接將可以測(cè)試汞贸。
測(cè)試通過之后绳军，再去測(cè)試下面的遞歸方法可以更加準(zhǔn)確的確定問題所在。
-
使兩端分別有序
通過遞歸的方式矢腻，將長(zhǎng)數(shù)組最終分解成有序的數(shù)組進(jìn)行排序處理门驾。
比如[4,2,6,1,9,7]
/// 在一個(gè)數(shù)組的某一段上進(jìn)行排序
///
/// - Parameters:
/// - arr: 數(shù)組
/// - left: 左側(cè)
/// - right: 右側(cè)
func mergeProcess(arr: inout [Int] ,left: Int ,right:Int) {
if left==right { //左右相等，說明這次要調(diào)整的只有一個(gè)數(shù)
return
}
let mid = (left+right)/2 //取得中心點(diǎn)位置
mergeProcess(arr: &arr, left: left, right: mid)//對(duì)左半邊進(jìn)行排序
mergeProcess(arr: &arr, left: mid+1, right: right)//對(duì)右半邊進(jìn)行排序
//此時(shí)左右兩側(cè)都已經(jīng)排序完成
merge(arr: &arr, left: left, mid: mid, right: right)//對(duì)左右兩側(cè)進(jìn)行合并排序
}
-
最外側(cè)還有一個(gè)入口方法
/// 歸并排序
///
/// - Parameter arr: 數(shù)組
func mergeSort(arr: inout [Int]) {
if arr.count<2 {
return
}
mergeProcess(arr: &arr, left: 0, right: arr.count-1)
}
時(shí)間復(fù)雜度O(N * logN)多柑，額外空間復(fù)雜度O(N)奶是。
-
圖解排序過程
網(wǎng)上還看到一個(gè)動(dòng)圖，結(jié)合上面的應(yīng)該更容易理解了竣灌。
這個(gè)過程中聂沙，不管數(shù)組多長(zhǎng)，最后都將被劃分成2個(gè)單位長(zhǎng)度的數(shù)組進(jìn)行排序初嘹。
然后向上依次合并并且排序及汉。
這也很好的體現(xiàn)出了分治或者遞歸的思想所在，將大樣本劃分成小樣本并依次解決屯烦。
遞歸時(shí)間復(fù)雜度的估算
只說一種普遍的通用情況
-
master公式
T(N) = A*T(N/B) + O(N^D)
當(dāng)量本量為N的情況下坷随，整個(gè)樣本被劃分成B樣本量，共執(zhí)行A次驻龟。
出去調(diào)用遞歸過程之外温眉，剩下的部分的時(shí)間復(fù)雜度O(N^D)
1) log(b,a) > d -> 復(fù)雜度為O(N^log(b,a))
2) log(b,a) = d -> 復(fù)雜度為O(N^d * logN)
3) log(b,a) < d -> 復(fù)雜度為O(N^d)
以歸并排序?yàn)槔?
func mergeProcess(arr: inout [Int] ,left: Int ,right:Int) {
if left==right { //左右相等，說明這次要調(diào)整的只有一個(gè)數(shù)
return
}
let mid = (left+right)/2 //取得中心點(diǎn)位置
mergeProcess(arr: &arr, left: left, right: mid)//T(N/2)
mergeProcess(arr: &arr, left: mid+1, right: right)//T(N/2)
merge(arr: &arr, left: left, mid: mid, right: right)//O(N)
}
有T(N) = T(N/2) + T(N/2) + O(N) = 2T(N/2) + O(N)
中A = 2,B=2,D=1
帶入master公式log(b,a) = 1,與d值相等翁狐。
于是歸并排序的時(shí)間復(fù)雜度為O(N * logN)类溢。
參考資料
【圖解數(shù)據(jù)結(jié)構(gòu)】 一組動(dòng)畫演示歸并排序
左神牛課網(wǎng)算法課
十大經(jīng)典排序算法（動(dòng)圖演示）
