public class HeapSort {
public static void main(String[] args) {
Integer[] datas = {5,1,56,4,9,7,23,108,34,24,12};
sort(datas);
}
public static void sort(Integer[] datas) {
// 构建最大堆
buildMaxHeap(datas);
// 循环,每次把根节点和最后一个节点调换位置
for (int i = datas.length; i > 1; i--) {
Integer tmp = datas[0];
datas[0] = datas[i - 1];
datas[i - 1] = tmp;
for(Integer data : datas) {
System.out.print(data + "\t");
}
System.out.println();
// 堆的长度减少1,排除置换到最后位置的根节点
maxHeapify(datas, 1, i - 1);
}
}
// 根据输入数组构建一个最大堆
private static void buildMaxHeap(Integer[] data) {
// 其中有一般是叶子节点,不需要全部进行构建
for (int i = data.length / 2; i > 0; i--) {
maxHeapify(data, i, data.length);
}
}
//堆调整,使其生成最大堆
private static void maxHeapify(Integer[] data, int parentNodeIndex, int heapSize) {
// 计算左节点索引
int leftChildNodeIndex = parentNodeIndex * 2;
// 计算右节点索引
int rightChildNodeIndex = parentNodeIndex * 2 + 1;
// 最大节点索引
int largestNodeIndex = parentNodeIndex;
// 如果左节点存在并且左子节点大于父节点,则将左子节点作为最大节点
if (leftChildNodeIndex <= heapSize && data[leftChildNodeIndex - 1] > data[parentNodeIndex - 1]) {
largestNodeIndex = leftChildNodeIndex;
}
// 如果有节点存在并且右子节点比最大节点还大,那么最大节点应该是右子节点
if (rightChildNodeIndex <= heapSize && data[rightChildNodeIndex - 1] > data[largestNodeIndex - 1]) {
largestNodeIndex = rightChildNodeIndex;
}
// 最后,如果最大节点和父节点不一致,则交换他们的值
if (largestNodeIndex != parentNodeIndex) {
Integer tmp = data[parentNodeIndex - 1];
data[parentNodeIndex - 1] = data[largestNodeIndex - 1];
data[largestNodeIndex - 1] = tmp;
// 交换完父节点和子节点的值,对换了值的子节点检查是否符合最大堆的特性
maxHeapify(data, largestNodeIndex, heapSize);
}
}
}
分享到:
相关推荐
本代码主要演示了堆排序的排序方法,代码在centos7中测试通过。 编译方法使用g++ heapsort.cpp -o heapsort,运行heapsort即可
heapsort
c语言实现堆排序算法 heapsort 排序算法 。采用随机产生100个数 利用堆排序 。排序1000次 计算排序用的时间。
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。 堆排序的平均时间复杂度为Ο...
基于c++的堆积排序算法。排序算法大体可分为两种: 一种是比较排序,时间复杂度O(nlogn) ~ O(n^2),主要有:冒泡排序,选择排序,插入排序,归并排序,堆排序,快速排序等。 另一种是非比较排序,时间复杂度可以达到...
堆排序的实现,支持文件导入和手动写入数字进行排序,简单易懂,欢迎给位下载学习使用
自己写的一些简单算法和数据结构的代码 快排 堆排 归并 二分查找 单链表
sort sort_使用C++实现的排序算法之HeapSort
zoj 2665 Heapsort.md
1_HeapSort.java
排序算法 排序算法_基于C语言实现的排序算法之HeapSort实现
heapSort-heapSort
runoob-algorithm-HeapSort.zip
通过堆排序的方式实现对一维数组的排序(数组输入在主函数中完成)
我们首先实现了swap函数用于交换两个元素的值,然后实现了heapify函数用于调整堆,最后实现了heapSort函数用于进行堆排序。在main函数中,我们定义了一个数组并对其进行堆排序,然后打印排序前后的数组。运行该代码...
堆排- -。使用了模板。一般可以实现正确输入的排序。
堆排序(Heapsort)是指利用堆这种数据结构(后面的【图解数据结构】内容会讲解分析)所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的...
heapsort代码, 导入txt文件,然后进行排序,vc++6.0通过
主要介绍了Java实现堆排序(Heapsort)实例代码,有需要的朋友可以参考一下
HeapSort.java