继续学习《算法》，这次依然是排序算法的学习：归并排序。
在这次的学习中本人遇到了一些问题，主要就是归并排序的实现较前面的选择排序和插入排序较为复杂。最主要的原因还是在《算法》中代码都是java实现的，我在用swift写的时候不仔细出了点错误。于是百度了一些C++的代码，再用C++代码实现了排序的过程之后才理解了整个排序的过程。
还是先上代码吧，将代码运行起来逐步的观察排序的过程更有利于理解；
注 本文中提及的‘分解’并不是真正的将数组变为一个个的小数组，而是根据角标当成小数组来分段的处理。
注 本文中标示数组起始和结束位置的lo和hi为左右都包含，并非常见的左包含右不包含，代码注释中已提及。
首先提供一个全局的临时数组 aux 用于归并操作；
num 为了方便测试不同长度的数组排序
let num = 10
var aux = [Int](repeating:0 , count:num)
归并的方法:
/// 归并
///
/// - Parameters:
/// - a: 需要归并的数组
/// - lo: 归并的起始位置(包含)
/// - mid: 归并的中间位置(视为包含在左边部分)
/// - hi: 归并的终点位置(包含)
func merge(a : inout[Int], lo : Int, mid : Int, hi : Int) -> Void {
/**
i、为左边数组的起始位置,
j、为右边数组的起始位置;
*/
var i = lo,j = mid+1
/**
将数组 a 中需要归并的元素复制到 数组 aux 的对应位置；
*/
for k in lo...hi {
aux[k] = a[k]
}
/**
归并 操作
*/
for k in lo...hi {
/**
当 i > mid 时，说明左边的数组已经全部归并完成，
这时只需要将 右边剩余的部分归并到 a 数组中即可；
*/
if i>mid {
a[k] = aux[j]
j = j+1
/**
当 j>hi 时，说明右边的数组已经全部归并完成，
这时只需要将左边剩余的部分归并到 a 数组中即可；
*/
}else if j>hi {
a[k] = aux[i]
i = i+1
/**
比较 左右两边数组元素的大小，
将较小的元素先归并到数组a中，并将对应的i或者j加一；
* 这里是归并过程完成排序的部分。
* 归并排序始终将数组一分为二，最终将分成只有单个元素的小数组。
* 那么只需要将较小的放在放在前面即可完成两个小数组的排序。
* 两个小数组在归并时，如果其中一个全部归并完成，那么剩余的数组要么是只有一个元素且较大，
要么是已经完成排序且全部大于已经完成的部分。
*/
}else if aux[i]<aux[j] {
a[k] = aux[i]
i = i+1
}else {
a[k] = aux[j]
j = j+1
}
}
}
排序的方法:
/// 归并排序方法
///
/// - Parameters:
/// - a: 排序的数组
/// - lo: 起始位置（包含）
/// - hi: 结束位置（包含）
func sort(a:inout[Int], lo:Int, hi:Int) -> Void {
///当lo大于或者等于hi时说明数组不能再分了。
if lo>=hi {
return
}
///mid为归并排序数组的中间位置，是分割数组的位置
///mid被认为包含在左边数组里
let mid = lo+(hi-lo)/2
/**
递归调用，将数组 a 逐步的不解为只有一个元素的数组（并非创建新的数组，只是根据小标按照单个数组的方式处理）
*/
sort(a: &a, lo: lo, hi: mid)
sort(a: &a, lo: mid+1, hi: hi)
/**
将数组归并 排序
*/
merge(a: &a, lo: lo, mid: mid, hi: hi)
}
现在将代码运行起来吧。
var a = [Int]()
for i in 0..<num {
// let c = arc4random_uniform(UInt32(num))
// a.append(Int(c))
a.append(num-i-1)
}
print("初始数组-->",a)
sort(a: &a, lo: 0, hi: a.count-1)
print("排序完成",a)
最开始为了方便查看排序的过程，并未使用无序的数组，而是使用了一个逆序的数组。附上C++运行的归并排序过程方便理解：
归并排序过程
lo=0,mid=0,hi=1
初始9，8
初始9，8 为第一次归并操作时归并的两个数组，左边为[9] 右边为[8]。在归并过程中将较小的元素放在靠前的位置完成归并时即成为
8 9
之后：
lo=0,mid=1,hi=2
初始8 9 ,7
第二次归并操作，完成归并且有序的[8,9]为左边的数组 ，[7] 为右边的数组。在归并时逐个比较两数组元素的大小 7<8 ，即将7放在靠前的位置。之后右边数组完成归并，将左边的数组[8,9]归并在后面位置。即为：
7 8 9
通过观察我们发现 排序过程中 归并排序会将整个数组分成只含有一个元素的数组，然后两两进行归并操作。之后再进一步归并直至完成整个过程。
在这个归并过程中因为始终将较小的元素放在靠前的位置，所以在完成归并时数组就变成了有序的。
《算�法》归并排序子数组依赖树
归并排序会将整个数组全部递归的"分解"为小数组进行排序，当数组较为庞大时归并操作就会变的过于频繁。因此在处理较大的数据时可以在数组被"分解"为较小的数组时使用插入排序，这样可以避免过于频繁的归并操作。
/// 对数组的部分元素插入排序
///
/// - Parameters:
/// - a: 排序的数组
/// - lo: 起始位置（包含）
/// - hi: 结束位置（包含）
func insertSort(a:inout[Int], lo:Int, hi:Int) -> Void {
for i in lo+1...hi {
for j in lo..<i {
let num = i-j
if a[num]<a[num-1] {
let temp = a[num]
a[num] = a[num-1]
a[num - 1] = temp
}else {
break
}
}
}
}
排序的方法修改为:
/// 归并排序方法
///
/// - Parameters:
/// - a: 排序的数组
/// - lo: 起始位置（包含）
/// - hi: 结束位置（包含）
func sort(a:inout[Int], lo:Int, hi:Int) -> Void {
///当lo大于或者等于hi时说明数组不能再分了。
if lo>=hi {
return
}
let len = 10000
if hi-lo<len {
insertSort(a: &a, lo: lo, hi: hi)
return
}
///mid为归并排序数组的中间位置，是分割数组的位置
///mid被认为包含在左边数组里
let mid = lo+(hi-lo)/2
/**
递归调用，将数组 a 逐步的不解为只有一个元素的数组（并非创建新的数组，只是根据小标按照单个数组的方式处理）
*/
sort(a: &a, lo: lo, hi: mid)
sort(a: &a, lo: mid+1, hi: hi)
/**
将数组归并 排序
*/
merge(a: &a, lo: lo, mid: mid, hi: hi)
}
sort方法中 len 即表示元素少于多少则使用插入排序，这个越大则需要做的归并操作越少，越小则归并操作越多。但是这个数字也不是越大越好，随着 len 的增大插入算法处理庞大数据的性能下降。因此在使用这种方式的归并排序需要选择合适 len 的大小。
To be continued
网友评论