- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 82
- 收听数
- 1
- 能力
- 120 分
- 体力
- 564648 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 174617
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 5313
- 主题
- 5273
- 精华
- 3
- 分享
- 0
- 好友
- 163
TA的每日心情 | 开心 2021-8-11 17:59 |
|---|
签到天数: 17 天 [LV.4]偶尔看看III 网络挑战赛参赛者 网络挑战赛参赛者 - 自我介绍
- 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
 群组: 2018美赛大象算法课程 群组: 2018美赛护航培训课程 群组: 2019年 数学中国站长建 群组: 2019年数据分析师课程 群组: 2018年大象老师国赛优 |
$ U, }4 |0 {$ Z( Z十大经典排序算法之堆排序(Java语言)
' g2 \/ I7 }9 W( H2 n+ T文章目录$ u+ o% u/ x, x7 j+ ]
, t. m1 ^+ U, @8 m" `& u0 k- S什么是堆8 Z7 n5 A( b: u3 c/ Q9 e6 O( [
如何进行堆排序呢6 I$ J1 I* b; u, w j9 C. S3 T
用数组构建一个堆
5 H% R6 V5 C* Y/ J上代码
3 x4 _. C' H0 K! k% E什么是堆
. C3 n9 Y; c8 h. A7 m9 t( h j+ l9 S" j5 ^& W( e- a0 W) A* f: F
在了解什么是堆之前一定要先了解什么是完全二叉树
( d/ r! ]. X; ]看一下百度百科的介绍
% Z% h7 ^0 G. L! a5 d$ V1 b1 U1 |+ P# B5 @+ d
若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。3 Q! l+ A- w, r6 x: S
百度百科拗口版性质介绍,能看懂上面的就行,下面的大概看下
Z5 @$ d7 H" v- O3 }0 p0 e2 y4 q! V/ L9 a" u( ^ C2 v
完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。) J9 S4 e" z0 s+ P4 ]9 w
(1)所有的叶结点都出现在第k层或k-l层(层次最大的两层)
7 t( R# F7 K8 q1 R(2)对任一结点,如果其右子树的最大层次为L,则其左子树的最大层次为L或L+l。& u$ {; \) v0 A3 C' k6 m4 V! v
一棵二叉树至多只有最下面的两层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,则此二叉树成为完全二叉树,并且最下层上的结点都集中在该层最左边的若干位置上,而在最后一层上,右边的若干结点缺失的二叉树,则此二叉树成为完全二叉树。0 C% M' s" ?' C7 b! t# l
那么在了解到什么是完全二叉树之后,我们再来看什么是堆* t, |( Z F, r1 H. K. N& R
堆有以下两个性质
8 p* v+ f/ R6 H, k2 E+ R% H7 a0 r; e# c! Z. g/ U
1 堆中某个节点的值总是不大于或不小于其父节点的值;
* w, R" ?% z2 j2 堆总是一棵完全二叉树。
3 V: w# H; V8 S8 v$ Z其中堆顶就对应二叉树的根
4 o( u( a/ A! m- A t+ J) `; Y5 k6 l* l3 ?8 f. A; C! v
堆又分为大顶堆和小顶堆,根据堆的第一个性质来进行区分/ V2 {! l; y/ H8 f9 t
0 u% F. w! K& c |8 _! W" l" t7 j
当堆中某个节点的值总是大于它的子节点的时候这个堆为大顶堆,反之为小顶堆
" M% ~3 ~/ @' h6 w' v) S如何进行堆排序呢
; Y+ b7 E* H3 \8 }: p7 U) h. r- Y- Z, n: _ o3 V8 k# p# o
堆排序,其实就是每次构造出一个大顶堆或者小顶堆,然后取出堆顶的值,再将剩下的值重新构造成大顶堆或者小顶堆,最终到堆里的值全部取出来,取出来的数就是排好序的
* C8 L$ g0 u" [- }
. m9 _' x% {, G. V5 Y5 j用数组构建一个堆
. h% E5 N9 q! `4 B8 `" A' x2 u% F5 e- U
因为堆是一颗完全二叉树,所以我们可以用数组来对其进行存储* A, v$ F( E d1 z( d6 S
对于用数组存储的二叉树,我们可以用如下方法来定义:! Y+ s/ h' J( I$ H( ^8 t
假设当前节点的下标为 n7 r% H9 W/ X/ q4 P. K6 s
- c8 d2 J; u' R/ F4 l2 h3 l
1、那么他的左子节点的下标 2*n + 1
! R! x" Y1 I- U4 o5 s$ u8 L2、那么他的右子节点的下标 2*n + 2- e. T9 F4 K* l8 b( v
3、他左边的节点是 n-1,如果当前节点是第 h 层的最左节点,那么第h-1层的最右节点的下标就是 n-1* F3 k: {# Q. c' K
4、根据1、2可以推出来n节点的父节点是 (n-1)/2,不管当前节点是父节点的左子节点还是右子节点,都用 (n-1)/2就行了,因为整型数字相除小数点后面的会被截断
. r, P; Z7 L1 r4 I5 x6 j' S那么有了上面四条性质,我们就可以开始动手了6 O* l' W6 X, w8 u! }6 e
8 U3 r) b! o# @+ @3 Q2 K
1、假设我们要构建的堆是大顶堆,那么根据大顶堆的性质,任意节点都比它的左右子节点要大,所以我们肯定有个heapify方法,该方法调整指定节点和其子节点的位置,并且继续调整被调整的子节点和孙子节点的关系,直到没有调整或者到数的最底层- p! n) F! ^9 r0 z+ B3 N) B
2、然后我们要有构造大顶堆的方法,构造大顶堆就是从最后一个节点的父节点开始调整,接设最后一个节点的父节点是n,那么我们就将n,n-1,n-2 ··· ··· 0,这些节点逐次,从大到小调用heapify方法,这些节点都调整完成后,大顶堆就构造完成了8 e. e7 A1 p/ V+ ]/ g1 x
3、接下来就开始将堆顶和堆尾互换,并砍断堆尾的操作了,由于互换之前,这是一个符合条件的大顶堆,但是换完只有只有一个堆顶这里不满足了,那么我们重新调整一下堆顶的三个元素就可以,还是调用heapify方法,这个方法会自上而下的重新调整堆,使其成为一个大顶堆
) z- G. Q' \: h7 \& F% Q" v d6 g1 h! r
堆排序的性质& F/ Q3 k" n7 o6 l$ E+ k
3 E! R* b8 @/ u* u! n# o中文名称 英文名称 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性8 x' @& j" d S8 l) f
堆排序 Heap n*logn n*logn n*logn 1 不稳定9 A u: F6 V+ d H* p( E
上代码
3 W7 [0 X/ h4 i: X1 {0 S# ]; L6 D2 v# S+ ?) b
/**
+ V) a8 |( V! P' E7 ^* K o* u' m3 p * 交换第n和m个元素$ e4 p! k6 V- N& ?; G
*/
' [' C) T$ o" cprivate static void swap(int arr[], int n, int m){
6 [8 F3 m& p) Y2 E) _ int temp = arr[n];
8 ^' n U v @# M3 {; x- m, M } arr[n] = arr[m];' v, o T4 z! I8 `; I7 s
arr[m] = temp;" q; k' d8 k! N9 j) G- H. B. H) k: G
}! A) B/ O- F9 C, p" u+ M
/ X! |" D6 ?9 g0 o. ~/**
& V3 z4 ^* k, ?# Z$ L * 调整指定节点和其子节点
* H. H O" C3 O) i; x; y * @param tree 整棵树
$ K- h( f7 [/ [$ l9 ` * @param n 数组长度,树的元素个数
& W4 n0 O: q: @ * @param i 要调整的节点的下标3 @) c( \ F( E; T
*/: }6 t+ `9 R* C
private static void heapIfy(int tree[], int n, int i){
/ N/ j/ V. C& }- I" t6 F2 J6 p if(i >= n){4 h$ a5 U1 a" N( i7 p$ m+ L- q) c4 J
return;
9 x1 n( C% c v }( k2 m/ j! B) }: t
int c1 = 2 * i + 1;//左子节点的下标
! N6 [' R' T. T% X; u int c2 = 2 * i + 2;//右子节点的下标3 k6 X2 I, t) L4 V8 k2 I& U
int max = i;//假设父节点是最大的
# C+ Q: C7 `! D. m! |0 a' ]( a7 q //找出最大值的下下标( v' L+ E9 K; @/ b) Y4 c* ^
if(c1 < n && tree[c1] > tree[max]){
2 N1 Z0 N: J/ }/ c+ T; ?5 Y max = c1;
0 K* _( W; E! R' K0 P! [7 Y2 D' j }
' S. J5 H$ i: p2 z% ? if(c2 < n && tree[c2] > tree[max]){5 Y7 t( b3 y1 n9 e
max = c2;/ |: U$ d0 A9 V1 s
}5 L! ]+ w, g, ?9 S
if(max != i){//如果最大值不是父节点,需要做换位置操作" ^9 c* r; @) `: Z* |; r# U
swap(tree, max, i);) D% U9 J! v; ~' ] [. K! _9 N- W. U
//此时,i节点被换成最大值了,符合大顶堆的性质
- c6 _1 `+ Y0 j( d3 l$ |9 r7 ~ //但是换到下面的节点不能保证比他的两个子节点都要大# W+ L# c. C& @) C: Q
//所以被换位置的节点继续调整
1 o! J, c$ S* ~. H% B heapIfy(tree, n, max);
/ R( Q* Z2 Q; s; H& Z }/ C2 o& G j# q8 B5 _* l
}- O: U! c! {$ Z) ?9 s/ P
- \; {3 G: ^/ z1 l- I/**
8 s: O- v6 E( b * 完整构建大顶堆$ R& N4 I+ G6 j) ]3 R9 O8 E; v$ p
* @param arr 用于构建堆的数组
+ t( A% u+ z! k; D * @param n 堆的最后一个节点的下标
" g0 E4 _- e0 G! ~- Q */
W5 {" X1 G# G( K$ y4 _# b2 sprivate static void buildHeap(int arr[],int n){) T" s3 |5 D' t; B4 M) A" i2 y0 [
int lastNode = n - 1;
+ d7 p. v8 K9 J& X3 | { int parent = (lastNode - 1) / 2;& c+ k/ ]2 p& e
for (int i = parent; i >= 0; i--){$ K, \7 N6 g. z; U3 D9 Q1 { _
heapIfy(arr, n, i);1 }3 F" ~0 o6 I
}. j& _7 t0 i' q; T
}4 p) B) Z1 M. H
; A7 c" M$ ^8 S/**
2 b5 q+ x [# w% @) I! y * 堆排序
* u9 B f$ y2 l# k2 y, f& w * @param arr 待排数组
) ^0 O2 _$ _' z" Y( [* ~ */, [+ w. E) v# ^0 c, S7 d( }
public static void sort(int arr[]){, `0 l8 @& d* {& j4 Y
buildHeap(arr, arr.length);//先构造大顶堆! O- v |1 m+ S; D
//每次构建堆后将根节点和最后一个节点进行交换 k% u$ `7 F9 a
//然后砍断最后一个节点( L/ E6 l1 t0 Z
//所以从最后一个节点向前循环
# s6 ^# b0 k; Y) b% J( f% U/ h for (int i = arr.length - 1; i > 0; i--){
$ ?$ o _$ [/ l; L; n swap(arr, 0, i);
) w+ L9 t8 V7 n0 O3 J4 A heapIfy(arr, i, 0);; P: T; I: n4 Q6 G) E, ^
}3 G0 k3 c( w. O5 ^2 o1 {' a
}, s# _7 v. m }6 v
————————————————
) ~: U) F6 @$ ~0 o2 k版权声明:本文为CSDN博主「qq_34912889」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
/ z9 N" M( i9 f% {; s原文链接:https://blog.csdn.net/qq_34912889/article/details/105690644% b C/ I/ N5 V, }% ^
4 D7 E1 |9 t5 `9 V5 Q
`4 g E }8 p% g3 L. S- N. w# T
|
zan
|