归并排序：
- 将序列每相邻两个数字进行归并操作，形成 floor ( n/2
) 个序列，排序后每个序列包含两个元素 - 将上述序列再次归并，形成 floor ( n/4
)
个序列，每个序列包含四个元素 - 重复步骤2，直到所有元素排序完毕
MergeSort.swift如下：
//归并排序 从小到大排序
var a = [6, 5, 4, 3, 2, 1]
print("a is \(a)")
func merge( array:inout [Int], first:Int, mid:Int, last:Int){
print("")
print("merge called: array is \(array), first is \(first), mid is \(mid), last is \(last)")
var tempArray = Array<Int>()
var indexA = first
var indexB = mid
while indexA < mid && indexB < last {
if array[indexA] < array[indexB]{
tempArray.append(array[indexA])
print("append \(array[indexA]) to tempArray while indexA \(indexA) < mid \(mid) && indexB \(indexB) < last \(last) and array[indexA] \(array[indexA]) < array[indexB] \(array[indexB])")
indexA += 1
}else{
tempArray.append(array[indexB])
print("append \(array[indexB]) to tempArray while indexA \(indexA) < mid \(mid) && indexB \(indexB) < last \(last) and array[indexA] \(array[indexA]) >= array[indexB] \(array[indexB])")
indexB += 1
}
}
while indexA < mid {
tempArray.append(array[indexA])
print("append \(array[indexA]) to tempArray while indexA \(indexA) < mid \(mid) ")
indexA += 1
}
while indexB < last{
tempArray.append(array[indexB])
print("append \(array[indexB]) to tempArray while indexB \(indexB) < last \(last) ")
indexB += 1
}
print("tempArray is \(tempArray)")
var index = 0
for item in tempArray{
array[first + index] = item
index += 1
}
print("")
print("merge finished: array is \(array), first is \(first), mid is \(mid), last is \(last)")
print("")
}
func mergeSort(array:inout [Int], first:Int, last:Int){
if first+1 < last{
print("")
print("====== start mergeSort loop")
let mid = (first + last)/2
print("first is \(first), last is \(last), mid is \(mid), array is \(array)")
mergeSort(array: &array, first: first, last: mid)
mergeSort(array: &array, first: mid, last: last)
merge(array: &array, first: first, mid: mid, last: last)
print("array now is \(array)")
} else {
print("-- end mergeSort loop, now first is \(first), last is \(last), array is \(array)")
}
}
print("")
mergeSort(array:&a, first:0, last: a.count)
//merge(array:&a, first: 0, mid:3, last:a.count)
print("")
//排序完成
print("sorted a is \(a)")
Terminal运行swift MergeSort.swift可以看到：
a is [6, 5, 4, 3, 2, 1]
====== start mergeSort loop
first is 0, last is 6, mid is 3, array is [6, 5, 4, 3, 2, 1]
====== start mergeSort loop
first is 0, last is 3, mid is 1, array is [6, 5, 4, 3, 2, 1]
-- end mergeSort loop, now first is 0, last is 1, array is [6, 5, 4, 3, 2, 1]
====== start mergeSort loop
first is 1, last is 3, mid is 2, array is [6, 5, 4, 3, 2, 1]
-- end mergeSort loop, now first is 1, last is 2, array is [6, 5, 4, 3, 2, 1]
-- end mergeSort loop, now first is 2, last is 3, array is [6, 5, 4, 3, 2, 1]
merge called: array is [6, 5, 4, 3, 2, 1], first is 1, mid is 2, last is 3
append 4 to tempArray while indexA 1 < mid 2 && indexB 2 < last 3 and array[indexA] 5 >= array[indexB] 4
append 5 to tempArray while indexA 1 < mid 2
tempArray is [4, 5]
merge finished: array is [6, 4, 5, 3, 2, 1], first is 1, mid is 2, last is 3
array now is [6, 4, 5, 3, 2, 1]
merge called: array is [6, 4, 5, 3, 2, 1], first is 0, mid is 1, last is 3
append 4 to tempArray while indexA 0 < mid 1 && indexB 1 < last 3 and array[indexA] 6 >= array[indexB] 4
append 5 to tempArray while indexA 0 < mid 1 && indexB 2 < last 3 and array[indexA] 6 >= array[indexB] 5
append 6 to tempArray while indexA 0 < mid 1
tempArray is [4, 5, 6]
merge finished: array is [4, 5, 6, 3, 2, 1], first is 0, mid is 1, last is 3
array now is [4, 5, 6, 3, 2, 1]
====== start mergeSort loop
first is 3, last is 6, mid is 4, array is [4, 5, 6, 3, 2, 1]
-- end mergeSort loop, now first is 3, last is 4, array is [4, 5, 6, 3, 2, 1]
====== start mergeSort loop
first is 4, last is 6, mid is 5, array is [4, 5, 6, 3, 2, 1]
-- end mergeSort loop, now first is 4, last is 5, array is [4, 5, 6, 3, 2, 1]
-- end mergeSort loop, now first is 5, last is 6, array is [4, 5, 6, 3, 2, 1]
merge called: array is [4, 5, 6, 3, 2, 1], first is 4, mid is 5, last is 6
append 1 to tempArray while indexA 4 < mid 5 && indexB 5 < last 6 and array[indexA] 2 >= array[indexB] 1
append 2 to tempArray while indexA 4 < mid 5
tempArray is [1, 2]
merge finished: array is [4, 5, 6, 3, 1, 2], first is 4, mid is 5, last is 6
array now is [4, 5, 6, 3, 1, 2]
merge called: array is [4, 5, 6, 3, 1, 2], first is 3, mid is 4, last is 6
append 1 to tempArray while indexA 3 < mid 4 && indexB 4 < last 6 and array[indexA] 3 >= array[indexB] 1
append 2 to tempArray while indexA 3 < mid 4 && indexB 5 < last 6 and array[indexA] 3 >= array[indexB] 2
append 3 to tempArray while indexA 3 < mid 4
tempArray is [1, 2, 3]
merge finished: array is [4, 5, 6, 1, 2, 3], first is 3, mid is 4, last is 6
array now is [4, 5, 6, 1, 2, 3]
merge called: array is [4, 5, 6, 1, 2, 3], first is 0, mid is 3, last is 6
append 1 to tempArray while indexA 0 < mid 3 && indexB 3 < last 6 and array[indexA] 4 >= array[indexB] 1
append 2 to tempArray while indexA 0 < mid 3 && indexB 4 < last 6 and array[indexA] 4 >= array[indexB] 2
append 3 to tempArray while indexA 0 < mid 3 && indexB 5 < last 6 and array[indexA] 4 >= array[indexB] 3
append 4 to tempArray while indexA 0 < mid 3
append 5 to tempArray while indexA 1 < mid 3
append 6 to tempArray while indexA 2 < mid 3
tempArray is [1, 2, 3, 4, 5, 6]
merge finished: array is [1, 2, 3, 4, 5, 6], first is 0, mid is 3, last is 6
array now is [1, 2, 3, 4, 5, 6]
sorted a is [1, 2, 3, 4, 5, 6]
源码引用参考[http://panl.github.io/2015/12/10/Algorithm/]
资料引用[https://zh.wikipedia.org/wiki/归并排序#C.2B.2B]
