Java数据结构与算法2——简单排序

1.冒泡排序

2.1 基本思路

BubbleSort.java
对未排序的各元素从头到尾依次比较相邻的两个元素是否逆序(与欲排顺序相反),若逆序就交换这两元素,经过第一轮比较排序后便可把最大(或最小)的元素排好,然后再用同样的方法把剩下的元素逐个进行比较,就得到所要的顺序。

2.2 效率

比较和交换次数都为O(N的平方)

2.选择排序

2.1 基本思路

SelectSort.java
从所有元素中选择一个最小元素a[i]放在a[0](即让最小元素a[i]与 a[0]交换),作为第一轮;第二轮是从a[1]开始到最后的各个元素中选择一个最小元素,放在a[1]中;……依次类推。n个数要进行(n-1)轮

2.2 效率

交换次数减少到O(N),但是比较次数仍为O(N的平方)

3.插入法排序

3.1 基本思路

每拿到一个元素,都要将这个元素与所有它之前的元素遍历比较一遍,让符合排序顺序的元素挨个移动到当前范围内它最应该出现的位置。

3.2 效率

比较和交换次数都为O(N的平方),大致为N*(N-1)/4,所以这个算法比冒泡大致快一倍,比选择排序略快,尤其是部分数据已经局部有序的情况下,这个算法效率会更高

4.对象排序

对象排序其实还是比较对象里面的某个或某些属性值来进行排序

参考

最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 一、 单项选择题(共71题) 对n个元素的序列进行冒泡排序时,最少的比较次数是( )。A. n ...
    貝影阅读 9,502评论 0赞 10
  • 1)这本书为什么值得看: Python语言描述,如果学的Python用这本书学数据结构更合适 2016年出版,内容...
    孙怀阔阅读 13,066评论 0赞 15
  • 概述排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的...
    Luc_阅读 2,423评论 0赞 35
  • 8月份已经过去,这是第5个月做检视,现在从八大关注来检视自己: 一、成长 1.完成书籍阅读3本、参加读书会分享一次...
    静待花开_问兰阅读 349评论 1赞 1

友情链接更多精彩内容