堆是一种特殊的数据结构,是一种完全二叉树,分为大根堆(根节点的值大于孩子节点)和小根堆(根节点小于孩子节点),建堆和堆排序代码如下:
package cn.com.daydayup.test;
public class StackSort {
public static void main(String[] args) {
int[] a = { 26, 5, 77, 1, 61, 11, 59, 15, 48, 19 };
Sort(a);
}
//堆排需方法
public static void Sort(int[] a) {
int n = a.length;//取得数组总长度,及堆最大的序号
int temp = 0;
Display(a, "Before sort : ");
//这是建堆的过程,一次从倒数第二层的根节点开始调整堆,即数组下标为i/2开始,一直到顶层根节点,这样就建好堆了。。
for (int i = n / 2; i > 0; i--) {
Adjust(a, i - 1, n);//从倒数第二层的最后一个根节点开始调整堆
Display(a, "建立大根堆 : ");
}
System.out.println("---------------------------------------");
for (int i = n - 2; i >= 0; i--) {//这是堆排序的具体算法,思想是每次取出堆的最顶层根节点,即数组下标为0,然后与最后一个节点即i+1交换,这样对于大根堆而言,最大值总是在后面。。循环过后就能排序了。。
temp = a[i + 1];//取出最后一个元素
a[i + 1] = a[0];//取出第一个元素,即顶层根节点
a[0] = temp;//交换位置
Adjust(a, 0, i + 1);//调整堆
Display(a, "重建立大根堆 : ");
}
Display(a, "After sort : ");
}
/**
* 调整堆的方法
* @param a 要调整的数组,即堆
* @param i 调整的根节点,即起始位置
* @param n 要调整的终止位置
*/
public static void Adjust(int[] a, int i, int n) {
int j = 0;
int temp = 0;
temp = a[i]; //取出根节点
j = 2 * i + 1; //左孩子节点
while (j <= n - 1) {
if (j < n - 1 && a[j] < a[j + 1])//比较左右孩子,取出较大的孩子
j++;
if (temp >= a[j]) //如果根节点大于孩子节点则退出循环,不用调整
break;
a[(j - 1) / 2] = a[j];//较大的孩子节点值赋值给根节点
j = 2 * j + 1;//继续寻找左孩子
}
a[(j - 1) / 2] = temp;//将根节点赋值给最后一个空出来的节点
}
//打印堆内容
public static void Display(int[] a, String str) {
System.out.println(str);
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
System.out.println();
}
}
分享到:
相关推荐
最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法
简单的堆排序算法:以定长数组为例,动态数组等可以以此类推
// 堆排序 #include typedef int InfoType; // 定义其它数据项的类型 #include "compare.h" #include "sort.h" typedef SqList HeapType; // 堆采用顺序表存储表示 void HeapAdjust(HeapType &H,int s,int m) // ...
一个堆排序算法 c++写的 逻辑相同 可自行 改为java 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一...
包含了四种常见的排序算法,是招聘面试时常出的题目,最好自己编译跑一遍
C语言实现的堆排序算法。 提供了堆排序算法的一个接口,可以为其它功能提供功能。
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
堆排序算法 java
java的堆排序算法实现程序,含测试,可直接运行。java的堆排序算法实现程序,含测试,可直接运行。
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
排序算法中的堆排序的代码,其他排序算法的代码可以私信我~
自己看书时写的排序算法:堆排序 CPP文件
排序算法包 各种排序算法 java源 堆排序,快排等各种排序算法
算法导论上堆排序算法的vc6.0下的Test实例。
用c语言实现堆排序算法,堆排序算法的实现,分析堆排序算法
堆排序的源代码; 平台:openSUSE 11.4 编译器:GCC version 4.5.1
# sort.heapSort() #堆排序 # sort.countSort() #计数排序 # sort.quickSort() #快速排序 该排序算法把每次的排序结果都列出来,可供初学者学习。 self.arr存放的是待排序列表,可改成自己的数据
详解Java常用排序算法-堆排序
自己编写的堆排序算法实现函数,本人亲测过绝对好使的代码,在这里与大家分享交流,希望能够给你带来帮助