- 在线时间
- 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年大象老师国赛优 |
! r7 G* N1 q$ G7 ?
十大经典排序算法之堆排序(Java语言)2 K; {) O8 E/ V$ p
文章目录' [! I# o; ~- ^- v
) X! Z1 h4 q6 z' c4 t4 d: @- O; t* L: o
什么是堆6 Y; ~3 _1 F" U3 C9 a# D; F0 b
如何进行堆排序呢' b- G' q; x! |) j, [8 K E
用数组构建一个堆
0 ^ b- G0 _$ ^" g+ Z& W上代码
, l6 e& `9 Z4 p( O q3 a4 ^什么是堆" R5 i; n* e! P0 i
% |4 i5 E6 D4 D# r, O& V3 k( U0 G在了解什么是堆之前一定要先了解什么是完全二叉树3 h# l$ c0 z1 p# [
看一下百度百科的介绍
" d0 [$ i# w1 a3 h
% v4 p$ t* ~% ^/ a若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
5 J* ~+ Y+ [; z( i百度百科拗口版性质介绍,能看懂上面的就行,下面的大概看下/ u0 @( y& `, {) Z( p1 A! p
1 G" w2 w7 s& M, q( T4 `完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
' V# @& ^$ {! x M5 Z e, ?(1)所有的叶结点都出现在第k层或k-l层(层次最大的两层)
) x; F- A" C. I(2)对任一结点,如果其右子树的最大层次为L,则其左子树的最大层次为L或L+l。* j- Z% O. |, z0 c. H. K: y
一棵二叉树至多只有最下面的两层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,则此二叉树成为完全二叉树,并且最下层上的结点都集中在该层最左边的若干位置上,而在最后一层上,右边的若干结点缺失的二叉树,则此二叉树成为完全二叉树。& y$ U2 e3 \8 C; @, H
那么在了解到什么是完全二叉树之后,我们再来看什么是堆, U8 r6 g W- V! y" A. Z) K
堆有以下两个性质8 K1 R& r* z6 h/ |
9 X" ~3 X9 y, N* n' P5 C" o- n
1 堆中某个节点的值总是不大于或不小于其父节点的值;
s% j% o# E: O" m4 Q2 堆总是一棵完全二叉树。
& A1 `7 n% ]6 @: Q4 K其中堆顶就对应二叉树的根' M$ B9 U# g* ]( J
0 U& K: q, O9 B G0 V# h; P堆又分为大顶堆和小顶堆,根据堆的第一个性质来进行区分
a2 N9 Q( B" y
- i: n! _9 {( u, a# w. U当堆中某个节点的值总是大于它的子节点的时候这个堆为大顶堆,反之为小顶堆
9 v2 v( L$ y# ]" t% Q如何进行堆排序呢7 j# J: j# \( Z- T/ O4 S5 X
N& y5 W5 e8 S0 H) K
堆排序,其实就是每次构造出一个大顶堆或者小顶堆,然后取出堆顶的值,再将剩下的值重新构造成大顶堆或者小顶堆,最终到堆里的值全部取出来,取出来的数就是排好序的9 M# f0 P$ x) @! s l* v
1 R5 |: g w, x6 a& ]1 A8 ?用数组构建一个堆
" \, ? d+ ~0 j: h( I1 U
' e ]6 S% ]+ f d& g因为堆是一颗完全二叉树,所以我们可以用数组来对其进行存储
: T( o3 ~8 }3 E对于用数组存储的二叉树,我们可以用如下方法来定义:
4 P6 B+ d$ j1 r, `3 F假设当前节点的下标为 n0 y* `4 E- ^9 z3 F; i) F' P) O
9 |& {) D l( k; u% Z
1、那么他的左子节点的下标 2*n + 13 l# Q9 G9 h# C4 g, d# I/ P
2、那么他的右子节点的下标 2*n + 2! p6 D. o& j' w9 z' h& ?! ?* t
3、他左边的节点是 n-1,如果当前节点是第 h 层的最左节点,那么第h-1层的最右节点的下标就是 n-1% A; ]8 b8 i) Y: M4 g- s8 S: ]+ }
4、根据1、2可以推出来n节点的父节点是 (n-1)/2,不管当前节点是父节点的左子节点还是右子节点,都用 (n-1)/2就行了,因为整型数字相除小数点后面的会被截断, v3 k- g% |% X2 X" M- t
那么有了上面四条性质,我们就可以开始动手了& P% W5 |+ t3 Y
. L" w+ A# R! q: t6 H
1、假设我们要构建的堆是大顶堆,那么根据大顶堆的性质,任意节点都比它的左右子节点要大,所以我们肯定有个heapify方法,该方法调整指定节点和其子节点的位置,并且继续调整被调整的子节点和孙子节点的关系,直到没有调整或者到数的最底层+ u+ ]3 b. q: r/ C+ b% {
2、然后我们要有构造大顶堆的方法,构造大顶堆就是从最后一个节点的父节点开始调整,接设最后一个节点的父节点是n,那么我们就将n,n-1,n-2 ··· ··· 0,这些节点逐次,从大到小调用heapify方法,这些节点都调整完成后,大顶堆就构造完成了
( {2 O- i* z K, d8 r3、接下来就开始将堆顶和堆尾互换,并砍断堆尾的操作了,由于互换之前,这是一个符合条件的大顶堆,但是换完只有只有一个堆顶这里不满足了,那么我们重新调整一下堆顶的三个元素就可以,还是调用heapify方法,这个方法会自上而下的重新调整堆,使其成为一个大顶堆
1 N# J# u" e$ G/ p' c0 [4 Y: y, r3 Y+ o! _) _
堆排序的性质
/ K, ^; p1 q0 g- S6 g7 W' g. ?, z: y: C" k% I
中文名称 英文名称 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性
& c/ ~% z) T$ }堆排序 Heap n*logn n*logn n*logn 1 不稳定
! @+ T; L% [. g2 x上代码6 r- _- n. w# Z7 h& a# t1 S0 I* A" I
) J4 C, u: J1 }1 M0 t& J# Y- o
/**
5 c5 ^: x4 |6 t * 交换第n和m个元素
6 u- @& y3 R: b% s */
# }0 X* Z9 o0 O- z# h% v2 q' `private static void swap(int arr[], int n, int m){6 e: S9 i$ ~: T8 J/ D
int temp = arr[n];$ h B1 {2 u# U- U
arr[n] = arr[m];' r$ c8 F) F* L# ^3 b Z" ]0 U
arr[m] = temp;
8 r6 s% R5 R& l$ ]. d( k/ d; z}
# T+ }2 g, \% g; f( l) M. H9 n. w( f
/**
/ w% ~2 c' M8 G* h5 H c5 C * 调整指定节点和其子节点" f) |5 M9 P$ m& ^
* @param tree 整棵树: P% K% Q6 y0 p7 q% Y- w
* @param n 数组长度,树的元素个数
/ ~6 N. }9 M1 U9 Y2 ` * @param i 要调整的节点的下标& l( c L3 A: l3 q& S6 n
*/& h; d4 \0 P$ e1 B6 L
private static void heapIfy(int tree[], int n, int i){2 U$ ]" i& `, N' O4 {7 b9 v
if(i >= n){
) h5 D! `. n, D' G return;. \. g$ T& G8 w v% P
}
# c5 j5 k' a& j5 m int c1 = 2 * i + 1;//左子节点的下标
0 v" E0 |) I& R( R, o& ~3 H# r int c2 = 2 * i + 2;//右子节点的下标
- a# A3 G _, _3 V1 O( l; y0 s0 T int max = i;//假设父节点是最大的: P3 j, B5 y Z; N& K4 s
//找出最大值的下下标% ^/ D0 g# k5 D; _" H7 Z% y+ M
if(c1 < n && tree[c1] > tree[max]){9 Q& _0 V' Q" e' w5 W8 |8 b
max = c1;% ]' J: o8 V$ X9 {# N( Q4 J3 A
}
: u) U+ R$ z3 J8 N6 U4 h+ t if(c2 < n && tree[c2] > tree[max]){
2 O; E! y. L) p% e. w, ^ max = c2;! m# E; B G% K3 R- C$ \' t
}4 k8 a' I7 s# O/ h) s( \" ?2 o! f
if(max != i){//如果最大值不是父节点,需要做换位置操作
7 V: K) O$ `, x9 V! g' ` swap(tree, max, i);. e+ G+ o B' r- ~0 i
//此时,i节点被换成最大值了,符合大顶堆的性质
0 ?% ~7 A. _* r8 d! H //但是换到下面的节点不能保证比他的两个子节点都要大
" Y+ d4 n* ^( E2 X7 v4 J //所以被换位置的节点继续调整
0 O2 [% b! x& } heapIfy(tree, n, max);+ ~: I) H( ^+ I7 @4 d' m
}
, w9 V0 e! K: c9 z}+ b: K4 x7 G# H9 F% ^& Y- F
5 V/ l9 w" t/ R* L) x1 I/**& v- y5 `4 N8 O
* 完整构建大顶堆
) w! }9 g9 T9 B * @param arr 用于构建堆的数组
, l. X9 q1 B1 t3 u4 S# [2 ~ * @param n 堆的最后一个节点的下标
, m2 K5 z9 ?; |5 ^: o P2 h */, |1 `$ n9 c# V3 l
private static void buildHeap(int arr[],int n){# H8 v5 ?) M# r0 F
int lastNode = n - 1;+ L* |" V% C( d3 R
int parent = (lastNode - 1) / 2;
( p! [* R7 r3 i. ?, V; W( l for (int i = parent; i >= 0; i--){( O4 O/ ]9 X, ~' e3 {2 U
heapIfy(arr, n, i);, \9 ~" j6 `5 g4 j3 O, m
}1 M8 T( {) E# z: n3 k
}
2 v6 H; j0 p3 a. ^9 F: g2 N, K
/ C, ~7 a. F1 ~" q/**
: j- K O2 N5 p8 ? * 堆排序
U6 C: y) y* Q% {1 l * @param arr 待排数组
2 M" b) B6 O! J2 b */7 L) d/ p* w- x) {2 ^
public static void sort(int arr[]){: U7 B( q* a @0 q# K ~
buildHeap(arr, arr.length);//先构造大顶堆' t* d/ G1 W7 ]; D1 m2 ?$ S
//每次构建堆后将根节点和最后一个节点进行交换
7 w( V' Q' C1 c& z1 P$ K //然后砍断最后一个节点* {6 F: M3 m4 q$ Y$ a0 `- s
//所以从最后一个节点向前循环; I- m3 S0 y- g% W9 L9 b1 n
for (int i = arr.length - 1; i > 0; i--){
# E) Y- w' ]$ _! t' O swap(arr, 0, i);- ^( s# y v8 D8 |7 I
heapIfy(arr, i, 0);
5 d8 Q( V' A, ^: ?0 b }7 V" j- V* w- v
}
- w6 K% p' {' M7 Y/ t————————————————) P4 ^6 u& ^6 \( `7 b6 ^" P, T% `
版权声明:本文为CSDN博主「qq_34912889」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
" U$ f0 L$ X% p: o; \3 a" U原文链接:https://blog.csdn.net/qq_34912889/article/details/1056906444 {' [( z& H8 L" d* O
9 ^7 u, e, C) Z9 i# Q; U! y( R6 N$ k' C2 o- C3 t6 j
|
zan
|