文档章节

堆排序

notAcoder
 notAcoder
发布于 2013/10/04 03:06
字数 513
阅读 54
收藏 3

堆排序是基于完全二叉树的排序。把一个完全二叉树调整为堆,以及每次堆顶元素交换后进行调整的时间复杂度均为O(lgn),所以堆排序的时间复杂度为O(nlgn)。堆排序的空间复杂度为O(1).堆排序是一种不稳定的排序。

堆排序的步骤为:

  1.将待排序的数组构建为一个最大堆
  2.在最大堆的基础上排序
  (1)把堆顶a[0]元素(最大的元素)和当前最大堆的最后一个元素交换
  (2)最大堆元素减一
  (3)调整跟节点使它满足最大堆 

java代码实现:

import java.util.Arrays;

/**
 * 堆排序
 * 1.将待排序的数组构建为一个最大堆
 * 2.在最大堆的基础上排序
 * 	(1)把堆顶a[0]元素(最大的元素)和当前最大堆的最后一个元素交换
 *  (2)最大堆元素减一
 *  (3)调整跟节点使它满足最大堆 
 */
public class HeapSort {

	/**
	 *@Description
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int arr[] = {10,50,32,5,76,9,40,88};
		heapSort(arr);
		System.out.println(Arrays.toString(arr));
	}
	
	public static void heapSort(int arr[]){
		initMaxHeap(arr);
		int n = arr.length,temp;
		for(int i=n-1;i>=0;i--){
			//把堆顶a[0]元素(最大的元素)和当前最大堆的最后一个元素交换
			temp = arr[0];
			arr[0] = arr[i];
			arr[i] = temp;
			//逐渐缩小堆的大小
			createMaxHeap(arr,0,i);
		}
	}
	
	//初始化最大堆
	public static void initMaxHeap(int arr[]){
		int n = arr.length;
		//从第一个非叶节点开始构造最大堆,注意完全二叉树的性质
		for (int i = (n-1)/2; i >= 0; i--) {
			createMaxHeap(arr,i,n);
		}
	}
	
	/**
	 *@Description 创建最大堆
	 * @param arr 需要创建堆的数组
	 * @param i 开始下标
	 * @param n 堆的大小
	 */
	public static void createMaxHeap(int arr[],int i,int n){
		int left = 2*i+1;
		int	right = 2*i+2;
		int largest = i;
		if(left<n && arr[left]>arr[largest]){
			largest = left; 
		}
		if(right<n && arr[right]>arr[largest]){
			largest = right;
		}
		if(largest!=i){
			int temp = arr[i];
			arr[i] = arr[largest];
			arr[largest] = temp;
			//递归地构建孩子节点,使其满足最大堆的特性
			createMaxHeap(arr,largest,n);
		}
	} 
	
}

© 著作权归作者所有

上一篇: 快速排序
下一篇: 清除浮动
notAcoder
粉丝 5
博文 30
码字总数 12671
作品 0
巴南
架构师
私信 提问
MySQL:关于排序order by limit值不稳定的说明(1)

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

gaopengtttt
2018/12/07
0
0
程序员必知的8大排序(java实现)

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

小帅帅丶
2015/01/09
360
7
JavaScript数据结构与算法(堆)

堆是一种完全二叉树. 堆得使用基本是通过最大堆和最小堆来实现的! 最大堆,最大堆中的最大元素值出现在根结点(堆顶),堆中每个父节点的元素值都大于等于其孩子结点 最小堆,最小堆中的最大元...

fiveoneLei
2018/07/12
0
0
算法——堆排序

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

嘿胖丁
2018/03/05
29
0
浅解前端必须掌握的算法(五):堆排序(下)

前言 虽然前端面试中很少会考到算法类的题目,但是你去比如像腾讯一样的大厂面试的时候就知道了,对基本算法的掌握对于从事计算机科学技术的我们来说,还是必不可少的,每天花上 10 分钟,轻...

程序猿何大叔
2018/07/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

SSH安全加强两步走

从 OpenSSH 6.2 开始已经支持 SSH 多因素认证,本文就来讲讲如何在 OpenSSH 下启用该特性。 OpenSSH 6.2 以后的版本多了一个配置项 AuthenticationMethods。该配置项可以让 OpenSSH 同时指定...

xiangyunyan
27分钟前
4
0
C或C++不是C/C++

http://www.voidcn.com/article/p-mucdruqa-ws.html

shzwork
今天
6
0
OSChina 周六乱弹 —— 如何将梳子卖给和尚

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @for_ :划水五分钟,专注两小时。分享Various Artists的单曲《贝多芬第8号钢琴奏鸣曲悲伤的第三乐章》: 《贝多芬第8号钢琴奏鸣曲悲伤的第三乐...

小小编辑
今天
179
8
ES5

什么是ES5:比普通js运行要求更加严格的模式 为什么:js语言本身有很多广受诟病的缺陷 如何:在当前作用域的顶部添加:"use strict" 要求: 1、禁止给未声明的变量赋值 2、静默失败升级为错误...

wytao1995
今天
7
0
c++ 内联函数调用快的原因

见图片分析

天王盖地虎626
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部