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