hangscer

scala写算法-mergeSort

2017/02/15

归并排序以O(NlogN)最坏情况运行。
这个算法基本的操作是合并两个已排序的表,取两个输入数组A和B,一个输出数组C,以及三个计数器Aptr、Bptr和Cptr。如下:

比较1和2。1被加入C中,然后13和2比较:

2被添加C中,然后13和15比较:

13被加入C中,比较24和15,这样一直进行到26和17比较:




1
2
3
4
5
6
7
8
9
10
11
def merge(a:List[Int],b:List[Int]):List[Int]=(a,b) match {
case (Nil,_)=>b
case (_,Nil)=>a
case (::(a_h,a_t),::(b_h,b_t)) if(a_h<=b_h) => List(a_h)++merge(a_t,b)
case (::(a_h,a_t),::(b_h,b_t)) if(a_h>b_h) => List(b_h)++merge(a,b_t)
}
def mergeSort(list:List[Int]):List[Int]=list.splitAt(list.length/2) match {
case (Nil,_)=>list // length=1 (List(),List(1))
case (first,second)=>merge(mergeSort(first),mergeSort(second))
}
println(mergeSort(List(23,34,1,23,23,34,45,56,34,32,34,45)))