- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 82
- 收听数
- 1
- 能力
- 120 分
- 体力
- 563412 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 174246
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 5313
- 主题
- 5273
- 精华
- 3
- 分享
- 0
- 好友
- 163
TA的每日心情 | 开心 2021-8-11 17:59 |
|---|
签到天数: 17 天 [LV.4]偶尔看看III 网络挑战赛参赛者 网络挑战赛参赛者 - 自我介绍
- 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
 群组: 2018美赛大象算法课程 群组: 2018美赛护航培训课程 群组: 2019年 数学中国站长建 群组: 2019年数据分析师课程 群组: 2018年大象老师国赛优 |
+ M0 I' x6 d$ g$ m
十大经典排序算法之堆排序(Java语言)
" r/ y2 K% ]* M* |; i7 f6 T文章目录
: r0 T" b0 V" \5 Q, @
* d2 w& A% F- S) b9 u- ?% \* ]9 {什么是堆
3 }8 r; x1 f& S5 a如何进行堆排序呢/ x0 R* T8 n3 d
用数组构建一个堆
4 @. j% z$ q1 I) S t }上代码' J0 u/ j# l# ^& x! B
什么是堆
- c4 A) C$ j+ s/ n0 ] ?, F o
/ ^* o4 t! m- S; @7 U/ ~6 n7 n在了解什么是堆之前一定要先了解什么是完全二叉树. ^4 K6 E' Y7 B8 _( p0 K
看一下百度百科的介绍
' g- ^$ t7 v8 q
$ f$ w4 |; v5 M3 o若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
7 m( c" N k3 ~# {# G9 ^百度百科拗口版性质介绍,能看懂上面的就行,下面的大概看下
6 g! Y. y& L; \: \! w- g+ Q5 O" P0 r( g ~
完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。' u9 I' ?( Y. W, f% C8 T' s
(1)所有的叶结点都出现在第k层或k-l层(层次最大的两层)
' |' H3 i* P4 {# C/ C5 P6 F(2)对任一结点,如果其右子树的最大层次为L,则其左子树的最大层次为L或L+l。
d/ l8 z; X$ r+ j一棵二叉树至多只有最下面的两层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,则此二叉树成为完全二叉树,并且最下层上的结点都集中在该层最左边的若干位置上,而在最后一层上,右边的若干结点缺失的二叉树,则此二叉树成为完全二叉树。
. C& ]7 [" R3 K! w3 ?0 g9 n, g那么在了解到什么是完全二叉树之后,我们再来看什么是堆
2 w/ e( \2 g8 V( D+ ^ }堆有以下两个性质
2 s2 X% E- ^/ F1 M0 W" J( D9 _, \5 i5 W6 e" N; T! T3 u+ }
1 堆中某个节点的值总是不大于或不小于其父节点的值;
! r1 I& ]$ q2 e) y& R2 堆总是一棵完全二叉树。, E) s3 \ W+ A
其中堆顶就对应二叉树的根
( O) Q1 G0 K0 @" ~3 J: I c. H8 |- N: d$ Y) r" y
堆又分为大顶堆和小顶堆,根据堆的第一个性质来进行区分! |) H# {4 Z1 [( A' S) |
4 N8 d; W1 W: j8 Z5 O ?当堆中某个节点的值总是大于它的子节点的时候这个堆为大顶堆,反之为小顶堆" u( X& y: Q5 Y! |6 u# ?
如何进行堆排序呢8 }; W6 [& K5 b3 I) Q# L% v% W( O
, m0 o3 _4 Z+ z$ @ e堆排序,其实就是每次构造出一个大顶堆或者小顶堆,然后取出堆顶的值,再将剩下的值重新构造成大顶堆或者小顶堆,最终到堆里的值全部取出来,取出来的数就是排好序的6 U% I5 |/ Q6 |* i( z9 w
: d3 R u6 ^+ W7 I& @
用数组构建一个堆$ [- N1 d5 m& E1 S# V
+ Y# N: H% r% X$ s6 v
因为堆是一颗完全二叉树,所以我们可以用数组来对其进行存储
4 z* t7 d; b3 T7 ]3 t5 X, X对于用数组存储的二叉树,我们可以用如下方法来定义:; U! v2 w: Q( [$ v6 {( w5 [
假设当前节点的下标为 n, G, z9 ?% D @# s
0 s6 E4 r7 C2 p1、那么他的左子节点的下标 2*n + 1
" V" m" {- T& A& `2、那么他的右子节点的下标 2*n + 2
% D* r$ ~- W. C0 m3、他左边的节点是 n-1,如果当前节点是第 h 层的最左节点,那么第h-1层的最右节点的下标就是 n-12 d; Z/ Z" V' F
4、根据1、2可以推出来n节点的父节点是 (n-1)/2,不管当前节点是父节点的左子节点还是右子节点,都用 (n-1)/2就行了,因为整型数字相除小数点后面的会被截断3 D) o( f4 [6 @& f- g
那么有了上面四条性质,我们就可以开始动手了1 Y) F- Z+ y* r6 Y) I9 V
1 D3 B; ]) O9 T G- C. @# E
1、假设我们要构建的堆是大顶堆,那么根据大顶堆的性质,任意节点都比它的左右子节点要大,所以我们肯定有个heapify方法,该方法调整指定节点和其子节点的位置,并且继续调整被调整的子节点和孙子节点的关系,直到没有调整或者到数的最底层
4 E; l0 p" D( L, c# S. L9 _- P+ [2、然后我们要有构造大顶堆的方法,构造大顶堆就是从最后一个节点的父节点开始调整,接设最后一个节点的父节点是n,那么我们就将n,n-1,n-2 ··· ··· 0,这些节点逐次,从大到小调用heapify方法,这些节点都调整完成后,大顶堆就构造完成了( R. @ a. A- C$ G
3、接下来就开始将堆顶和堆尾互换,并砍断堆尾的操作了,由于互换之前,这是一个符合条件的大顶堆,但是换完只有只有一个堆顶这里不满足了,那么我们重新调整一下堆顶的三个元素就可以,还是调用heapify方法,这个方法会自上而下的重新调整堆,使其成为一个大顶堆
4 `4 X- G$ }- i) W+ D. c1 H$ r. M
* L! y6 `% K5 v) n- N堆排序的性质 `" t' \& @2 w7 X9 z9 b* M2 \
8 B, a& c* ]) a% }) T
中文名称 英文名称 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性
% a" j$ l$ w* v$ Y堆排序 Heap n*logn n*logn n*logn 1 不稳定
& A: p1 \6 `$ L- A9 ?上代码7 H$ c' Y. [# `
. c! e+ @8 l W9 d, C, \8 d
/**
( d3 S( O% c' b7 _1 r * 交换第n和m个元素
& x5 H& X' m' _1 H( R d! F- k# N" T */
! S {) ~0 E5 x' nprivate static void swap(int arr[], int n, int m){
9 Z" y4 V/ d2 x) t int temp = arr[n]; B a5 l4 V/ }: f2 h7 L1 G3 i0 C
arr[n] = arr[m];5 {0 K' o8 j3 v6 e) a5 Y
arr[m] = temp;
, ?/ q6 A2 G# z) s- s}
. z8 B6 |( X) i9 _1 y
! z' E/ y9 a2 d' S0 ^7 u7 Z/**
& B& j' d& J1 A9 R * 调整指定节点和其子节点
4 r+ m& H9 [. e* a * @param tree 整棵树/ U. g5 Y6 H7 g* {, {) u$ D
* @param n 数组长度,树的元素个数( |' Z, ~" }" L' h9 v. e
* @param i 要调整的节点的下标+ b9 O; c7 \+ }0 u
*/2 e" h, F& F# D! w
private static void heapIfy(int tree[], int n, int i){
j1 N/ Z( u- O3 \5 ~ if(i >= n){
, i) A: K8 h. T* C, l return;" D( }2 B4 d4 F+ m3 [+ I
}
& |& D( E1 P4 T7 y int c1 = 2 * i + 1;//左子节点的下标
9 C* ` U- m# ^- Q1 y% V- ?) N int c2 = 2 * i + 2;//右子节点的下标
) M' i% u2 B( N. T |1 Z) B int max = i;//假设父节点是最大的/ k1 v1 ^% K- b( P3 [' z
//找出最大值的下下标- `, Y' W9 [- k! g) C; n2 T
if(c1 < n && tree[c1] > tree[max]){8 ?& P3 n8 b/ x% ~) e- R
max = c1;
' r5 w+ C' e# W }
, f4 a& {$ k: q7 x7 n6 n; Z if(c2 < n && tree[c2] > tree[max]){- E. N0 f6 l- s) d3 T- e) h2 f
max = c2;
; k. }) t( O) B6 q2 \; n0 t7 j% z }
, F* h* s' _8 t$ [0 h3 `, Y if(max != i){//如果最大值不是父节点,需要做换位置操作
+ b$ n, D' h6 R% ~7 j( {$ H swap(tree, max, i);7 y& r3 J% p; ` M5 `' M
//此时,i节点被换成最大值了,符合大顶堆的性质& U V. c9 o" O7 \: G. a5 q) d% D
//但是换到下面的节点不能保证比他的两个子节点都要大
9 M3 Q/ Q( a) t1 @" O //所以被换位置的节点继续调整
6 b+ S; |9 u3 ]3 Y heapIfy(tree, n, max);. S2 B: l6 E* `5 [* @
}
$ ?6 w3 Q4 C8 r D- i/ D0 J}2 q& u! Z/ S9 D( W; _( [' e
4 D+ \* j) Y2 K9 W
/**
0 F T) u0 s( X * 完整构建大顶堆4 F- w" I7 a A5 B, d
* @param arr 用于构建堆的数组" Z+ g* y4 R8 D0 b1 W
* @param n 堆的最后一个节点的下标# d8 u' C: R# I$ ]% K. g% C$ x
*/& |$ c" r q" A& E4 z6 j! ]
private static void buildHeap(int arr[],int n){
, l; _. B& k; z. [# Y6 |1 f4 z int lastNode = n - 1;) r5 D: Y, ?3 ~( W
int parent = (lastNode - 1) / 2;
0 @8 `$ r1 f& s, M1 b# Y3 @ for (int i = parent; i >= 0; i--){
+ `: _( o/ d" }, s" ^ heapIfy(arr, n, i);/ W% U9 T0 g6 M$ ~1 \ z# ^( p- `6 f
}! V3 k1 y6 G# i( ~# g4 u. `# O
}
. O) ~4 R& y2 T' { @; c! e4 P9 r# h+ C
/**
, ]6 P! u; H: j4 i/ q7 l * 堆排序( f& k. D* j; Y4 p( q0 _- t H
* @param arr 待排数组
- S4 R: }( ^9 \0 i+ f; ?6 R+ r */+ X) \, v$ @7 C% q* _
public static void sort(int arr[]){, q& a, U. Y2 [/ z
buildHeap(arr, arr.length);//先构造大顶堆
! Z# K. a7 U7 Z: [ //每次构建堆后将根节点和最后一个节点进行交换$ Z. c( u, O& Q; n# A2 _% m
//然后砍断最后一个节点# f8 D4 f4 \1 a' B
//所以从最后一个节点向前循环
& {3 E. y8 P. n) L% F) I for (int i = arr.length - 1; i > 0; i--){
$ b# s: o3 ^( J) E, K* }/ B2 B swap(arr, 0, i);
7 }/ {" q$ `. n! L- w$ c4 U2 U heapIfy(arr, i, 0);$ I0 P, u4 y, I; F' W. x
}8 j% w8 X3 ?; {+ d% p, N
}
- r9 j& g# ^. Z$ W. a" \————————————————7 o" w5 K+ _6 p4 P4 G4 `
版权声明:本文为CSDN博主「qq_34912889」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。, k" p- P) d& ^
原文链接:https://blog.csdn.net/qq_34912889/article/details/105690644
' t8 ^" m0 c [: Q: G t; j
2 i7 g/ g. s6 r+ T; P. J& ]0 A+ {# G3 x9 ~( E
|
zan
|