排序----堆排序

上一篇:快速排序

数据结构--堆的构造和实现

堆排序可以分为两个阶段:

  1. 构造堆。将原始数组重新组织安排进一个堆中
  2. 下沉排序。从堆中按递减顺序取出所有元素并得到排序结果

用下沉操作由N个元素构造堆只需少于2N次比较以及少于N次交换。

将N个元素排序,堆排序只需少于(2NlgN+2N)次比较以及一半次数的交换。2N来字堆的构造。

堆排序的特点:

  • 唯一的能够同时最优地利用空间和时间的方法。
  • 无法利用缓存。数组元素很少和相邻的元素直接比较,因此缓存未命中的次数远远高于其他排序算法。
  • 能够在插入操作和删除最大元素操作混合的动态场景中保证对数级别的运行时间。

堆排序实现要点:

  • 代码中堆是用数组实现的,数组a[0]弃之不用,堆顶元素存在a[1]中。
  • 最先构造的堆是最大堆(元素越大越靠近堆顶),然后通过循环交换a[1]和a[N--]元素,使大元素沉到数组底部,并修复堆。如此循环直到堆为空,则实现堆的数组中元素已经排好序了。
  • 下面代码是堆排序主要算法,具体堆的实现可以参考数据结构----堆。
public static void sort(Comparable[] a){
	int N = a.length;
	for(int k=N/2;k>=1;k--)//构造堆
		sink(a,k,N);//由上至下的堆有序化(下沉)的实现
	while(N>1){
		exch(a,1,N--);//交换
		sink(a,1,N);//修复堆
	}
}

下一篇:排序算法总结

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏北京马哥教育

Python正则表达式的七个使用范例

作为一个概念而言,正则表达式对于Python来说并不是独有的。但是,Python中的正则表达式在实际使用过程中还是有一些细小的差别。 本文是一系列关于Pyth...

34650
来自专栏PHP实战技术

解构赋值,你不能不懂!

153100
来自专栏JetpropelledSnake

Python入门之面向对象编程(一)面向对象概念及优点

本文分为如下几个部分 首先说明面向对象是什么,然后结合实际例子说明面向对象的如下几个优点 方便函数管理 数据封装 对象操作 最后总结一下面向对象的好处 概念...

39070
来自专栏aCloudDeveloper

全排列(含递归和非递归的解法)

全排列在近几年各大网络公司的笔试中出现的比较频繁 首先来看看题目是如何要求的。 用C++写一个函数, 如 Foo(const char *str), 打印出 s...

37390
来自专栏阿凯的Excel

Python读书笔记22(函数传递任意数量实参)

连小编都没想到一个小小的函数要分享这么多期~ 当然,主要原因是! 不好意思,放错图了是! 今天和大家分享函数的最后一个部分,虾米呢? 前期有分享过传递一个...

38470
来自专栏韦弦的偶尔分享

Swift 最长公共前缀 - LeetCode

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 ""。

13730
来自专栏前端黑板报

一个数字截取引发的精度问题(二)

上篇文章只是简单介绍了Number的 toFixed 方法,周末抽时间把 Number 里的一些方法又看了一下,其中有个方法引起我的注意: Number.pro...

20760
来自专栏Vamei实验室

Python基础09 面向对象的进一步拓展

我们熟悉了对象和类的基本概念。我们将进一步拓展,以便能实际运用对象和类。 调用类的其它信息 上一讲中提到,在定义方法时,必须有self这一参数。这个参数表示某个...

20770
来自专栏Vamei实验室

Python基础09 面向对象的进一步拓展

我们熟悉了对象和类的基本概念。我们将进一步拓展,以便能实际运用对象和类。 调用类的其它信息 上一讲中提到,在定义方法时,必须有self这一参数。这个参数表示某个...

21760
来自专栏老九学堂

【学习】Java微课堂之for循环

主要知识点 ? ? for循环注意要点 本讲视频中讲了for循环的要点以及三大循环的区别,主要笔记如下: 1.for循环是循环控制结构中使用最广泛的一种循环控制...

33960

扫码关注云+社区

领取腾讯云代金券