堆分类是借助一种称为堆的完全二元树结构进行的。完全二元树可以用一个数组表示。在这种表示法中,容易确定一个结点的父结点及其左右儿子的下标。现在,把具有如下性质的数组A表示的完全二元树称为堆:(1)如果2i < n, 则A[i] <= A[2i] (2)如果2i + 1 < n, 则A[i] <= A[2i + 1] 。即树中任一非叶子结点的值都不大于其左右儿子结点的值。
堆排序算法思想:(1)初始化操作:初始建堆(2)每一趟排序的基本操作:将堆中的第一个结点值与最后一个结点值交换,重新把前面的元素整理成堆。
我的方法实现与这种略有差别:我是每次先整理成堆,然后交换。
其实都是一样的,都是以一个堆开始,以交换结束。
/**
* 堆排序类
*
* @author YouFengkai
*
*/
public class HeapSort {
private final int ARRAYSIZE = 10;
// 该数组表示一颗完全二叉树
private int[] tree;
public HeapSort() {
// 排序下标1到ARRAYSIZE的
this.tree = new int[ARRAYSIZE + 1];
for (int i = 0; i < this.ARRAYSIZE + 1; i++) {
tree[i] = (int) (1 + Math.random() * 40);
}
}
// 输出排序数组下标1到ARRAYSIZE中的所有数据
public void desc() {
for (int i = 1; i <= ARRAYSIZE; i++) {
System.out.print(tree[i]);
System.out.print(" ");
}
System.out.println();
}
// 堆排序
public void sort() {
int last = ARRAYSIZE;
for (int i = last; i >= 2; i--) {
// 初始化堆,先整理好堆,从i/2开始是因为这是最后一个非叶子结点
for (int j = i / 2; j >= 1; j--) {
pushDown(j, i);
}
// 树根为最小的,把它与最后的元素交换。
// 除最后的元素外,是一个只有树根不满足条件的堆,重新整理。
swap(1, i);
}
}
/**
* 交换树中两个节点的值
*
* @param positionA
* 第一个位置
* @param positionB
* 第二个位置
*/
private void swap(int positionA, int positionB) {
int temp = tree[positionA];
tree[positionA] = tree[positionB];
tree[positionB] = temp;
}
/**
* 下推整理堆
*
* @param first
* 开始整理的第一个节点
* @param last
* 最大的节点
*/
private void pushDown(int first, int last) {
// 如果first位置不是叶子节点,开始下推整理
int r = first;
if (r <= last / 2) {
// 如果当前节点不是叶子,则继续整理下推
while (2 * r <= last) {
int leftSon = 2 * r;
boolean hasRightSon = false;
int rightSon = leftSon + 1;
if (leftSon + 1 <= last) {
hasRightSon = true;
}
// 如果只有左儿子,且左儿子值比当前节点值小,则与左儿子交换
if (!hasRightSon && tree[leftSon] < tree[r]) {
swap(r, leftSon);
r = leftSon;
}
// 否则如果右儿子值不大于左儿子值,且左儿子值比当前节点值小,则与左儿子交换
else if (hasRightSon && tree[rightSon] <= tree[leftSon]
&& tree[rightSon] < tree[r]) {
swap(r, rightSon);
r = rightSon;
}
// 否则如果左儿子值不大于右儿子值,且左儿子值比当前节点值小,则与左儿子交换
else if (hasRightSon && tree[leftSon] <= tree[rightSon]
&& tree[leftSon] < tree[r]) {
swap(r, leftSon);
r = leftSon;
}
// 否则,不做变化。结束循环
else {
break;
}
}
} else {
return;
}
}
public static void main(String[] args) {
HeapSort hs = new HeapSort();
System.out.println("初始的数组为:");
hs.desc();
hs.sort();
System.out.println("经过堆排序后的数组为:");
hs.desc();
}
}
结果:
初始的数组为:
22 36 18 10 24 18 12 35 15 5
经过堆排序后的数组为:
36 35 24 22 18 18 15 12 10 5
分享到:
相关推荐
一个堆排序算法 c++写的 逻辑相同 可自行 改为java 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一...
最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法
六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
简单的堆排序算法:以定长数组为例,动态数组等可以以此类推
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
排序算法: 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
C语言实现的堆排序算法。 提供了堆排序算法的一个接口,可以为其它功能提供功能。
1) 对以下6种常用的内部排序算法进行比较:起泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序。 2) 待排序记录的文件个数不小于1000( 其数据用伪随机数产生),至少用5组不同的输入数据作比较;比较...
各种排序算法的实现函数:包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序。 查找最大最小值函数 findMinMax:在给定数组中查找最大值和最小值。 计算平均值...
堆排序:HeapSort 讲解详见http://blog.csdn.net/fly_yr/article/details/8550701 插入排序:InSertion_Sort 讲解详见http://blog.csdn.net/fly_yr/article/details/8544847 合并排序:MergeSort 讲解详见...
堆排序算法 java
排序算法汇总P: 冒泡排序快速排序直接选择排序插入排序希尔排序 堆排序........
上课的算法设计实验,内容有堆排序等一些内容!的代码 上课的算法设计实验,内容有堆排序等一些内容!的代码 上课的算法设计实验,内容有堆排序等一些内容!的代码
C++实现希尔、快速、堆排序、归并排序算法,一些中文注释可能成乱码了,但是不影响代码执行。
java的堆排序算法实现程序,含测试,可直接运行。java的堆排序算法实现程序,含测试,可直接运行。
简单的排序演示 有交换排序、快速排序、插入排序、堆排序、选择排序和希尔排序
算法设计课程中的最小堆排序算法实现,windows下实现。