主程序:
package yangkunlin.algorithm.sort;
import yangkunlin.algorithm.tool.SortTool;
/**
* 堆排序
*
* 前提:堆的根节点的序号是1,并且满足最大堆属性。
* 堆是存放在数组中的,堆的大小要小于数组的大小。
* 注意下边个方法的参数是以1开始记得。
*
* 时间复杂度:O(nlgn)
* 原地排序,不需要多余的空间。
* @author yangkunlin
*
*/
public class HeapSort {
/**
* 最大堆排序算法,将source按最大堆排序算法由小到大排序
* @param source
*/
public void heapSort(int[] source){
bulidMaxHeap(source);
for (int lastElement = source.length -1; lastElement >0; lastElement--) {
SortTool.exchange(source, 0, lastElement);
maxHeapily(source, 1, lastElement);
}
}
/**
* 以第i个元素为根的子树保持最大树,终点为第heapSize个元素。source中第heapSize个元素之后的元素不予理会。
* 即堆的大小为heapSize,从数组第一个元素到第heapSize个元素为止。
* @param source
* @param i 第i个元素,指的是从1开始的。因此后边在取数组元素的时候,都有-1.
* @param heapSize
*/
public void maxHeapily(int[] source,int i ,int heapSize){
int left = Left(i);
int right = Right(i);
int largest = i;
if(heapSize >= left && source[left-1] > source[i-1] ){
largest = left;
}
if(heapSize >= right && source[right-1] > source[largest-1]){
largest = right;
}
if(largest != i){
SortTool.exchange(source, i-1, largest-1);
maxHeapily(source, largest ,heapSize);
}
}
/**
* 构建最大堆树
* @param source
*/
public void bulidMaxHeap(int[] source){
//beginFlag以后的都是叶子节点。
int beginFlag = (int)Math.floor(source.length/2);
for(int i = beginFlag; i >= 1 ;i--){
maxHeapily(source, i , source.length);
}
}
/**
* 根据序号获得左儿子的序号
*/
public int Left(int i){
return 2*i;
}
/**
* 根据序号获得右儿子的序号
*/
public int Right(int i){
return 2*i + 1;
}
}
辅助类方法
/**
* 交换数组中两元素的位置
* @param source
* @param i
* @param j
*/
public static void exchange(int[] source, int i, int j) {
int bridge = source[i];
source[i] = source[j];
source[j] = bridge;
}
分享到:
相关推荐
参考《算法导论》这本书写的一个堆排序的代码,我个人是用Visual studio写的。只要一个积分哦
堆排序 java实现
根据算法导论第六章实现的堆排序
简单的堆排序算法:以定长数组为例,动态数组等可以以此类推
堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆...
算法导论上的堆排序c++源程序||学习分享
堆排序算法 java
堆排序算法Java实现
java的堆排序算法实现程序,含测试,可直接运行。java的堆排序算法实现程序,含测试,可直接运行。
数据结构堆排序的java算法实现,里面用java语言实现了堆排序的算法实现,有输入和输出结果
堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用...
实现算法导论中的堆排序,区别数组以0作为根,算法导论中的实现是以数组1作为根
ps:按照书中伪码写成,元素由1开始,故数组中第一位A[0]为填充,并不算在排序中。 for(int i = length; i >= 2;) { temp = A[i]; //交换堆的第一个元素和堆的最后一个元素 A[i] = A[1]; A[1] = temp; i--; //...
Java实现堆排序不是C,Java实现堆排序不是C,Java实现堆排序不是C,Java实现堆排序不是C
Java排序算法实现 Java排序算法实现 Java排序算法实现
php堆排序(算法导论)
堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆...
用Java实现的堆排序算法,二叉树转换为堆,然后排序
第6章 堆排序 第7章 快速排序 第8章 线性时间排序 第9章 中位数和顺序统计学 第三部分 数据结构 第10章 基本数据结构 第11章 散列表 第12章 二叉查找树 第13章 红黑树 第14章 数据结构的扩张 第四部分 高级设计和...