参照改写自 http://blog.kingsamchen.com/archives/547#viewSource
public class HeapSorter {
int temp = 0;
/*
* 输 入: Ary(int[]) - [in,out]排序数组 nIndex(int) - 起始下标 nHeapSize(int) - 堆大小 输
* 出: - 功 能: 从nIndex开始检查并保持最大堆性质
*/
void MaxHeapify(int Ary[], int nIndex, int nHeapSize) {
while (true) {
int nL = left(nIndex);
int nR = right(nIndex);
int nLargest;
if (nL <= nHeapSize && Ary[nIndex] < Ary[nL]) {
nLargest = nL;
} else {
nLargest = nIndex;
}
if (nR <= nHeapSize && Ary[nLargest] < Ary[nR]) {
nLargest = nR;
}
if (nLargest != nIndex) {
// 调整后可能仍然违反堆性质
swap(Ary, nLargest, nIndex);
nIndex = nLargest;
} else {
break;
}
}
}
/*
* 输 入: Ary(int[]) - [in,out]排序数组 nHeapSize(int) - [in]堆大小(zero-based) 输 出:
* - 功 能: 将一个数组改造为最大堆
*/
void BuildMaxHeap(int Ary[], int nHeapSize) {
for (int i = parent(nHeapSize); i >= 0; --i) {
MaxHeapify(Ary, i, nHeapSize);
}
}
/*
* 输 入: Ary(int[]) - [in,out]排序数组 nCount(int) - [in]元素个数 输 出: - 功 能:
* 对一个数组进行堆排序
*/
void HeapSort(int Ary[], int nCount) {
int nHeapSize = nCount - 1;
BuildMaxHeap(Ary, nHeapSize);
for (int i = nHeapSize; i >= 1; --i) {
swap(Ary, 0, i);
--nHeapSize;
MaxHeapify(Ary, 0, nHeapSize);
}
}
private void swap(int[] array, int index1, int index2) {
temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
private int left(int x) {
return (x << 1) + 1;
}
private int right(int x) {
return (x + 1) << 1;
}
private int parent(int x) {
return ((x + 1) >> 1) - 1;
}
public static void main(String[] s) {
int a[] = {6, 16, 4, 10, 14, 7, 9, 3, 2, 8, 1 };
new HeapSorter().HeapSort(a, 10);
for (int i : a) {
System.out.print(i + ",");
}
}
}
输出结果是:1,2,3,4,6,7,8,9,10,14,16,
未做优化.原文就不贴出了
分享到:
相关推荐
堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用...
Java 写得最大堆排序代码,给大家参考下,自己刚写的。
NULL 博文链接:https://128kj.iteye.com/blog/1679094
Java实现堆排序算法的代码。这是一个完整的示例,它首先构建一个大顶堆(升序排列时),然后通过交换堆顶元素和最后一个元素,并对剩余元素重新调整堆来完成排序
此外,文档还包括一个逐步指南,介绍了如何在Java中实现堆排序,包括详细的代码示例和实现细节。 文档还涵盖了高级主题,如如何优化代码以提高性能以及如何处理大的数组。该资源包括实用练习,让读者可以练习在Java...
代码十分清楚的描述了堆排序是如何进行的,配合笔者写的博客,可以将此种算法掌握的十分牢靠,代码结构清晰。
Java各种排序算法代码,冒泡,插入,希尔,快速,堆等排序代码
java堆排序和几种排序方法实现代码.pdf
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
java堆排序和几种排序方法实现代码文.pdf
用java实现的常用排序,都可以编译运行。 包括shellSort, quickSort, mergeSort, heapSort
java数组排序的思想,过程和代码实现。多种数组排序的方法,主要有冒泡排序,堆排序,插入排序, 归并操作(merge), 归并操作(merge),选择排序,希尔排序。
介绍堆排序的概念、特点、优缺点、适用场景和java代码简单实现
十大排序算法十大排序算法源码,自己整理的,可以直接运行,Java版本
包括了堆排序 归并排序 快速排序 基数排序 选择排序 冒泡排序 插入排序 希尔排序 计数排序 桶排序等算法。
对于堆排序的java实现的理解,是初学数据结构的人的入门资源
Java各种排序算法集合: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(箱排序、基数排序)
Java大根堆演示代码 在控制台输入java -jar maxHeap.jar后即可运行项目。 所支持的操作: 0:初始化一个新堆 1:向堆中插入一个数值 2:增大堆中某个节点的值 :堆排序操作 4:打印堆的树结构 5:打印堆排序结果 6:...
主要介绍了Java算法之堆排序代码示例,具有一定参考价值,需要的朋友可以了解下。
排序方法总结---Java语言源代码 排序方法总结---Java语言源代码