- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章Java排序实现的心得分享由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.
1.概述 排序和查找是程序设计里的两类非常基本的问题,而现在也存在很多经典的算法用于解决这两类问题,本文主要对java中排序算法实现进行一个基本的探讨,希望能够起到抛砖引玉的作用。在此之前,首先问各位几个问题:你能写出一个正确的快排吗?快排在什么情况下真正的快?你的快排足够快吗?还可以进一步优化吗?带着这些问题,我们来看看jre7中快排是如何实现的吧。 Jre7中排序的实现类是DualPivotQuickSort.java,相比jre6有一些改变,主要发生在两个地方,一个是insertion sort的实现上,另一个是QuickSort实现中pivot从一个变成了两个。我们以int型的数组为例,该类中有个排序实现的核心方法,该方法的原型为 。
。
。
参数a为需要排序的数组,left代表需要排序的数组区间中最左边元素的索引,right代表区间中最右边元素的索引,leftmost代表该区间是否是数组中最左边的区间。举个例子: 数组:[2, 4, 8, 5, 6, 3, 0, -3, 9]可以分成三个区间(2, 4, 8){5, 6}<3, 0, -3, 9> 对于()区间,left=0, right=2, leftmost=true 对于 {}区间, left=3, right=4, leftmost=false,同理可得<>区间的相应参数 当区间长度小于47时,该方法会采用插入排序;否则采用快速排序.
2. 插入排序实现 当leftmost为true时,它会采用传统的插入排序(traditional insertion sort),代码也较简单,其过程类似打牌时抓牌插牌:
。
传统插入排序代码 当leftmost为false时,它采用一种新型的插入排序(pair insertion sort),改进之处在于每次遍历前面已排好序的数组需要插入两个元素,而传统插入排序在遍历过程中只需要为一个元素找到合适的位置插入。对于插入排序来讲,其关键在于为待插入元素找到合适的插入位置,为了找到这个位置,需要遍历之前已经排好序的子数组,所以对于插入排序来讲,整个排序过程中其遍历的元素个数决定了它的性能。很显然,每次遍历插入两个元素可以减少排序过程中遍历的元素个数,其实现代码如下:
。
现在有个问题:为什么最左边的区间采用传统插入排序,其他的采用成对插入排序呢?加入用上述成对插入排序代码替换传统插入排序代码,会出现什么问题呢?期待大家自己来回答。。。 3. 快速排序实现 Jre7中对快速排序也做了改进,传统的快速排序是选取一个pivot(jre6种选取pivot的方法是挑选出数组最左边,中间和最右边位置的元素,将其中数值大小排在中间的元素作为pivot),然后分别从两端向中间遍历,把左边遍历过程中遇到的大于pivot的值和右边遍历中遇到的小于等于pivot的值进行交换,当遍历相遇后,插入pivot的值;这样就使得pivot左边的值均小于或等于pivot,pivot右边的值大于pivot;接下来再采用递归的方式对左边和右边分别进行排序。 通过上述分析,我们可以看到:插入排序的每一步是使数组的一个子区间绝对有序,而每一次循环的本质是使这个子区间不断扩大,所以我们可以看到其优化的方向是使每次循环遍历尽可能的使子区间扩大的速度变快,所以上面把每次遍历插入一个元素优化成每次插入两个元素。当然肯定有人会问,那为什么不把这个数字变得更大一点呢?比如每次遍历插入5个,10个。。。很显然,这样是不行,它的一个极端情况就是每次遍历插入n个(n为数组长度)。。。至于为什么,大家自己回答吧。 对于快速排序来讲,其每一次递归所做的是使需要排序的子区间变得更加有序,而不是绝对有序;所以对于快速排序来说,其性能决定于每次递归操作使待排序子区间变得有序的程度,另一个决定因素当然就是递归次数。快速排序使子区间变得相对有序的关键是pivot,所以我们优化的方向也应该在于pivot,那就增加pivot的个数吧,而且我们可以发现,增加pivot的个数,对递归次数并不会有太大影响,有时甚至可以使递归次数减少。和insert sort类似的问题就是,pivot增加为几个呢?很显然,pivot的值也不能太大;记住,任何优化都是有代价的,而增加pivot的代价就隐藏在每次交换元素的位置过程中。关子貌似卖的有点大了。。。下面我们就来看看pivot的值为2时,快速排序是如何实现的吧。其实现过程其实也不难理解: 1. 首先选取两个pivot,pivot的选取方式是将数组分成近视等长的六段,而这六段其实是被5个元素分开的,将这5个元素从小到大排序,取出第2个和第4个,分别作为pivot1和pivot2; 2. Pivot选取完之后,分别从左右两端向中间遍历,左边遍历停止的条件是遇到一个大于等于pivot1的值,并把那个位置标记为less;右边遍历的停止条件是遇到一个小于等于pivot2的值,并把那个位置标记为great 3. 然后从less位置向后遍历,遍历的位置用k表示,会遇到以下几种情况: a. k位置的值比pivot1小,那就交换k位置和less位置的值,并是less的值加1;这样就使得less位置左边的值都小于pivot1,而less位置和k位置之间的值大于等于pivot1 b. k位置的值大于pivot2,那就从great位置向左遍历,遍历停止条件是遇到一个小于等于pivot2的值,假如这个值小于pivot1,就把这个值写到less位置,把less位置的值写道k位置,把k位置的值写道great位置,最后less++,great--;加入这个值大于等于pivot1,就交换k位置和great位置,之后great— 4. 完成上述过程之后,带排序的子区间就被分成了三段(<pivot1, pivot1<=&&<=pivot2,>pivot2),最后分别对这三段采用递归就行了.
。
Jre7中对排序实现的核心内容就如上所述,具体细节可参见相应类中的代码,如发现错误或不妥之处,望指正.
最后此篇关于Java排序实现的心得分享的文章就讲到这里了,如果你想了解更多关于Java排序实现的心得分享的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
直接上代码,可以写在公共文件common和继承的基础类中,方便调用 ?
1、php服务端环境搭建 1.php 服务端环境 安装套件 xampp(apach+mysql+php解释器) f:\mydoc文件(重要)\dl_学习\download重要资源\apache
如下所示: Eclipse快捷键 Ctrl+1 快速修复 Ctrl+D: 删除当前行 Ctrl+Alt+↓ 复制当前行到下一行(复制增加) Ctrl+Alt+↑ 复制当前行到上一行(复制增加)
第一步:conn.PHP文件,用于连接数据库并定义接口格式,代码如下: php" id="highlighter_808731">
本篇文章整理了几道Linux下C语言的经典面试题,相信对大家更好的理解Linux下的C语言会有很大的帮助,欢迎大家探讨指正。 1、如果在Linux下使用GCC编译器执行下列程序,输出结果是什么?
安装完最新的Boost库 官方说明中有一句话: Finally, $ ./b2 install will leave Boost binaries in the lib/ subdirecto
为了梳理前面学习的《spring整合mybatis(maven+mysql)一》与《spring整合mybatis(maven+mysql)二》中的内容,准备做一个完整的示例完成一个简单的图书管理功
网站内容质量仅仅是页面综合得分里面的一项.不管算法如何改变调整,搜索引擎都不会丢弃网站页面的综合得分。 一般情况下我们把页面的综合得分为8个点: 1、标题的设置 (标题的设置要有独特性)
最近事情很忙,一个新项目赶着出来,但是很多功能都要重新做,一直在编写代码、debug。今天因为一个新程序要使用fragment来做,虽然以前也使用过fragment,不过没有仔细研究,今天顺道写篇文
Android资源命名规范 最近几个月,大量涉及android资源的相关工作。对于复杂的应用而言,资源命名的规范很有必要。除了开发人员之外,UI设计人员(或者切图相关人员)也需要对资源使用的位置非常
以前一直使用Hibernate,基本上没用过Mybatis,工作中需要做映射关系,简单的了解下Mybatis的映射。 两者相差不多都支持一对一,一对多,多对多,本章简单介绍一对一的使用以及注意点。
如下所示: ? 1
如果想在自定义的View上面显示Button 等View组件需要完成如下任务 1.在自定义View的类中覆盖父类的构造(注意是2个参数的) 复制代码 代码如下: publ
实现功能:实现表格tr拖动,并保存因为拖动改变的等级. jsp代码 ?
代码:测试类 java" id="highlighter_819000"> ?
红黑树是一种二叉平衡查找树,每个结点上有一个存储位来表示结点的颜色,可以是red或black。 红黑树具有以下性质: (1) 每个结点是红色或是黑色 (2) 根结点是黑色的 (3) 如果一个
废话不多说,直接上代码 ? 1
码代码时,有时候需要根据比较大小分别赋值: ? 1
实际项目开发中,我们经常会用一些版本控制器来托管自己的代码,今天就来总结下Git的相关用法,废话不多说,直接开写。 目的:通过Git管理github托管项目代码 1、下载安装Git 1、下载
直接上代码: 复制代码 代码如下: //验证码类 class ValidateCode { private $charset = 'abcdefghkmnprstuvwxyzABC
我是一名优秀的程序员,十分优秀!