文档章节

排序-堆排序

一杯82年的JAVA
 一杯82年的JAVA
发布于 2016/05/04 17:03
字数 415
阅读 29
收藏 0

【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>

主要思路:

(1)根据初始数组去构造 初 始 堆 (构建一个完全二叉树,保证所有的父结点都比它的孩子结点数值大)。

(2)每次交换 第一个 和 最后一个元素,输出最后一个元素(最大值),然后把 剩下元素 重新调整为大根堆。

public class HeapSort {

	public static void main(String[] args) {
		int[] array = { 2, 3, 5, 1, 4 };
		heapSort(array);
	}

	public static void heapSort(int[] list) {
		// 循环建立初始堆
		for (int i = list.length / 2; i >= 0; i--) {
			heapAdjust(list, i, list.length);
			System.out.print("初始化(" + i + "):");
			printArray(list);
		}
		// 进行n-1次循环,完成排序
		for (int i = list.length - 1; i > 0; i--) {
			// 最后一个元素和第一元素进行交换
			int temp = list[i];
			list[i] = list[0];
			list[0] = temp;
			// 调整前面元素组成的堆
			heapAdjust(list, 0, i); // 0~i,忽略i后面的,相当于最大的数移到数组尾部后已经被“移除”
			System.out.format("第 %d 趟:\t", list.length - i);
			printArray(list);
		}
	}

	/**
	 * 将array[parent,length)调整为最大堆
	 */
	private static void heapAdjust(int[] array, int parent, int length) {
		int temp = array[parent]; // temp保存当前父节点
		int child = 2 * parent + 1; // 先获得左孩子
		while (child < length) {
			// 如果有右孩子结点,并且右孩子结点的值大于左孩子结点,则选取右孩子结点
			if (child + 1 < length && array[child] < array[child + 1]) {
				child++;
			}
			// 如果父结点的值已经大于孩子结点的值,则直接结束
			if (temp >= array[child])
				break;
			// 把孩子结点的值赋给父结点
			array[parent] = array[child];
			// 选取孩子结点的左孩子结点,继续向下筛选
			parent = child;
			child = 2 * child + 1;
		}
		array[parent] = temp;
	}

	private static void printArray(int[] array) {
		for (int i = 0; i < array.length - 1; i++)
			System.out.print(array[i] + ",");
		System.out.println(array[array.length - 1]);
	}
}


© 著作权归作者所有

一杯82年的JAVA
粉丝 8
博文 76
码字总数 36575
作品 0
杭州
程序员
私信 提问
MySQL:关于排序order by limit值不稳定的说明(1)

水平有限,有过有误请谅解和指正,仅仅作为抛砖引玉。谢谢! 源码版本:5.7.14 本文约定:PQ 就是 Priority Queue 及优先队列其核心是堆排序,文中代表一种算法。 一、问题抛出 数据如下: ...

gaopengtttt
2018/12/07
0
0
mysql 在orderby和limit混合使用时重复数据问题

# 问题背景 select * from table_1 order by field_1,field_2 limit 0,10;select * from table_1 order by field_1,field_2 limit 10,10; 这样两条分页sql在查询数据时有两条数据既出现在第一......

小孑
2018/08/07
0
0
程序员必知的8大排序(java实现)

8种排序之间的关系:  1、 直接插入排序   (1)基本思想:   在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好...

小帅帅丶
2015/01/09
373
7
十种常见排序算法

1.常见算法分类 十种常见排序算法一般分为以下几种: (1)非线性时间比较类排序:交换类排序(快速排序和冒泡排序)、插入类排序(简单插入排序和希尔排序)、选择类排序(简单选择排序和堆...

architect刘源源
2018/01/28
16
0
算法——堆排序

我们可以把任意优先队列编程一种排序方法。将所有元素插入一个查找最小元素的优先队列,然后再重复调用删除最小元素的操作来将他们按顺序删除。用无序数组实现的优先队列这么做相当于一次选择...

嘿胖丁
2018/03/05
31
0

没有更多内容

加载失败,请刷新页面

加载更多

nginx反向代理+负载均衡+服务器宕机解决办法

反向代理 作用:保证系统安全,不暴露服务器IP,利用nginx服务器,利用内网ip进行访问,避免出现攻击服务器的情况 启动本地tomact,127.0.0.1:8080可以访问到tomcat管理页面 效果:通过 bbs....

Jack088
5分钟前
1
0
返回IEnumerable 与IQueryable相比 [关闭]

返回IQueryable<T>与IEnumerable<T>之间有什么区别? IQueryable<Customer> custs = from c in db.Customerswhere c.City == "<City>"select c;IEnumerable<Customer> custs = from c i......

技术盛宴
12分钟前
2
0
开放下载 | 《Knative 云原生应用开发指南》开启云原生时代 Serverless 之门

点击下载《Knative 云原生应用开发指南》 自 2018 年 Knative 项目开源后,就得到了广大开发者的密切关注。Knative 在 Kubernetes 之上提供了一套完整的应用 Serverless 编排服务,让应用开发...

阿里巴巴云原生
16分钟前
2
0
解密淘宝推荐实战,打造 “比你还懂你” 的个性化APP

手淘推荐简介 手淘推荐的快速发展源于2014年阿里“All in 无线”战略的提出。在无线时代,手机屏幕变小,用户无法同时浏览多个视窗,交互变得困难,在这样的情况下,手淘借助个性化推荐来提升...

阿里云官方博客
18分钟前
2
0
内核程序中进程的pid,handle,eprocess之间相互转换的方法

在内核程序开发中,我们常常需要取得某进程的pid或句柄,或者需要检索进程的eprocess结构,很多API函数需要的参数也不同,所以掌握pid<->handle<->eprocess相互转换的方法会大大提高我们的开...

simpower
20分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部