第二十章 Caché 算法与数据结构 归并排序
思想
归并排序通过不断的将原数组进行拆分(通常拆分成左右两项)，一直到剩下一项，然后分别将拆分的子数组进行合并，此时，两个子数组已经是排好序的，所以合并排序只需要进行一趟排序即可完成，所以此类排序需要两个步骤：
- 拆分原数组
- 利用递归，不断得寻找左子数组和右子数组，一直到数组的长度为一
- 合并子数组。因此此算法是经典的分治算法。
- 每次合并需要子数组A,B，并新创建一个临时数组C，同时需要三个计数器Actr，Bctr和Cctr，其中Actr和Bctr用来判断数组是否用完，如果用完，则将剩余的数组元素按顺序放入临时数组中。全部放完后，将临时数组中的已经排好顺序的元素更新到原数组中。
时间复杂度
归并排序的最坏时间复杂度和平均时间复杂度均为O(nlogn)
归并排序的应用
归并排序是所有流行的排序算法中比较次数最少的排序算法，在Java类库中的泛型排序就是使用的归并排序(因为泛型类的比较所消耗的时间占比更多),而对于Java类库中的基本类型排序则是使用的快速排序算法
算法描述
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
- 把长度为n的输入序列分成两个长度为n/2的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列。
image
完整示例
并归类
Class PHA.YX.Arithmetic.MergeSort Extends %RegisteredObject
{
Method mergeSort(array As PHA.YX.Arithmetic.Array)
{
s array = ..sort(array, 0, array.length() - 1)
q array
}
Method sort(array As PHA.YX.Arithmetic.Array, left As %Integer, right As %Integer)
{
#dim mid = (left + right) \ 2
q:(left >= right) array
s array = ..sort(array, left, mid)
s array = ..sort(array, mid + 1, right)
s array = ..merge(array, left, mid , right)
q array
}
Method merge(array As PHA.YX.Arithmetic.Array, left As %Integer, mid As %Integer, right As %Integer)
{
d array.output()
#dim Actr as %Integer = left
#dim Bctr as %Integer = mid + 1
#dim Cctr as %Integer = 0
#dim tmp As PHA.YX.Arithmetic.Array = ##class(PHA.YX.Arithmetic.Array).%New()
d tmp.init(right - left + 1)
while ((Actr <= mid) && (Bctr <= right)){
w "Actr:" _ Actr _ " mid：" _ mid _" Bctr:" _ Bctr _ " right：" _ right,!
if (array.get(Actr) <= array.get(Bctr)){
d tmp.set(Cctr, array.get(Actr))
s Cctr = Cctr +1
s Actr = Actr +1
}else{
d tmp.set(Cctr, array.get(Bctr))
s Cctr = Cctr +1
s Bctr = Bctr +1
}
}
while(Actr <= mid){
d tmp.set(Cctr, array.get(Actr))
s Cctr = Cctr +1
s Actr = Actr +1
}
while(Bctr <= right){
d tmp.set(Cctr, array.get(Bctr))
s Cctr = Cctr +1
s Bctr = Bctr +1
}
for i = 0 : 1 : tmp.length() - 1{
d array.set(left,tmp.get(i))
s left = left + 1
}
q array
}
}
调用
/// w ##class(PHA.YX.Arithmetic).MergeSort()
ClassMethod MergeSort()
{
#dim array as PHA.YX.Arithmetic.Array = ##class(PHA.YX.Arithmetic.Array).%New()
d array.init(8)
d array.insert(0,52)
d array.insert(1,63)
d array.insert(2,14)
d array.insert(3,59)
d array.insert(4,68)
d array.insert(5,35)
d array.insert(6,67)
d array.insert(7,99)
#dim sort as PHA.YX.Arithmetic.MergeSort = ##class(PHA.YX.Arithmetic.MergeSort).%New()
s array = sort.mergeSort(array)
d array.output()
q ""
}
输出
DHC-APP> w ##class(PHA.YX.Arithmetic).MergeSort()
52
63
14
59
68
35
67
99
Actr:0 mid：0 Bctr:1 right：1
52
63
14
59
68
35
67
99
Actr:2 mid：2 Bctr:3 right：3
52
63
14
59
68
35
67
99
Actr:0 mid：1 Bctr:2 right：3
Actr:0 mid：1 Bctr:3 right：3
Actr:1 mid：1 Bctr:3 right：3
14
52
59
63
68
35
67
99
Actr:4 mid：4 Bctr:5 right：5
14
52
59
63
35
68
67
99
Actr:6 mid：6 Bctr:7 right：7
14
52
59
63
35
68
67
99
Actr:4 mid：5 Bctr:6 right：7
Actr:5 mid：5 Bctr:6 right：7
Actr:5 mid：5 Bctr:7 right：7
14
52
59
63
35
67
68
99
Actr:0 mid：3 Bctr:4 right：7
Actr:1 mid：3 Bctr:4 right：7
Actr:1 mid：3 Bctr:5 right：7
Actr:2 mid：3 Bctr:5 right：7
Actr:3 mid：3 Bctr:5 right：7
14
35
52
59
63
67
68
99
