返回顶部

收藏

插入排序的尾递归写法

更多

[Scala]代码

@scala.annotation.tailrec
def _insertSort[T](x1: List[T], x2: List[T])(p: (T, T) => Boolean): List[T] = x2 match {
    case Nil => x1
    case x2_head :: x2_tail =>  
        val (x1_left, x1_right) = x1.partition( x => p(x, x2_head) )
        val x1_new = (x1_left ::: (x2_head :: x1_right))
        _insertSort(x1_new, x2_tail)(p)
}

def insertSort[T](xs: List[T])(p: (T, T) => Boolean) = xs match{
    case Nil => Nil
    case head :: tail => _insertSort(head :: Nil, tail)(p)
}

// 定义比较函数
val compare = (x1: Int, x2: Int) => x1 < x2;
//生成测试样本
val intList = List(3,4,2,1,8,7,6,3)
insertSort(intList)(compare)

标签:排序

收藏

0人收藏

支持

0

反对

0

发表评论