使用scala语言实现快排，算法的行数很少，但是想要理解，需要有一些前提条件，下面介绍了我理解的详细过程。

object quickSort { def main(args: Array[String]): Unit = { val intArray: Array[Int] = Array.fill(1000)(util.Random.nextInt(1000)) val list: List[Int] = intArray.toList val ints: List[Int] = quickSort(list) // 快排的结果打印 for (elem <- ints) { println(elem) } } /* todo 补充知识点1：partition方法是干什么的？ partition将使用给定的谓词函数分割列表。 如下所示，就是对List中的每一个元素跟列表的首元素进行比较，如果比首元素大则返回到一个列表中 如果比首元素小则放到另一个列表中，两个列表组合成一个元组。 scala> val numbers = List(5, 8, 3, 7, 10, 6, 4, 2, 9, 1) numbers: List[Int] = List(5, 8, 3, 7, 10, 6, 4, 2, 9, 1) scala> numbers.partition(_ > numbers.head) res8: (List[Int], List[Int]) = (List(8, 7, 10, 6, 9),List(5, 3, 4, 2, 1)) */ /* todo 补充知识点2：::与:::区别 :::运算符连接两个List类型的列表， ::该方法称为cons，意为构造，向列表的头部追加数据，会将::前面的数据当成一个元素追加到后面List的前面。 ::与:::通过下面的例子可以直观的感受到区别。 scala> "A"::"B"::Nil res0: List[String] = List(A, B) scala> "A"::"B"::Nil res1: List[String] = List(A, B) scala> res0 ::: res1 res2: List[String] = List(A, B, A, B) scala> res0 :: res1 res3: List[java.io.Serializable] = List(List(A, B), A, B) */ /** * 快排 * 时间复杂度:平均时间复杂度为O(nlogn) * 空间复杂度:O(logn)，因为递归栈空间的使用问题 */ def quickSort(list: List[Int]): List[Int] = list match { // Nil是一个空的List，定义为List[Nothing]。 case Nil => Nil // todo 下面的匹配的结果是 一个元素::其他的所有元素组合成的集合 case first :: others => // 因为列表中的元素是无序的，取第一个元素作为一个个体，这个元素称为first, // 其他的元素组合成others列表，others列表中的每一个元素 // 跟first相比较，小于first的元素放在一个列表left中，大于等于first的元素放到另一个列表right中。 // 切割后的两个列表组合成一个元组，todo 现在有一个元素的顺序可以确定，那就是first元素的位置，如下所示 // todo left列表中的每一个元素 < first <= right列表中的每一个元素 val (left, right) = others.partition(_ < first) // 对left，right列表，做quickSort递归操作，最后一定会出现所有元素是全局升序的。 quickSort(left) ::: first :: quickSort(right) } }