`
akon405
  • 浏览: 45561 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

2012/3/28----堆排序

 
阅读更多

堆排序是一种基于二叉树的排序,利用二叉树的性质进行排序的算法。但是这里的二叉树并不是真实存在的,是我们利用数组的编号进行设计的特殊的二叉树。

而堆排序其本质是一个就地排序算法。

/*
 * 堆排序算法
 * @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);
	}
}
 
0
0
分享到:
评论

相关推荐

    vc源代码合集.rar

    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++...

    数据结构考研真题(09-12)

    - **题目描述**:给定关键字序列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:错误。 ...

    2009~2012年计算机统考数据结构部分真题及解析

    3,5,12,8,28,20,15,22,19 **10. 排序方法** - **知识点**: 本题考查不同的排序算法的特点及其应用。 - **解析**: 题目给出了一组排序后的序列,并询问这是哪种排序算法的结果。观察给出的序列,可以看到...

    南京师范大学GIS考研01方向-C语言程序设计历年考研真题

    7. 排序算法:包括冒泡排序、快速排序、选择排序、堆排序、基数排序等,每种排序算法都有其特点和应用场景,对于理解算法的时间复杂度和空间复杂度非常有帮助。 8. 有向图中医院选址问题:这是一个典型的图论问题,...

    javascript入门笔记

    var age = 28; var msg = age &gt;= 18 ? "你已成年" : "你未成年"; 练习: 从弹框中录入一个数字表示考试成绩(score) 如果 成绩为 100 分 ,提示 :满分 如果 成绩 &gt;= 90 分 ,提示 :优 如果 成绩 &gt;= 80 分 ,...

    全国硕士研究生入学计算机专业统考历年真题及答案解析(答案缺2012的)

    根据小根堆的性质,正确选项为**A.3,5,12,8,28,20,15,22,19**。 10. **排序算法的识别**: 给出了一个排序序列的结果,要求识别出该排序算法。根据序列11, 12, 13, 7, 8, 9, 23, 4, 5,可以判断出这个序列...

    东南大学计算机专业考博真题回忆

    2. 排序与查找算法:快速排序、归并排序、冒泡排序、二分查找等。掌握算法的时间复杂度和空间复杂度分析,理解其效率对比。 3. 动态规划:解决最优化问题的常用方法,例如背包问题、最长公共子序列等。 4. 图论算法...

Global site tag (gtag.js) - Google Analytics