Scala实现排序算法

超、凢脫俗 2024-04-18 08:29 32阅读 0赞

# 1.冒泡排序 #

object BubbleSort {
    /**
        * 冒泡排序
        * 时间复杂度:平均时间复杂度为O(n^2)
        * 空间复杂度:O(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.快速排序 #

object QuickSort {
      /**
        * 快排
        * 时间复杂度:平均时间复杂度为O(nlogn)
        * 空间复杂度:O(logn)，因为递归栈空间的使用问题
        */
      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]): Unit = {
        val list = quickSort(List[Int](5,1,3,2,6,4,8,7,9))
        println(list)
      }
    }

# 3.归并排序 #

/**
        * 归并排序
        * 时间复杂度:O(nlogn)
        * 空间复杂度:O(n)
        */
      def merge(left: List[Int], right: List[Int]): List[Int] = (left, right) match {
        case (Nil, _) => right
        case (_, Nil) => left
        case (x :: xTail, y :: yTail) =>
          if (x <= y) x :: merge(xTail, right)
          else y :: merge(left, yTail)
      }

# 4.二分查找 #

/**
        * 二分查找 时间复杂度O(log2n);空间复杂度O(1)
        */
    
      def binarySearch(arr: Array[Int], left: Int, right: Int, findVal: Int): Int = {
        if (left > right) {
          //递归退出条件，找不到，返回-1
          -1
        }
    
        val midIndex = (left + right) / 2
    
        if (findVal < arr(midIndex)) {
          //向左递归查找
          binarySearch(arr, left, midIndex, findVal)
        } else if (findVal > arr(midIndex)) {
          //向右递归查找
          binarySearch(arr, midIndex, right, findVal)
        } else {
          //查找到，返回下标
          midIndex
        }
      }