- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 82
- 收听数
- 1
- 能力
- 120 分
- 体力
- 558510 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 172926
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 5313
- 主题
- 5273
- 精华
- 18
- 分享
- 0
- 好友
- 163
TA的每日心情 | 开心 2021-8-11 17:59 |
---|
签到天数: 17 天 [LV.4]偶尔看看III 网络挑战赛参赛者 网络挑战赛参赛者 - 自我介绍
- 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
 群组: 2018美赛大象算法课程 群组: 2018美赛护航培训课程 群组: 2019年 数学中国站长建 群组: 2019年数据分析师课程 群组: 2018年大象老师国赛优 |
. }$ M ]# _/ ^9 B( m十大经典排序算法之堆排序(Java语言)
5 Y) X. O* R. c1 N; X5 E文章目录+ a n5 L' T7 M' e* s$ l( I. J; X% `* W, D
7 E- h7 x8 P) ?0 {/ j) U8 R什么是堆
3 h7 I' t7 w, t ]3 `. ]! U$ k如何进行堆排序呢+ D; c: E8 {" @& e T+ c- N
用数组构建一个堆 \. Q% {3 T7 m K4 |% ~
上代码& q. i. C) S# Y8 A
什么是堆
$ ^0 @: I2 T/ X& }6 \( ?: z3 F" j% E! U; e" A: i! Z
在了解什么是堆之前一定要先了解什么是完全二叉树6 n' `" q% t% J. _5 l* ^" w) j' i
看一下百度百科的介绍$ R* C: w; c' c
% G/ n4 L2 R# l7 j9 V9 d- e
若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
) e2 W# r( a7 K' {& y5 @百度百科拗口版性质介绍,能看懂上面的就行,下面的大概看下. x; G8 H' @' ~7 N$ ]3 q
9 @7 w: f8 L5 D9 G* c. j# F) c完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
5 u7 P! e. Z; e+ r. H. \% y. z(1)所有的叶结点都出现在第k层或k-l层(层次最大的两层)
$ g5 i6 P* u6 e& o' V3 ]9 G(2)对任一结点,如果其右子树的最大层次为L,则其左子树的最大层次为L或L+l。
M% R8 \# \7 r/ p8 A% J/ i9 K' F, O2 O一棵二叉树至多只有最下面的两层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,则此二叉树成为完全二叉树,并且最下层上的结点都集中在该层最左边的若干位置上,而在最后一层上,右边的若干结点缺失的二叉树,则此二叉树成为完全二叉树。
% P" W% e4 ^+ I, [9 V4 D那么在了解到什么是完全二叉树之后,我们再来看什么是堆
9 i* b/ n3 A2 d2 Y# j" ]7 W6 S9 U堆有以下两个性质
* _( G3 u( z5 ]( T) ?: Q" |7 o A" H& x2 y/ ?' u0 X
1 堆中某个节点的值总是不大于或不小于其父节点的值;
0 S7 y+ i7 R$ a+ H2 堆总是一棵完全二叉树。
+ [8 [! X, M0 w9 E) V/ X9 k3 A* d其中堆顶就对应二叉树的根
6 I% r4 B: R; n# L" M( I" u6 D+ p$ Q* q
堆又分为大顶堆和小顶堆,根据堆的第一个性质来进行区分
4 b' b& _9 w, |6 V3 N3 B/ Q% H5 o# B! ]: _% O
当堆中某个节点的值总是大于它的子节点的时候这个堆为大顶堆,反之为小顶堆7 q* g5 M8 G r) q: \$ ]: O7 N
如何进行堆排序呢% {1 A4 m' T' s3 U0 L$ y
' ], y4 D0 L4 L% Y/ Y; Y
堆排序,其实就是每次构造出一个大顶堆或者小顶堆,然后取出堆顶的值,再将剩下的值重新构造成大顶堆或者小顶堆,最终到堆里的值全部取出来,取出来的数就是排好序的& r) ]: L" Z* o, A; t5 `2 N
* K; m9 V7 N9 I) A/ M
用数组构建一个堆
# O+ o7 Z. {1 w" W' L- r3 _4 @- z: z) J8 B+ S8 A
因为堆是一颗完全二叉树,所以我们可以用数组来对其进行存储6 K3 N) @" C0 L5 e+ |/ }
对于用数组存储的二叉树,我们可以用如下方法来定义:
# x0 Q R, Q: u1 H4 @4 {( g假设当前节点的下标为 n
9 g i- v& B0 A- Y% c) P; t' z* a/ Z1 I8 u0 \* ^: F
1、那么他的左子节点的下标 2*n + 1
* a6 {- N) ?5 l* k, ]" a, m# k0 U2、那么他的右子节点的下标 2*n + 2" ]$ ]+ T& h$ r A9 \
3、他左边的节点是 n-1,如果当前节点是第 h 层的最左节点,那么第h-1层的最右节点的下标就是 n-1
a+ d( i, U6 C6 L" q: t. m* _4、根据1、2可以推出来n节点的父节点是 (n-1)/2,不管当前节点是父节点的左子节点还是右子节点,都用 (n-1)/2就行了,因为整型数字相除小数点后面的会被截断
* l" c6 |3 O0 e: t* E! D2 H# {# x4 h那么有了上面四条性质,我们就可以开始动手了
* u4 M k% V8 {4 S/ b- }. V- h, [% F. L! j8 m* C
1、假设我们要构建的堆是大顶堆,那么根据大顶堆的性质,任意节点都比它的左右子节点要大,所以我们肯定有个heapify方法,该方法调整指定节点和其子节点的位置,并且继续调整被调整的子节点和孙子节点的关系,直到没有调整或者到数的最底层4 F! Y. p+ d ~
2、然后我们要有构造大顶堆的方法,构造大顶堆就是从最后一个节点的父节点开始调整,接设最后一个节点的父节点是n,那么我们就将n,n-1,n-2 ··· ··· 0,这些节点逐次,从大到小调用heapify方法,这些节点都调整完成后,大顶堆就构造完成了
; L# B R# ?' v( f0 v) f1 V3、接下来就开始将堆顶和堆尾互换,并砍断堆尾的操作了,由于互换之前,这是一个符合条件的大顶堆,但是换完只有只有一个堆顶这里不满足了,那么我们重新调整一下堆顶的三个元素就可以,还是调用heapify方法,这个方法会自上而下的重新调整堆,使其成为一个大顶堆
! a1 H, a) @! N- p0 l7 A- }4 Q: z. o! L7 m- V" c& U& i
堆排序的性质
4 B) C/ d3 {& n: \6 g* o$ W" _, R" H, P5 k$ M- B5 v: H
中文名称 英文名称 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性# I U2 H* _4 [/ Z( i ?% q9 ]
堆排序 Heap n*logn n*logn n*logn 1 不稳定- {0 f# Z" b* [4 C' A% |( u
上代码* p7 n! n& q; ], e2 E. D
' ^9 v4 X, P: X& ^' [
/**% ]: I; P ]* m3 H
* 交换第n和m个元素
$ k& }5 N/ v8 T. a5 q */0 ~4 b0 W ~& ^
private static void swap(int arr[], int n, int m){( ?! J' U, h# x, F6 H9 m
int temp = arr[n];# q7 r6 R9 ]. |2 R( ]
arr[n] = arr[m];+ P+ _" { _9 L" ^ X
arr[m] = temp;
3 v4 ?, c: X E8 B- r2 a' Z) c}
' Z% D- E; ]5 y; \0 d* X4 n5 e3 y6 G' G8 g1 L/ G
/**
% P4 F* W+ W8 I * 调整指定节点和其子节点6 r# e: ~ V5 ]" l: \! I) u
* @param tree 整棵树
: d' `9 t8 v" p. h2 P' g * @param n 数组长度,树的元素个数
( \" O {1 e' z0 ~9 @ * @param i 要调整的节点的下标& o% m5 ~2 U; `/ O7 u/ g
*/4 u8 r3 ~+ h! h
private static void heapIfy(int tree[], int n, int i){! h+ ~5 X7 m" U- u4 z1 j
if(i >= n){/ n6 z- a U; o" I {
return;5 v1 t- N3 Y( | s
}
) F6 |* h7 y, ]( m- d int c1 = 2 * i + 1;//左子节点的下标3 K/ t& x. a( i; X8 {( U/ T! Q
int c2 = 2 * i + 2;//右子节点的下标. l. H. U; m- U1 j
int max = i;//假设父节点是最大的' q% p. v( \5 c3 U9 D) k4 o; Z
//找出最大值的下下标
8 U! y3 w2 |# F$ d. @- \) L if(c1 < n && tree[c1] > tree[max]){
' P$ t2 O6 m7 I0 h! z4 [, m1 d max = c1;
8 r. E/ |; l. p5 S3 U7 w }5 h' w* s/ R' u* C; {
if(c2 < n && tree[c2] > tree[max]){
3 \. Q( v% R4 a& s1 I max = c2;
8 Y, h' @) H3 X1 ~ }9 q) z! G j& N- @. R
if(max != i){//如果最大值不是父节点,需要做换位置操作
+ ^/ k% V. e+ c# c/ t+ q swap(tree, max, i);. \9 s, t, w% F# j
//此时,i节点被换成最大值了,符合大顶堆的性质
" L( K' s( c( f* s0 E //但是换到下面的节点不能保证比他的两个子节点都要大7 j" H$ {3 B" l& l+ r
//所以被换位置的节点继续调整
3 k- u Q5 E- V! P0 C heapIfy(tree, n, max);) m5 ~- \5 ^) P* E8 f& N
}( e+ U3 d* s' u) A$ R7 ` l; W
}
; j5 ^( K; w/ H* W$ M; ]4 Z3 U- A9 }$ n5 m2 d0 \9 X) f
/**% u# Y6 k/ ], I( I
* 完整构建大顶堆
) A2 v6 Q# A' M6 X+ i5 Q * @param arr 用于构建堆的数组
) _/ l- b. z4 a * @param n 堆的最后一个节点的下标0 P, V# W( X0 z$ K" Y( d! L: I) m0 Y
*/
3 J9 d$ Q9 k3 g% n, Hprivate static void buildHeap(int arr[],int n){% `+ x: m. x! q) }3 ^( k, a
int lastNode = n - 1;! {1 R$ f- q# J4 |' y# O. Y
int parent = (lastNode - 1) / 2;
% O, Y- Z3 ^, u) r8 t& J/ [ for (int i = parent; i >= 0; i--){6 B! D( ~ V; }; s
heapIfy(arr, n, i);
) Y( H0 _0 O" k7 X/ a, c }
9 x9 d( k" |; j}
( ^3 o& p s N8 Z
/ Y- { ~4 u0 e1 z2 I& M/**
" d }# h3 y" I8 Z. f5 ? * 堆排序! J" i. L. c; X' v4 F1 h$ u+ J
* @param arr 待排数组4 ^) v! u+ c' c) j! {* o( g0 q
*/% g+ O( [/ Z0 l ?* p2 H6 T
public static void sort(int arr[]){
8 L4 s! J) G0 v buildHeap(arr, arr.length);//先构造大顶堆0 h, v8 k U* F* K
//每次构建堆后将根节点和最后一个节点进行交换
. f% |3 I0 @7 ]5 W% X v6 l //然后砍断最后一个节点* |. r6 \6 B, S
//所以从最后一个节点向前循环1 L% U' d6 e3 E4 \, E
for (int i = arr.length - 1; i > 0; i--){6 j! ~7 C' c$ l/ e0 F9 m
swap(arr, 0, i);& R+ |6 z; y" |' S1 n
heapIfy(arr, i, 0);1 `6 N+ k ]4 ?& ]2 x% z; s) f
}
/ d2 W6 Z* p* @}$ b* n1 f0 C& a( P! T
————————————————+ [1 x' J9 p8 L1 ^* A `3 p
版权声明:本文为CSDN博主「qq_34912889」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。$ p- d9 b9 C9 O G
原文链接:https://blog.csdn.net/qq_34912889/article/details/105690644
, U6 D# b7 j# Z4 A% p% Z5 o3 D
+ C+ P/ R7 O5 k4 j$ ^7 }5 h% ]& Y1 C2 V7 B; X# j- z" k
|
zan
|