学习了堆排序的思想,便试着用Java设计堆排序算法,如下即对应的堆排序方法,代码注释描述了堆排序的思想即堆排序与其他排序的不同之处:
/**
* 堆排序使用的是最大堆,即堆中的每个节点的值都不小于其子节点的值.
* 堆排序的思想:
* 1.构建最大堆;
* 2.从最大堆中移除根节点,也就是最大值;
* 3.将最后一个节点移至根节点的位置;
* 4.一直向下筛选这个节点,直至满足最大堆的条件为止;
* 5.重复以上操作即可从大到小移除所有节点,即实现了排序.
*
* 堆排序可以直接在原数组基础之上构建最大堆,无需额外的存储空间,构建最大堆的时间复杂度为O(n*log(n)).
* 堆排序移除最大节点的时间复杂度为O(1),但是筛选节点的时间复杂度为O(log(n)),因此排序的时间复杂度为O(n*log(n)).
*
* @param array
*/
public static void heapSorting(int[] array) {
final int[] a = array;
final int length = a.length;
int p, q, r, s;
/**
* 构建最大堆.
* 此处认为数组索引0~i-1已经是最大堆,a[i]为插入的新节点,因此需要进行向上筛选直至满足最大堆的条件.
* 向上筛选即如果当前节点大于其父节点,则交换当前节点与其父节点的值,然后对父节点重复这个操作.
* 通过复制取代交换,减少复制总数,将a[i]复制到临时变量,然后在筛选时只做向下复制操作即可,在退出时将临时变量的值复制到循环结束节点,
* 这样以n+2次复制操作代替3n次复制操作.如a->b->c->d->a按照箭头方向复制时可以a<->b,b<->c,c<->d,这样需要九次复制(包含临时变量),
* 也可以先将d的值赋给临时变量,然后c->d,b->c,a->b,最后将临时变量的值赋给a即可,这样减少了复制的次数.
*/
/*for(int i = 1; i < length; i++) {
r = a[i];
//向上筛选.
for(p = i; p > 0; a[p] = a[p = q]) {
q = (p - 1) >> 1;//用数组表示最大堆是节点的根节点即为(x-1)/2
if(a[q] >= r) break;
}
a[p] = r;
}*/
/**
* 构建最大堆.
* 此处采用n/2次向下筛选代替n次向上筛选来构造最大堆,只需对非叶子节点操作即可,即索引为0~n/2-1.
*/
for(s = (length >> 1) - 1; s >= 0; s--) {
r = a[s];
//向下筛选形成新的最大堆.
//用数组表示最大堆时节点的子节点即为2x+1与2x+2,这里取2x+2即只遍历左右子节点均存在的情况.
//这里也采用了如上机制减少了复制的次数.
for(p = s, q = (p << 1) + 2; q < length; a[p] = a[p = q], q = (p << 1) + 2) {
if(a[q - 1] > a[q]) q = q - 1;
if(a[q] <= r) break;
}
//此处添加if判断是因为可能有只存在左子节点的情况,上述for循环并不包括这种情况,因此需要特殊考虑.
if(--q < length && a[q] > r) a[p] = a[p = q];
a[p] = r;
}
/**
* 从最大堆中删除根节点并复制到数组中.
* 此处认为数组索引0~last是最大堆,last+1之后的为已经排好序的元素,从最大堆中删除根节点并与索引last所在元素交换,执行向下筛选形成新的最大堆,
* 即新的最大堆索引为0~last-1,last之后的为新的已经排好序的元素,重复进行删除操作即可完成排序(last为0).
*/
for(s = length - 1; s > 0; s--) {
//交换删除根节点.
r = a[s];
a[s] = a[0];
//向下筛选形成新的最大堆.
//用数组表示最大堆时节点的子节点即为2x+1与2x+2,这里取2x+2即只遍历左右子节点均存在的情况.
//这里也采用了如上机制减少了复制的次数.
for(p = 0, q = 2; q < s; a[p] = a[p = q], q = (p << 1) + 2) {
if(a[q - 1] > a[q]) q = q - 1;
if(a[q] <= r) break;
}
//此处添加if判断是因为可能有只存在左子节点的情况,上述for循环并不包括这种情况,因此需要特殊考虑. if(--q < s && a[q] > r) a[p] = a[p = q];
a[p] = r;
}
}
下面是堆排序与快速排序的性能对比
数据量 10e5 10e6 10e7
堆排序时间:
0.01158s 0.21217s 5.63784s
快速排序时间:
0.01143s 0.12764s 1.47240s
分享到:
相关推荐
C 排序 数据结构 链表 堆排序 希尔排序 快速排序 递归排序。详细解释了每个排序方法原理,并带有程序代码。是学习C语言的绝好资料
堆排序相关算法 输入一列数据进行堆排序 并显示每步数据交换 最后显示排序最终结果 适合初学者学习
堆排序c++实现,编译通过,供学习堆排序使用
仔细讲解了堆排序的过程,通过动画进行演示,适合用作课堂展示,也适合自己学习。
学习堆排序时自己编的代码,里面有自动生成随机数的代码段方便大家测试
本课件讲述堆排序的中建堆和排序的过程,并有详细的过程描述,对于建堆的过程有详细和动画介绍,通俗易懂,有助于学习和帮助
1. 实现最大堆的调整 2. 实现堆排序 3. 学习堆排序的demo 4. 代码仅作参考,亲测可用
算法导论上的堆排序c++源程序||学习分享
提供8中排序方法之一的堆排序代码,供大家学习和参考
我学习java的实践,基于堆的二维数组排序
该资源是一个入门级别的C++算法练习,旨在帮助读者学习和理解堆排序算法。文档中包含了堆排序的基本原理和实现方法,并提供了详细的代码示例和解析。 通过学习和完成这个练习,读者将能够掌握堆排序算法的思想和...
堆排序
堆排序过程实例PPT学习教案.pptx
本文对经典的堆排序非递归算法进行了详细的分析,并用JAVA实现。用过该问题的JAVA实现,可使学习者清晰的观测到解决该问题的全过程。
简单实现了快速排序和堆排序,堆排序采用和数据结构上面不同的向上筛选法,可以编译,运行,可供学习
数据结构与算法Python语言描述DS优先级队列和堆排序PPT学习教案.pptx
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
堆排序算法Java面向对象实现源码,仅供学习使用,算法实现用面向对象的方式实现本身效率上是个瓶颈。所以这个实例仅供学习使用,用到项目实践中就不能了。
本文实例讲述了C++实现堆排序算法的方法,相信对于大家学习数据结构与算法会起到一定的帮助作用。具体内容如下: 首先,由于堆排序算法说起来比较长,所以在这里单独讲一下。堆排序是一种树形选择排序方法,它的...
堆排序的实现,支持文件导入和手动写入数字进行排序,简单易懂,欢迎给位下载学习使用