首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >一个有趣的函数式插入排序实现

一个有趣的函数式插入排序实现

作者头像
哒呵呵
发布2018-08-06 11:32:46
2630
发布2018-08-06 11:32:46
举报
文章被收录于专栏:鸿的学习笔记鸿的学习笔记

分享一个有趣的函数式的插入排序实现方式,它利用Scala的模式匹配和列表的操作,通过递归的方式给列表排序,大概流程是有一个列表x::xs,先对xs排序。再将x插入到正确的位置。

def isort(xs:List[Int]):List[Int] = xs match {
    case List()  => List()
    case x :: xs1 => insert(x, isort(xs1))
  }

def insert(x:Int, xs:List[Int]):List[Int] = xs match {
    case List() => List(x)
    case y :: ys => if (x <= y) x :: xs
                     else y :: insert(x,ys)
  }

产生的效果就是

scala> isort(List(34,53,53,7,35,1))
res8: List[Int] = List(1, 7, 34, 35, 53, 53)

然后把这两个函数拆解,看看是怎么排序的,先对insert函数稍作改造:

  def insert(x:Int, xs:List[Int]):List[Int] = xs match {
    case List() => List(x)
    case y :: ys => if (x <= y) {
                         println(s"x:$x")
                         println(s"xs:$xs")
                         x :: xs}
                     else
                     {
                       println(s"x:$x")
                       println(s"xs:$xs")
                       y :: insert(x,ys)}
                      }

输出结果为:

scala> isort(List(34,53,53,7,35,1))
x:35
xs:List(1)
x:7
xs:List(1, 35)
x:7
xs:List(35)
x:53
xs:List(1, 7, 35)
x:53
xs:List(7, 35)
x:53
xs:List(35)
x:53
xs:List(1, 7, 35, 53)
x:53
xs:List(7, 35, 53)
x:53
xs:List(35, 53)
x:53
xs:List(53)
x:34
xs:List(1, 7, 35, 53, 53)
x:34
xs:List(7, 35, 53, 53)
x:34
xs:List(35, 53, 53)
res0: List[Int] = List(1, 7, 34, 35, 53, 53)

这个的函数流程可以这么理解,列表会从最后一个元素开始往上比较排序,每一的比较都是采用需要比较的元素通过递归的方式与已有列表的元素比较放入到一个合适的位置,再和头元素拼接在一起。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2018-04-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 鸿的学习笔记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档