Scala实现冒泡排序、归并排序和快速排序

柔情只为你懂 2022-05-18 07:18 217阅读 0赞

**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))
      }

转载自：[https://blog.csdn.net/qq1010885678/article/details/46755749][https_blog.csdn.net_qq1010885678_article_details_46755749]

[https_blog.csdn.net_qq1010885678_article_details_46755749]: https://blog.csdn.net/qq1010885678/article/details/46755749