归并排序基于分治,利用归并来实现排序，其基本思想是：
如果一个数组有n个数据，则可以把这个数组看作n个有序的子序列，每个子序列的长度为1，然后两两归并，就能得到[n/2]个长度为2（或者1，落单的)的字序列，再不断地两两归并，直到得到一个长度为n的有序数组。
核心代码:
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 { // 左边数组还有未比较的数字
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]
}
}
测试代码:
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)")
