堆排序是一种基于二叉树的排序,利用二叉树的性质进行排序的算法。但是这里的二叉树并不是真实存在的,是我们利用数组的编号进行设计的特殊的二叉树。
而堆排序其本质是一个就地排序算法。
/*
* 堆排序算法
* @version 1.0 2012/3/28
* @author akon
*/
package com.akon405.www;
public class HeapSort {
/*
* createMaxHeap的功能:
* 创建最大堆
*/
public void createMaxHeap(int[] A,int length){
int j;//最后一个非叶子节点
for(j=length/2-1;j>=0;j--){
heapAdjust(A,j,length);//依次遍历每个非叶结点,然后做出调整
}
}
/*
* heapAdjust的功能:
* 进行堆的调整,使它始终是最大堆
*/
public void heapAdjust(int[] A,int i,int length){
int l,r,temp;
l=i*2+1;//非叶节点的左子节点
r=i*2+2;//非叶节点的右子节点
int largest=i;//比较当前节点和子节点的大小的标志
while(l<length||r<length){
if(l<length&&r<length){
//当左右子节点都存在的时候
if(A[i]<A[l]&&A[r]<A[l]){
largest=l;
}
if(A[i]<A[r]&&A[r]>A[l]){
largest=r;
}
}else if(l<length&&r>=length){
//只有左子节点,没有右子节点
if(A[i]<A[l]){
largest=l;
}
}
if(largest!=i){
temp=A[i];
A[i]=A[largest];
A[largest]=temp;
i=largest;
l=i*2+1;
r=i*2+2;
}else{
break;
}
}
}
/*
* HeapSort的功能:
* 进行堆排序
*/
public HeapSort(int[] A,int length){
int temp;
createMaxHeap(A,length);//创建最大堆
System.out.print("最大堆:");
for(int i=0;i<A.length;i++){
System.out.print(A[i]+",");//输出我们第一次创建的最大堆(主要是用来调试程序)
}
while(length>1){
temp=A[length-1];
A[length-1]=A[0];
A[0]=temp;
length--; //把最大的数值放到数组末尾,然后再把堆进行整理,让剩余的数值继续构成一个最大堆
heapAdjust(A,0,length);
}
System.out.println("");
System.out.print("排序结果:");
for(int i=0;i<A.length;i++)
System.out.print(A[i]+",");
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] A={40,10,32,8,78,98,20,3,1};
int length=A.length;
new HeapSort(A,length);
}
}
分享到:
相关推荐
2012-06-11 08:57 88,576 C++ 开发中内存分配及堆和栈的区别.doc 2012-06-11 08:52 190,100 C++中二维数组与指针关系的剖析.pdf 2012-06-11 08:48 171,862 C++函数后加const的意义.pdf 2012-06-11 08:57 9,174 C++...
- **题目描述**:给定关键字序列5,8,12,19,28,20,15,22是小根堆,插入关键字3后的结果。 - **选项分析**: - A. 3,5,12,8,28,20,15,22,19:正确。 - B. 3,5,12,19,20,15,22,8,28:错误。 ...
3,5,12,8,28,20,15,22,19 **10. 排序方法** - **知识点**: 本题考查不同的排序算法的特点及其应用。 - **解析**: 题目给出了一组排序后的序列,并询问这是哪种排序算法的结果。观察给出的序列,可以看到...
7. 排序算法:包括冒泡排序、快速排序、选择排序、堆排序、基数排序等,每种排序算法都有其特点和应用场景,对于理解算法的时间复杂度和空间复杂度非常有帮助。 8. 有向图中医院选址问题:这是一个典型的图论问题,...
var age = 28; var msg = age >= 18 ? "你已成年" : "你未成年"; 练习: 从弹框中录入一个数字表示考试成绩(score) 如果 成绩为 100 分 ,提示 :满分 如果 成绩 >= 90 分 ,提示 :优 如果 成绩 >= 80 分 ,...
根据小根堆的性质,正确选项为**A.3,5,12,8,28,20,15,22,19**。 10. **排序算法的识别**: 给出了一个排序序列的结果,要求识别出该排序算法。根据序列11, 12, 13, 7, 8, 9, 23, 4, 5,可以判断出这个序列...
2. 排序与查找算法:快速排序、归并排序、冒泡排序、二分查找等。掌握算法的时间复杂度和空间复杂度分析,理解其效率对比。 3. 动态规划:解决最优化问题的常用方法,例如背包问题、最长公共子序列等。 4. 图论算法...