歸并排序基于分治,利用歸并來實(shí)現(xiàn)排序侍咱，其基本思想是：
如果一個(gè)數(shù)組有n個(gè)數(shù)據(jù)红选，則可以把這個(gè)數(shù)組看作n個(gè)有序的子序列弛饭，每個(gè)子序列的長(zhǎng)度為1冕末，然后兩兩歸并，就能得到[n/2]個(gè)長(zhǎng)度為2（或者1侣颂，落單的)的字序列档桃，再不斷地兩兩歸并，直到得到一個(gè)長(zhǎng)度為n的有序數(shù)組憔晒。
核心代碼:
func mergeSort(arr:inout [Int],low:Int,high:Int) {
if low >= high {
return
}
let mid = (low + high) / 2
mergeSort(arr: &arr, low: low, high: mid)
mergeSort(arr: &arr, low: mid + 1, high: high)
merge(arr: &arr, low: low, mid: mid, high: high)
}
func merge(arr:inout [Int],low:Int,mid:Int,high:Int) {
let count:Int = high - low + 1
var temp:[Int] = [Int].init(repeating: 0, count: count)
var i:Int = low // 左指針
var j:Int = mid + 1 // 右指針
var index:Int = 0
while i <= mid && j <= high {
if arr[i] < arr[j] {
temp[index] = arr[i]
i += 1
} else {
temp[index] = arr[j]
j += 1
}
index += 1
}
while i <= mid { // 左邊數(shù)組還有未比較的數(shù)字
temp[index] = arr[i]
i += 1
index += 1
}
while j <= high {
temp[index] = arr[j]
j += 1
index += 1
}
for m in 0..<count {
arr[low+m] = temp[m]
}
}
測(cè)試代碼:
let mergeSort:MergeSort = MergeSort()
var mergeSortData:[Int] = [1,10,2,4,3,9,9,5,6,8,7]
mergeSort.mergeSort(arr: &mergeSortData, low: 0, high:mergeSortData.count-1 )
print("FlyElephant-歸并排序---\(mergeSortData)")
