千锋教育-做有情怀、有良心、有品质的职业教育机构

手机站
千锋教育

千锋学习站 | 随时随地免费学

千锋教育

扫一扫进入千锋手机站

领取全套视频
千锋教育

关注千锋学习站小程序
随时随地免费学习课程

首页 视频教程 培训课程 师资团队 技术干货 常见问题 面试题 职场就业 零基础学大数据 行业资讯
【热点话题】 大数据技术干货 大数据学习教程 大数据学习笔记 大数据面试题 大数据培训问答 大数据培训机构哪些好 大数据职场就业
当前位置:大数据培训  >  大数据学习笔记  >  手写算法-四大排序

手写算法-四大排序

来源:千锋教育
发布人:qyf
时间: 2022-12-08 16:04:40 1670486680

手写算法-四大排序

  速度上:改良的归并排序算法是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)

  }

声明:本站稿件版权均属千锋教育所有,未经许可不得擅自转载。

猜你喜欢LIKE

最新文章NEW

相关推荐HOT

更多>>