速度上：改良的归并排序算法是n-nlogn，快速排序的时间复杂度是nlogn-n^2.冒泡和选择都是n^2.

　　稳定性：快速、选择都不稳定，冒泡和归并都稳定

　　空间上：冒泡和选择都是1.快速为logn，归并为n

　　/**

　　* 一个完整的快速排序的方法

　　* 可以传入任意类型的buffer对其排序后返回

　　* 可以传入一个比较器对自定义类型排序

　　*

　　* @author 孤星魅影

　　* @param buffer 任意类型的buffer

　　* @param isASC 是否正序排序

　　* @param ev 自定义比较器

　　* @return 返回一个快速排序后的buffer

　　*/

　　def quickSort[T: ClassTag](buffer: mutable.Buffer[T])(implicit isASC: Boolean = true, ev: T => Comparable[T]): mutable.Buffer[T] = {

　　//为null、为空、长度为1时都返回buffer

　　if (buffer == null || buffer.length <= 1)

　　return buffer

　　//1.将数组的第一个数head与后面所有的数进行比较，左边放比head小的数，右边放比head大的数(从小到大)

　　//2.递归执行拆分，直到数组只剩下1个

　　//3.按顺序将左、中、右三者拼接起来，完成排序

　　val (left, right) = buffer.tail.partition(t => {

　　if (isASC) t.compareTo(buffer.head) < 0

　　else t.compareTo(buffer.head) > 0

　　})

　　quickSort(left) += buffer.head ++= quickSort(right)

　　}

上一篇

是一个宽表好还是多个维表好？

下一篇

手写算法-懒汉式单例