个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
24
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章java堆排序概念原理介绍由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
堆排序介绍:
堆排序可以分为两个阶段。在堆的构造阶段，我们将原始数组重新组织安排进一个堆中；然后在下沉排序阶段，我们从堆中按顺序取出所有元素并得到排序结果.
1.堆的构造，一个有效的方法是从右到左使用sink()下沉函数构造子堆。数组的每个位置都有一个子堆的根节点，sink()对于这些子堆也适用，如果一个节点的两个子节点都已经是堆了，那么在该节点上调用sink()方法可以把他们合并成一个堆。我们可以跳过大小为1的子堆，因为大小为1的不需要sink()也就是下沉操作，有关下沉和上浮操作可以参考我写的优先队列那篇.
2.堆的排序，我们通过第一步操作构造了一个堆，在这个堆中，根节点永远是最大值的节点，所以我们把根节点的值与数组最后的值进行交换，在使用sink()下沉来维护堆的结构即可.
具体代码实现
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
public
class
pqsort{
public
static
void
main(string[] args){
int
[] a = {
9
,
1
,
7
,
5
,
3
,
9
,
12
,
56
,
21
,
45
};
sort(a);
for
(
int
i=
0
;i<a.length;i++) {
system.out.print(a[i]+
" "
);
}
}
//排序方法
public
static
void
sort(
int
[] a){
int
n = a.length-
1
;
//通过下沉操作构造堆,因为下标从0开始，所以子节点为2*k+1和2*k+2;
for
(
int
k = (n-
2
)/
2
;k>=
0
;k--){
sink(a,k,n);
}
//通过不断把堆中最大值放到数组的后面来排序
while
(n>
0
){
exch(a,
0
,n--);
sink(a,
0
,n);
}
}
//下沉函数
private
static
void
sink(
int
[] a,
int
i,
int
n){
while
(
2
*i+
1
<=n){
int
j =
2
*i+
1
;
if
(j<n&&a[j]<a[j+
1
]) j++;
if
(a[i]>a[j])
break
;
exch(a,i,j);
i=j;
}
}
//交换函数
private
static
void
exch(
int
[] a,
int
i,
int
j){
int
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
|
运行结果
最后此篇关于java堆排序概念原理介绍的文章就讲到这里了,如果你想了解更多关于java堆排序概念原理介绍的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
24
4
0
晚上在 QQ 上看到昵称为“乱码”的好友回答了搜搜问问里一个问题： 在VBS中有办法定义字节数组么？ 在VBS中有办法定义字节数组么？就是字节子类型数组（VarType是8209的那种）注意不是V
例如，员工管理应用程序可能包括一个EmPloyee 类。然后可以用这个类来创建和维护特定实例，比如Gonn和Sally。 根据预定义的类创建对象常称为类的实例化（class insta
在自然语言中，我们理解抽象的概念是，一个物体的一种大的描述，这种描述对某类物体来说是共有的特性。那么在PHP中也是一样的，我们把一个类进行抽象，可以指明类的一般行为，这个类应该是一个模板，它指示它的
DBA_2PC_PENDING Oracle会自动处理分布事务，保证分布事务的一致性，所有站点全部提交或全部回滚。一般情况下，处理过程在很短的时间内完成，根本无法察觉到。但是，如果在commit或
目录 计算过程 投影分量计算 假设你有一家理发店,已经记录了过去一年中所有顾客的头发长度和发型偏好的数据。现在你想从这些数据中提取一些主要的信息,比如顾客最常
Object.defineProperty函数会直接在一个对象上定义一个新的属性，或者修改一个对象的现有属性，并返回此对象。 一、简单使用 const obj = {} Object.defineP
SPL官网 http://www.scudata.com.cn/ 介绍 业务逻辑经常包含较复杂的流程和计算，同时涉及数据库的读写。由于授权麻烦、影响数据库安全、无法迁移、技术要求高、编写困难等原因，很
SPL官网 http://www.scudata.com.cn/ 介绍 业务逻辑经常包含较复杂的流程和计算，同时涉及数据库的读写。由于授权麻烦、影响数据库安全、无法迁移、技术要求高、编写困难等原因，很
一 点睛 Thrift 是一歀基于 CS 架构的 RPC 框架，最初由 Facebook 研发，2008 年转入 Apache 组织。开发人员可以使用 Thrift 提供的 IDL（接口定义语言）来定
数据库应用程序与主应用程序分开存在，并存储数据集合。 每个数据库都使用一个或多个API来创建，访问，管理，搜索和复制其包含的数据。 数据库还使用非关系数据源，例如对象或文件。 然而，数据库证明是大数
介绍 Ant是一个 Apache 基金会下的跨平台的基于 Java 语言开发的构件工具。在我们详细了解 Apache Ant 之前， 让我们来讲解为什么构建工具是需要最先了解的。 构建工具的需求
我现在正在尝试学习ocaml，并希望从一个小程序开始，生成所有位组合: [“0”，“0”，“0”] [“0”，“0”，“1”] [“0”，“1”，“0”] ... 等等 我的想法是下面的代码: let
我正在做我的介绍 C 类(class)作业，我的任务是执行以下任务...... 为一个函数编写代码，该函数通过值接收两个参数(a 和 b)并通过引用具有另外两个参数(c 和 d)。所有参数都是双倍的。
我希望提供有关我网站内容的快速演示，以及如何在用户访问我的页面后立即以正确的方式使用它们。我希望使用顶部的弹出式窗口进行演示。 我的意思是小信息框，一个接一个地通知用户各个步骤。任何人都可以帮助我如何
与C、Java等语言一样，JavaScript中可以用&&、||、!三个逻辑判断符来对boolean值进行逻辑判断。与C、Java不同的是，JavaScript中逻辑与(&&
JavaScript中，==与===操作符均可用于判断两个值是否相等；不同之处在于，如果进行判断的两个值类型不一致，===操作符会直接返回false，而==操作符则会在类型转换后再进行判断。详细的判
JavaScript中，object转换为boolean的操作非常简单：所有的object转换成boolean后均为true；即使是new Boolean(false)这样的object在转换为bo
在android开发中，当不满足触发条件就按返回键的时候，就要对此进行检测。尤其是当前Activity需要往前一个Activity传送消息时。即Activity1跳转到Activity3如果采用的是
背景 当要求系统启动一个应用程序时，系统会先查找当前命令是否是内部命令，若不是，则在当前目录下查找，如果仍没有找到，则在系统变量 Path 指定的路径去查找。JDK（Java Developmen
概述 想做一个微信的公众平台，阅读了微信官方给的网址接入的示例代码，发现有个问题好像一直都是半知半解的，就是在类里边直接使用$_GET。仔细查了下关于这方面的知识，发现PHP中这部分的基础知识掌握
我是一名优秀的程序员,十分优秀！