import scala.util.Sorting

/**
 * ***** Scala 快速排序 quick sort *****
 *
 * 快速排序的思想是,假如有一个List存放整数,首先选取第一个数作为基准(pivot),将这个LIst分为如下三部分,
 * less pivot greater, 其中less和greater也是List, less是小于pivot的List,greater是大于pivot的List
 * 接下来对less和greater采用同样算法,递归调用方法
 *
 * 借用scala强大的表达能力和简洁的语法,实现快速排序只用了 5 行代码.
 * 但是这里的对比scala中自带的原生的快速排序,自己实现的的算法效率和原生的还是不具备可比性
 * 1000个随机生成正数排序,scala原生算法只用了 2 毫秒,而自己的要 46 毫秒,
 * 所以在实际项目中,还是要采用scala原生的算法
 * 这里只是记录自己对快速排序算法的理解
 *
 * P.S. scala的quickSort方法其实是调用java.util.DualPivotQuicksort中的方法来实现的
 *
 * --output
 * 自己实现快速排序,耗时=46 毫秒
 * scala 原生快速排序,耗时=2 毫秒
 *
 */
object QuickSort {
  def main(args: Array[String]): Unit = {
    val ints = Array.fill(1000)(util.Random.nextInt(1000))
    val list = ints.toList
    var start = System.currentTimeMillis()
    quickSort(list)
    var timingConsuming = System.currentTimeMillis() - start
    println(s"自己实现快速排序,耗时=${timingConsuming} 毫秒")

    start = System.currentTimeMillis()
    Sorting.quickSort(ints)
    timingConsuming = System.currentTimeMillis() - start
    println(s"scala 原生快速排序,耗时=${timingConsuming} 毫秒")
  }

  def quickSort(ls:List[Int]) :List[Int] = {
    ls match {
      case Nil => Nil
      case pivot :: tail => {
        val(less,greater) = tail.partition(_<pivot)
        quickSort(less) ::: pivot :: quickSort(greater)
      }
    }
  }
}

本文固定链接: https://www.jack-yin.com/coding/scala/2723.html | 边城网事