手写算法-四大排序
推荐
在线提问>>
速度上：改良的归并排序算法是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)
}
