个人中心
文章发布
退出
作者热门文章
- 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
关闭。这个问题是off-topic .它目前不接受答案。 想改进这个问题？ Update the question所以它是on-topic对于堆栈溢出。 10年前关闭。 Improve this qu
我正在开发一个 Android 应用程序。在此应用程序中， Logo 栏显示在所有页面( Activity )上，或者我们可以说它在所有页面上都有标题。这个 Logo 栏有几个图标，如主页、登录、通知
我正在使用 hadoop 使用开源接口(interface) HVPI 处理视频。然而，inputsplit 的实现，更准确地说是在 isSplitableobContext (context, Pa
1. 是什么？ MySQL 是最流行的关系型数据库管理系统，在 WEB 应用方面 MySQL 是最好的 RDBMS(Relational Database Management System
有没有办法使用 c++20s 的概念来检查一个值是否满足某些要求？ 假设我正在编写某种使用分页的容器，并且我想让页面大小成为模板参数。 template class container; 我可以使用带
如何在 ArrayList 中循环遍历 ArrayList？ 例如，如果我有一个名为 Plants of Plant 对象的 ArrayList。每个 Plant 对象内部都有一个随机数量的花名。我如
如何在UML类图中绘制C++概念？ 具体来说，我有以下代码: template concept Printable = requires(T a, std::ostream &where) {
我有兴趣制作一个网站，在访问者访问时闪现整个网络历史记录。我计划使用 JavaScript 来获取每个观看者计算机上的历史记录，并根据他们拥有的内容以不同的速度对其进行动画处理。我的想法是使用 his
有一个模板定义，例如: template void foo( void ) { /* ... */ } 如何定义一个概念，以便N必须为非零正值(N> = 1)？ 就像是: template con
封装是信息隐藏还是导致信息隐藏？ 正如我们所说，封装将数据和函数绑定(bind)在单个实体中，因此它为我们提供了对数据流的控制，并且我们只能通过一些定义良好的函数来访问实体的数据。因此，当我们说封装导
下面有一个简单的代码片段，它使用以下方式进行编译: g++-9 -std=c++2a -fconcepts 这是试图定义一个需要存在函数的概念。我希望输出是"is"，但事实并非如此……知道为什么吗？谢
我有一个普通二元运算符的概念 template concept is_binary_operation = requires (const T& t1, const T& t2) // e.g
我正在c++ 20中实现具有启发式功能的搜索算法。 我试图用类似这样的概念来约束我的算法可以使用的功能: template concept Heuristic = requires(SelfType
我需要了解 SAS 如何读取/执行数据步骤。当我查找有关 SAS 如何读取数据步骤的信息时，我似乎只找到有关它如何读取以进行合并的信息，我不了解与常规数据步骤相关的信息。比方说，我有这行代码: dat
最近我看到一个关于“框架”的问题，如果“框架”有不同的类型或概念。那么，存在不同“类型”的“框架”吗？ 例如:NodeJS 是一种“类型”(概念)，而 Hibernate ORM 是另一种“类型”(概
如何使用任何技术禁用或清除客户端浏览器 Cookie 我认为使用 javascript 可以用于任何技术 最佳答案 var cookies = document.cookie.split(";");
我正在使用 target = "_blank" 单击链接时生成新选项卡。但是，浏览器会将焦点移至该选项卡。 有没有办法让焦点保持在当前标签页上？ 回答摘要 基本上，只需发送一个模拟控件点击的当前事件。
我正在尝试在我的 android/firebase(cloud firestore) 应用程序上添加一项需要其他用户批准/拒绝的功能。例如，当 Air&BnB 上的用户想要预订一个地方时，所有者必须批
这个问题在这里已经有了答案: mysql_fetch_array()/mysql_fetch_assoc()/mysql_fetch_row()/mysql_num_rows etc... expec
public class MyClass { public static void main(String[] args) { System.out.println("Hell
我是一名优秀的程序员,十分优秀！