hangscer

scala写算法-insertSort

2017/02/15

scala写算法-insertSort

简单的排序算法之一插入排序,用较为函数式风格整理思路并实现:
insertSort由N-1趟(pass)排序组成。对于P=1趟到P=N-1趟,插入排序保证从为位置0到位置P上的元素为已排序(基于这样的事实:位置0到位置P-1上的元素是已排序)。

1
2
3
4
5
6
7
8
9
10
def insert(x:Int,list:List[Int]):List[Int]=list match{
case Nil=>List(x)
case ::(h,t) if(x<=h) =>List(x)++list
case ::(h,t) if(x>h) =>List(h)++insert(x,t)
}
def insertSort(list:List[Int]):List[Int]=list match{
case Nil=>Nil
case ::(h,t)=>insert(h,insertSort(t))
}
insertSort(List(23,23,321,123,123,122,323,213))