美文网首页
Arrays.sort()排序算法分析

Arrays.sort()排序算法分析

作者: 大头8086 | 来源:发表于2018-05-06 21:30 被阅读14次

Arrays.sort()根据入参类型选择以下排序算法

  • 基本类型数组使用快速排序
  • 对象数组使用归并排序

原因

  • 使用不同类型的排序算法主要是由于快速排序是不稳定的,而合并排序是稳定的。这里的稳定是指比较相等的数据在排序之后仍然按照排序之前的前后顺序排列。对于基本数据类型,稳定性没有意义,而对于对象类型,稳定性是比较重要的,因为对象相等的判断可能只是判断关键属性,最好保持相等对象的非关键属性的顺序与排序前一直;
  • 另外一个原因是由于合并排序相对而言比较次数比快速排序少,移动(对象引用的移动)次数比快速排序多,而对于对象来说,比较一般比移动耗时。

补充一点合并排序的时间复杂度是n*logn, 快速排序的平均时间复杂度也是n*logn,但是合并排序的需要额外的n个引用的空间。

相关文章

  • Arrays.sort()排序算法分析

    Arrays.sort()根据入参类型选择以下排序算法 基本类型数组使用快速排序 对象数组使用归并排序 原因 使用...

  • 浅析Collections.sort()和Arrays.sort

    Arrays.sort()和Collections.sort()都是java为我们提供的排序算法,它们的内部原理到...

  • 数据结构与算法第七讲 - 排序(上)

    对于排序算法,主要掌握内容如下: 排序算法的实现原理 手写出实现代码 评价及分析算法 本讲内容 如何分析一个排序算...

  • 2020-04-30-排序算法

    冒泡排序 直接选择排序 插入排序 快速排序 参考 算法学习笔记17-经典排序算法八大排序算法稳定性分析

  • 6基础算法之冒泡,插入,选择排序

    如何分析一个“排序算法”? 排序算法的执行效率 对于排序算法执行效率的分析,我们一般会从这几个方面来衡量: 最好情...

  • 排序算法

    常用排序算法总结(一)找出数组中出现次数最多的那个数——主元素问题 Arrays.sort() 对基本类型用快速排...

  • Arrays.sort()之双轴快排算法

    概述 我们在写代码时常常使用Arrays.sort()方法给数组排序,但是背后的实现算法是怎么样的呢,深入到这个方...

  • 剖析JDK8中Arrays.sort底层原理及其排序算法的选择

    写这篇文章的初衷,是想写篇Java和算法的实际应用,让算法不再玄乎,而Arrays.sort是很好的切入点,即分析...

  • 第4章 结构体

    1、排序 算法分析 用结构体存储,并进行排序 时间复杂度 Java 代码 2、成绩排序 算法分析 先对分数从小到大...

  • 基础算法(查找 , 排序)

    算法分析 渐进符号 - (O , Ω , θ) 查找算法 二分查找 - O(logn) 排序算法 直接插入排序 -...

网友评论

      本文标题:Arrays.sort()排序算法分析

      本文链接:https://www.haomeiwen.com/subject/lvhprftx.html