本文共 2355 字，大约阅读时间需要 7 分钟。

学习了堆排序的思想，便试着用Java设计堆排序算法，如下即对应的堆排序方法，代码注释描述了堆排序的思想即堆排序与其他排序的不同之处： [color=blue]/** * 堆排序使用的是最大堆,即堆中的每个节点的值都不小于其子节点的值. * 堆排序的思想: * 1.构建最大堆; * 2.从最大堆中移除根节点,也就是最大值; * 3.将最后一个节点移至根节点的位置; * 4.一直向下筛选这个节点,直至满足最大堆的条件为止; * 5.重复以上操作即可从大到小移除所有节点,即实现了排序. * * 堆排序可以直接在原数组基础之上构建最大堆,无需额外的存储空间,构建最大堆的时间复杂度为O(n*log(n)). * 堆排序移除最大节点的时间复杂度为O(1),但是筛选节点的时间复杂度为O(log(n)),因此排序的时间复杂度为O(n*log(n)). * * @param array */[/color] public static void heapSorting(int[] array) { final int[] a = array; final int length = a.length; int p, q, r, s; [color=blue]/** * 构建最大堆. * 此处认为数组索引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即可,这样减少了复制的次数. */[/color] [color=green]/*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; }*/[/color] [color=blue]/** * 构建最大堆. * 此处采用n/2次向下筛选代替n次向上筛选来构造最大堆,只需对非叶子节点操作即可,即索引为0~n/2-1. */[/color] for(s = (length >> 1) - 1; s >= 0; s--) { r = a[s]; [color=blue]//向下筛选形成新的最大堆. //用数组表示最大堆时节点的子节点即为2x+1与2x+2,这里取2x+2即只遍历左右子节点均存在的情况. //这里也采用了如上机制减少了复制的次数.[/color] 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; } [color=blue]//此处添加if判断是因为可能有只存在左子节点的情况，上述for循环并不包括这种情况,因此需要特殊考虑.[/color] if(--q < length && a[q] > r) a[p] = a[p = q]; a[p] = r; } [color=blue]/** * 从最大堆中删除根节点并复制到数组中. * 此处认为数组索引0~last是最大堆,last+1之后的为已经排好序的元素,从最大堆中删除根节点并与索引last所在元素交换,执行向下筛选形成新的最大堆, * 即新的最大堆索引为0~last-1,last之后的为新的已经排好序的元素,重复进行删除操作即可完成排序(last为0). */[/color] for(s = length - 1; s > 0; s--) { [color=blue]//交换删除根节点.[/color] r = a[s]; a[s] = a[0]; [color=blue]//向下筛选形成新的最大堆. //用数组表示最大堆时节点的子节点即为2x+1与2x+2,这里取2x+2即只遍历左右子节点均存在的情况. //这里也采用了如上机制减少了复制的次数.[/color] 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; } [color=blue]//此处添加if判断是因为可能有只存在左子节点的情况，上述for循环并不包括这种情况,因此需要特殊考虑.[/color] if(--q < s && a[q] > r) a[p] = a[p = q]; a[p] = r; } } 下面是堆排序与快速排序的性能对比 数据量 10e5 10e6 10e7 堆排序时间： [color=red]0.01158s 0.21217s 5.63784s[/color] 快速排序时间： [color=red]0.01143s 0.12764s 1.47240s[/color]

转载地址：https://blog.csdn.net/iteye_5883/article/details/82477884 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！