欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Scala实现冒泡排序、归并排序和快速排序的示例代码

程序员文章站 2024-02-14 15:09:10
1、冒泡排序 def sort(list: list[int]): list[int] = list match { case list() => l...

1、冒泡排序

def sort(list: list[int]): list[int] = list match {
  case list() => list()
  case head :: tail => compute(head, sort(tail))
 }

 def compute(data: int, dataset: list[int]): list[int] = dataset match {
  case list() => list(data)
  case head :: tail => if (data <= head) data :: dataset else head :: compute(data, tail)
 }

def main(args: array[string]) {
  val list = list(3, 12, 43, 23, 7, 1, 2, 0)
  println(sort(list))
 }

2、归并排序

def mergedsort[t](less: (t, t) => boolean)(list: list[t]): list[t] = {

  def merged(xlist: list[t], ylist: list[t]): list[t] = {
   (xlist, ylist) match {
    case (nil, _) => ylist
    case (_, nil) => xlist
    case (x :: xtail, y :: ytail) => {
     if (less(x, y)) x :: merged(xtail, ylist)
     else
      y :: merged(xlist, ytail)
    }
   }
  }

  val n = list.length / 2
  if (n == 0) list
  else {
   val (x, y) = list splitat n
   merged(mergedsort(less)(x), mergedsort(less)(y))
  }
 }

def main(args: array[string]) {
  val list = list(3, 12, 43, 23, 7, 1, 2, 0)
  println(mergedsort((x: int, y: int) => x < y)(list))
 }

3、快速排序

 def quicksort(list: list[int]): list[int] = {
  list match {
   case nil => nil
   case list() => list()
   case head :: tail =>
    val (left, right) = tail.partition(_ < head)
    quicksort(left) ::: head :: quicksort(right)
  }
 }

def main(args: array[string]) {
  val list = list(3, 12, 43, 23, 7, 1, 2, 0)
  println(quicksort(list))
 }

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。