/**
* 堆排序 维基百科
* */
public class HeapSorts {
private static int[] sort = {144,233,55,66,1235,85,4,79};
/**
* @param args
*/
public static void main(String[] args) {
buildMaxHeap(sort);
heapSort(sort);
for(int i : sort){
System.out.println(i);
}
}
private static void heapSort(int[] data){
for(int i = data.length -1; i >0 ;i--){
//交换 将堆顶的值和最后一个元素交换
int temp = data[i];
data[i] = data[0];
data[0] = temp;
//交换完 从 堆顶就开始不稳定了 因此要从第一个元素开始重新建
maxHeap(data,i,0);
}
}
private static void buildMaxHeap(int[] data){
int startIndex = getParaentIndex(data.length -1);
//建堆
for(int i = startIndex ;i >=0 ;i--){
maxHeap(data,data.length,i);
}
}
/**
* @param index 建堆的位置
* @param heapSize
* */
private static void maxHeap(int[]data ,int heapSize ,int index){
int left = getLeftChildIndex(index);
int right = getRightChildIndex(index);
int largest = index ;//用来记录根 左右孩子的最大值
//创建的是大根堆
if(left < heapSize && data[index] < data[left]){
largest = left;
}
if(right < heapSize && data[largest] < data[right]){
largest = right;
}
//如果最大值不是根节点 需要交换
if(largest != index){
int temp = data[index];
data[index] = data[largest];
data[largest] = temp ;
//交换后可能破坏子堆的稳定性 因此要重新建堆 largest 记录了交换的位置
maxHeap(data,heapSize,largest);
}
}
//获取父节点
private static int getParaentIndex(int current){
return (current - 1) >> 1 ;
}
//获取左孩子节点
private static int getLeftChildIndex(int current){
return (current << 1) + 1;
}
//获取右孩子节点
private static int getRightChildIndex(int current){
return (current << 1) + 2;
}
}
分享到:
相关推荐
把待排序的数组构造出最大堆是进行堆排序操作的基本方法,这里将带大家来解读堆排序算法及用C++实现基于最大堆的堆排序示例,首先从堆排序的概念开始:
网络上堆排序的教程很多,但是却几乎都是以数组存储的数,直接以下标访问元素,当然这样是完全没有问题的,实现简单,访问速度快,也容易理解。 但是以练手的角度来看,我还是写了一个二叉树存储结构的堆排序 其中最...
堆排序的思想 利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单。 最大堆:所有节点的子节点比其自身小的堆。 最小堆:所有节点的子节点比其自身...
个人原创总结的常用排序算法C语言示例代码解说PDF...包含有直接插入排序,折半插入排序,2路直接插入排序,起泡排序,简单选择排序,快速排序,堆排序,(希尔排序,归并排序,基数排序为空白),供学习排序算法的爱好者参考。
冒泡排序、快速排序;:简单插入、希尔排序;简单选择、堆排序;简单归并、多路归并;计数排序;桶排序;基数排序的PPT讲解及代码演示
*一个简单的能够形象演示各种排序算法的applet小程序 *类似于Sun公司的示例程序,但比它复杂 ... *快速排序,希尔排序,堆排序,归并排序共七种排序算法 *每次80个整数随机生成,七种算法同时运行,之间的对比非常明显
4.7.2 堆排序算法示例 121 4.8 合并排序法 123 4.8.1 合并排序算法 123 4.8.2 合并排序算法示例 126 4.9 排序算法的效率 129 4.10 排序算法的其他应用 130 4.10.1 反序排序 130 4.10.2 字符串数组的排序 132...
047 堆排序 048 归并排序 049 基数排序 050 二叉搜索树操作 051 二项式系数递归 052 背包问题 053 顺序表插入和删除 054 链表操作(1) 055 链表操作(2) 056 单链表就地逆置 057 运动会分数统计 058 双...
7.5 堆排序 7.6 归并排序 7.7 快速排序 7.7.1 选取枢纽元 7.7.2 分割策略 7.7.3 小数组 7.7.4 实际的快速排序例程 7.7.5 快速排序的分析 7.7.6 选择问题的线性期望时间...
最新Python3.5零基础+高级+完整项目(28周全)培训视频学习资料;本资料仅用于学习。 【课程内容】 第1周 开课介绍 python发展介绍 ...堆排序复习 归并排序 希尔排序 算法练习 栈和队列 数据结构其他
最小和最大堆(更改排序顺序或修改的比较器、getter、setter) 添加文字 比喻一个漏斗来解释它? 类似于谐波势的量子化能级? 应用示例:锦标赛、音序器? 添加 Leftist、Skew 和 Binomial 堆?
几种简单排序之间的比较 小结 问题 实验 编程作业 第4章 栈和队列 不同的结构类型 栈 队列 优先级队列 解析算术表达式 小结 问题 实验 编程作业 第5章 链表 链结点(Link) LinkList专题Applet 单链表 查找和删除...
7.5 堆排序 7.6 归并排序 7.7 快速排序 7.7.1 选取枢纽元 7.7.2 分割策略 7.7.3 小数组 7.7.4 实际的快速排序例程 7.7.5 快速排序的分析 7.7.6 选择问题的线性...
全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和队列、链表、递归、进阶排序、二叉树、红黑树、哈希表及图形等知识。附录中则提供了运行专题Applet和例程、相关书籍和问题解答。本书提供了学完一门编程...
堆排序 小结 问题 实验 编程作业 第13章 图 图简介 搜索 最小生成树 有向图的拓扑排序 有向图的连通性 小结 问题 实验 编程作业 第14章 带权图 带权图的最小生成树 最短路径问题 每一对顶点...
堆排序 小结 问题 实验 编程作业 第13章 图 图简介 搜索 最小生成树 有向图的拓扑排序 有向图的连通性 小结 问题 实验 编程作业 第14章 带权图 带权图的最小生成树 最短路径问题 每一对顶点...
3.9.6 简单示例 —— 向ndarray添加额外属性 132 3.9.7 稍微更现实的例子 —— 添加到现有数组的属性 134 3.9.8 __array_ufunc__ 对于ufuncs 135 3.9.9 __array_wrap__用于ufuncs和其他函数 139 3.9.10 额外的坑 ...
-简单方便,示例可以参考 default.aspx 或者 other\accordion_tree_run.aspx。 +2009-08-14 v2.0.6 -动态生成菜单实例(other\menu_dynamic_run.aspx和other\menu_dynamic2_run.aspx)(feedback:shguo)。 -...
9.4.2 堆排序 9.5 归并排序 9.6 基数排序 9.7 内部排序总结 9.8 有关排序算法的C语言源程序 9.9 多路归并用于外排序的简介 习题九 第10章 文件 10.1 文件的基本概念 10.1.1 文件 10.1.2 外存储器及信息...
我将这些图表开发为用于项目管理和时间跟踪的简单工具。 它基于和作为工具提示。 交互式堆积图 数据以按组类型排列的连续顺序显示,以便于数据组之间的比较。 在此示例中,团队A,B,C和D有4个数据组,具有3种工作...