- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 82
- 收听数
- 1
- 能力
- 120 分
- 体力
- 565565 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 174892
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 5313
- 主题
- 5273
- 精华
- 3
- 分享
- 0
- 好友
- 163
TA的每日心情 | 开心 2021-8-11 17:59 |
|---|
签到天数: 17 天 [LV.4]偶尔看看III 网络挑战赛参赛者 网络挑战赛参赛者 - 自我介绍
- 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
 群组: 2018美赛大象算法课程 群组: 2018美赛护航培训课程 群组: 2019年 数学中国站长建 群组: 2019年数据分析师课程 群组: 2018年大象老师国赛优 |
8 d1 C- `1 [, x* `) H+ g- _十大经典排序算法之堆排序(Java语言)
: u6 g) z$ F6 X1 B$ B+ k* U% B, {文章目录
! }6 e$ k6 D3 ^- H9 d, u4 S) _9 ? ^" y
什么是堆( K; v' P6 O2 j
如何进行堆排序呢
y: [! P7 u: K( Y' _: ?0 W' d) Q用数组构建一个堆
; ?4 W! M+ B: \( H5 m. C' f上代码
* m, |" ]4 i3 A* h8 s4 \8 g3 Q# Z* V什么是堆
r$ G( O L, V# b0 s
4 n2 {" C9 ?, Z0 V# N在了解什么是堆之前一定要先了解什么是完全二叉树
3 j0 b' K0 ?- p+ d- o, i0 }/ o看一下百度百科的介绍/ @* O; A, o* n: D4 Y" u1 {# e# f
. m( [" s% ]' A0 T
若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
9 I0 _( k' v5 a7 i百度百科拗口版性质介绍,能看懂上面的就行,下面的大概看下7 L8 O" Y6 B" U
3 A0 y, {6 L) T8 `完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。7 I* U2 W8 K+ ?1 B: }1 Y2 q( y
(1)所有的叶结点都出现在第k层或k-l层(层次最大的两层)
7 O9 h& F& O# L' }4 i(2)对任一结点,如果其右子树的最大层次为L,则其左子树的最大层次为L或L+l。- l8 }5 f0 w% c" w* ?" m3 i
一棵二叉树至多只有最下面的两层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,则此二叉树成为完全二叉树,并且最下层上的结点都集中在该层最左边的若干位置上,而在最后一层上,右边的若干结点缺失的二叉树,则此二叉树成为完全二叉树。0 p5 i7 {$ v: i A1 R
那么在了解到什么是完全二叉树之后,我们再来看什么是堆
& M0 N1 P) u* @; I2 ~5 Y堆有以下两个性质, }" N( `' y9 |$ [& y* Y
7 x- c/ s# O8 p# e& t9 Z. I
1 堆中某个节点的值总是不大于或不小于其父节点的值;
+ C: [8 v6 ^' T# V, J5 i2 堆总是一棵完全二叉树。3 a" A+ }$ _* i7 ?
其中堆顶就对应二叉树的根
; G5 T6 @ |0 o2 M$ p
1 X" }7 u) B5 j堆又分为大顶堆和小顶堆,根据堆的第一个性质来进行区分
2 [% J4 H5 i) A9 m1 L" K2 P
' J7 p# M% Y' h& w当堆中某个节点的值总是大于它的子节点的时候这个堆为大顶堆,反之为小顶堆
! F# X6 h- H; M如何进行堆排序呢
9 e' L4 ^7 K& G5 d% Z5 m! s2 X' T
堆排序,其实就是每次构造出一个大顶堆或者小顶堆,然后取出堆顶的值,再将剩下的值重新构造成大顶堆或者小顶堆,最终到堆里的值全部取出来,取出来的数就是排好序的! c1 [7 L% ~# k6 V5 S V
0 E4 F( ]9 a$ F1 u9 q* ]用数组构建一个堆1 L. V0 \. t8 o. ~
: c' A( g" c: F. s
因为堆是一颗完全二叉树,所以我们可以用数组来对其进行存储
& S8 ^: X6 a! E; Q, W% Z0 \对于用数组存储的二叉树,我们可以用如下方法来定义:
+ D0 R" h: V- k9 x* ?假设当前节点的下标为 n( N# W' m+ A- S
$ e }, p. u5 A' M
1、那么他的左子节点的下标 2*n + 12 G* ?5 \! m5 `2 w
2、那么他的右子节点的下标 2*n + 2
0 e4 i9 m% u+ G! c3、他左边的节点是 n-1,如果当前节点是第 h 层的最左节点,那么第h-1层的最右节点的下标就是 n-1 f% M( W4 p- ^4 M4 }; }4 p
4、根据1、2可以推出来n节点的父节点是 (n-1)/2,不管当前节点是父节点的左子节点还是右子节点,都用 (n-1)/2就行了,因为整型数字相除小数点后面的会被截断
0 F8 u0 L6 ]( F5 k; f那么有了上面四条性质,我们就可以开始动手了" o* m4 L0 x1 d/ u8 y
4 _0 _! z4 A. F% u5 u7 J- h6 x! Y
1、假设我们要构建的堆是大顶堆,那么根据大顶堆的性质,任意节点都比它的左右子节点要大,所以我们肯定有个heapify方法,该方法调整指定节点和其子节点的位置,并且继续调整被调整的子节点和孙子节点的关系,直到没有调整或者到数的最底层
6 z" j0 ?" C4 T5 z; w) o' }2 ~2、然后我们要有构造大顶堆的方法,构造大顶堆就是从最后一个节点的父节点开始调整,接设最后一个节点的父节点是n,那么我们就将n,n-1,n-2 ··· ··· 0,这些节点逐次,从大到小调用heapify方法,这些节点都调整完成后,大顶堆就构造完成了
8 a( m- S1 Z+ y+ a3、接下来就开始将堆顶和堆尾互换,并砍断堆尾的操作了,由于互换之前,这是一个符合条件的大顶堆,但是换完只有只有一个堆顶这里不满足了,那么我们重新调整一下堆顶的三个元素就可以,还是调用heapify方法,这个方法会自上而下的重新调整堆,使其成为一个大顶堆
7 @( p1 H4 H8 K" A" D7 K8 M8 i2 X8 m1 E/ L. U5 a
堆排序的性质
. p% }" k- F/ m% R/ E6 g8 v% S3 D: {8 X& B) Q5 u: c
中文名称 英文名称 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性' L, R0 q- Y- v0 U1 P
堆排序 Heap n*logn n*logn n*logn 1 不稳定. ?) D6 T: {5 V) a, \4 T
上代码3 Z6 g1 h7 i0 A8 F1 M6 q% J
$ \$ Y2 C9 }) q' r Q4 P
/**
& b) B) o- ]" o, B) S; \* R: | * 交换第n和m个元素
! ]/ S) B* \- _7 U4 t2 ^" m */
; k* `) O Y8 h2 }- Y' Gprivate static void swap(int arr[], int n, int m){3 S: C; ]; g6 p
int temp = arr[n];
& O9 z4 J" ~+ d9 f) m' D arr[n] = arr[m];; p/ |: p7 r5 e. ^7 _+ s' n7 R
arr[m] = temp;
5 G! N5 ~0 `) U' x4 x6 f( z}6 P+ Y1 V: X% P8 m" B# W' i
, u; N5 X- f, G- C. _% A/**7 j, X3 c; G8 t; x+ Q
* 调整指定节点和其子节点
! e5 f7 g; r) T3 u5 J1 c * @param tree 整棵树. ~7 S( d* R# Z8 P
* @param n 数组长度,树的元素个数
5 Q0 r( H5 m0 }! r; C7 Z, p * @param i 要调整的节点的下标" ~$ G8 |: o+ ]
*/+ t+ ~* v% Q, n( U# y: l
private static void heapIfy(int tree[], int n, int i){4 r6 V$ s! L# w
if(i >= n){
+ |* D. [! r! X0 Z2 G! P9 Y return;) w; T1 O) w( R9 _! v
}
6 @' W8 f4 F' U: z int c1 = 2 * i + 1;//左子节点的下标) ?' p7 x0 n( w' J7 e6 P* t6 K
int c2 = 2 * i + 2;//右子节点的下标1 D, h6 e5 ?" `5 e) D- E0 J! W
int max = i;//假设父节点是最大的
. z6 D& u6 Y3 t3 ~7 Q6 W. F //找出最大值的下下标
% u" M$ {' @1 V: V" \ if(c1 < n && tree[c1] > tree[max]){
( a" [# }! ~6 z max = c1;5 d9 |+ S7 T( R
}5 m/ o1 s8 |* k$ w2 c" [' }
if(c2 < n && tree[c2] > tree[max]){
0 u, u' @* n) d; C; [: a max = c2;
/ @( M) P3 [8 m O, T3 k }
# T- R7 [) f' k! L2 K! [ if(max != i){//如果最大值不是父节点,需要做换位置操作
' Q4 d8 M0 j z6 h swap(tree, max, i);1 {9 Y# H1 d. e: c6 O8 t' B p. x
//此时,i节点被换成最大值了,符合大顶堆的性质. Z& Y; |, F# p7 F* C% e3 e
//但是换到下面的节点不能保证比他的两个子节点都要大8 b) C* E+ O9 s; E, G
//所以被换位置的节点继续调整
4 V" w$ b# s0 Y, T# H8 B5 o0 a; A heapIfy(tree, n, max);+ K; u" G0 u; _/ x3 p
}' E0 t4 Q) J+ }/ r- C# d2 t
}
$ r8 W" K. F0 t9 c$ I' [0 M) C* `0 {
/**
( ^( R/ Q2 o+ l$ c: N) p- l3 ]7 Z * 完整构建大顶堆
' S5 T' N# {$ ?! G# r7 \; ~- l * @param arr 用于构建堆的数组 }2 R8 H: T% d& w
* @param n 堆的最后一个节点的下标
2 n! {! r- i# S) Z2 ^3 G */+ C( d/ x, e. F0 T1 ~. s# e7 j
private static void buildHeap(int arr[],int n){
, h6 d h3 ?% E; ?" ~; F# z int lastNode = n - 1;
! o$ r. r& j; e) W6 o int parent = (lastNode - 1) / 2;
; V9 \; ?1 D% a+ p' h, M ^ for (int i = parent; i >= 0; i--){8 Q q! k- X% u5 V# c' [" L
heapIfy(arr, n, i);
) v9 s3 o' `8 l5 [& M. b$ g }
6 p3 }3 I6 @: }2 ?/ t}8 E6 C7 c" `( S* N6 Z
' U4 O/ W+ ]; R
/**
1 |( D. D4 {' [' W( o3 p2 F: z9 Z * 堆排序
3 y, r6 ?: l- X5 a! F * @param arr 待排数组% _# P- f, H9 v% I) S" L
*/
& U2 C4 Y7 O3 x3 s7 dpublic static void sort(int arr[]){
2 v" K _8 S9 I- {# z buildHeap(arr, arr.length);//先构造大顶堆
) Z. B4 p/ w: b5 }0 O9 Y, Z; V //每次构建堆后将根节点和最后一个节点进行交换
* m$ n' G7 {' G& @2 \! ?! B+ u( k //然后砍断最后一个节点0 j3 E$ _1 o( i( R: e2 u
//所以从最后一个节点向前循环+ P1 n1 n7 W6 Y2 ~, b
for (int i = arr.length - 1; i > 0; i--){5 \( Z* j/ L- ~8 o( A
swap(arr, 0, i);
) I! e+ g# R8 C/ w/ i; v heapIfy(arr, i, 0);
, K- g) ]; k& G X b; k- I" ] }
# K/ d1 w- K. J) D8 N8 t3 k4 s$ u}
5 A7 c q c/ C% x, u2 L————————————————
|. e6 J4 @( v9 [1 Y版权声明:本文为CSDN博主「qq_34912889」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。! z) ]& @& d1 m% @
原文链接:https://blog.csdn.net/qq_34912889/article/details/1056906447 w$ G4 I8 W$ ]. d7 S# m) m
3 Z3 @) F Q; v8 M1 ]
' M8 o4 w5 n! G' k |
zan
|