- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 81
- 收听数
- 1
- 能力
- 120 分
- 体力
- 540731 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 167598
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 5324
- 主题
- 5250
- 精华
- 18
- 分享
- 0
- 好友
- 163
TA的每日心情 | 开心 2021-8-11 17:59 |
---|
签到天数: 17 天 [LV.4]偶尔看看III 网络挑战赛参赛者 网络挑战赛参赛者 - 自我介绍
- 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
群组: 2018美赛大象算法课程 群组: 2018美赛护航培训课程 群组: 2019年 数学中国站长建 群组: 2019年数据分析师课程 群组: 2018年大象老师国赛优 |
! V$ f1 ^: h; w5 ^* ~
十大经典排序算法之堆排序(Java语言)
: g( W% [: ?% C文章目录; b% k/ v1 H3 l% H
( _! s9 g# o0 b0 \% t什么是堆
; k0 g# I( v4 h) M如何进行堆排序呢+ |! _- t# k1 i' ?
用数组构建一个堆
: [$ b6 h6 c: R* g1 ]/ @上代码$ f! ~2 R. p: U; L
什么是堆
3 s% m B% ]! f! @- \0 K; m5 F0 J% n B* R5 O# [! G
在了解什么是堆之前一定要先了解什么是完全二叉树
% l9 V% k, }/ `% N看一下百度百科的介绍
# z9 _9 f0 H, M0 ~9 E& ?5 F
: @! V: u% B* M% N# M. b" ~* ]若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
) l! @; k+ [; V7 J( l3 D# x E) f; l百度百科拗口版性质介绍,能看懂上面的就行,下面的大概看下
- @2 x8 u( g1 J! {- w4 @0 x9 M& [( C, G
完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
3 |) H1 V9 {, ]! q1 z/ V" W1 q(1)所有的叶结点都出现在第k层或k-l层(层次最大的两层)
1 Y/ x# w, ]! U# D1 F- F1 E(2)对任一结点,如果其右子树的最大层次为L,则其左子树的最大层次为L或L+l。* Y& T9 c% H/ j
一棵二叉树至多只有最下面的两层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,则此二叉树成为完全二叉树,并且最下层上的结点都集中在该层最左边的若干位置上,而在最后一层上,右边的若干结点缺失的二叉树,则此二叉树成为完全二叉树。) ]4 E7 z4 p# E8 S: K/ N
那么在了解到什么是完全二叉树之后,我们再来看什么是堆 Q- s9 p- `2 B4 L4 H+ S
堆有以下两个性质 t! S( k _ p
, _, q$ v8 j" X8 j3 f Q
1 堆中某个节点的值总是不大于或不小于其父节点的值;& N( m; S8 f9 A
2 堆总是一棵完全二叉树。
! A* a5 \2 M9 G& Z* g/ ]其中堆顶就对应二叉树的根, r& d" h$ v0 G9 y6 B [, m' b
+ |; {: _; H4 v& [: E- ^堆又分为大顶堆和小顶堆,根据堆的第一个性质来进行区分
+ T9 y' g9 G4 R0 a. c1 ]
. ]1 v/ O+ c* l当堆中某个节点的值总是大于它的子节点的时候这个堆为大顶堆,反之为小顶堆5 r0 f; d9 w2 M0 q, y+ I: e
如何进行堆排序呢" i$ [' D0 Q! Z7 e2 t6 N
. H/ H$ ~% [- ?, F& N堆排序,其实就是每次构造出一个大顶堆或者小顶堆,然后取出堆顶的值,再将剩下的值重新构造成大顶堆或者小顶堆,最终到堆里的值全部取出来,取出来的数就是排好序的
' m8 x$ I/ c6 h
1 D" _& c& f* ?# k% Q用数组构建一个堆7 L7 ~! s |! v U- N0 ~* K& i
1 J3 o; W. g9 K1 q1 i
因为堆是一颗完全二叉树,所以我们可以用数组来对其进行存储
5 g/ B9 |7 k. m" Z对于用数组存储的二叉树,我们可以用如下方法来定义:/ N4 q( ?6 m, m u$ ?
假设当前节点的下标为 n
6 S% [) Z# |3 `# a
* ]% ~5 }% k) X) \1、那么他的左子节点的下标 2*n + 16 t8 O6 N$ `4 y: O6 e
2、那么他的右子节点的下标 2*n + 26 w! S% N8 t; l" X4 n
3、他左边的节点是 n-1,如果当前节点是第 h 层的最左节点,那么第h-1层的最右节点的下标就是 n-15 x! Z5 l) j$ U& e9 J9 t$ {* z
4、根据1、2可以推出来n节点的父节点是 (n-1)/2,不管当前节点是父节点的左子节点还是右子节点,都用 (n-1)/2就行了,因为整型数字相除小数点后面的会被截断
; s& x8 L" M7 x5 H3 M- j. b那么有了上面四条性质,我们就可以开始动手了' |" t$ e* E/ ?5 w
8 Z3 e. t8 Q5 k& Q
1、假设我们要构建的堆是大顶堆,那么根据大顶堆的性质,任意节点都比它的左右子节点要大,所以我们肯定有个heapify方法,该方法调整指定节点和其子节点的位置,并且继续调整被调整的子节点和孙子节点的关系,直到没有调整或者到数的最底层" y, A# C+ {: A/ O1 y
2、然后我们要有构造大顶堆的方法,构造大顶堆就是从最后一个节点的父节点开始调整,接设最后一个节点的父节点是n,那么我们就将n,n-1,n-2 ··· ··· 0,这些节点逐次,从大到小调用heapify方法,这些节点都调整完成后,大顶堆就构造完成了
! K( ?8 k2 c4 p$ u' q+ H3、接下来就开始将堆顶和堆尾互换,并砍断堆尾的操作了,由于互换之前,这是一个符合条件的大顶堆,但是换完只有只有一个堆顶这里不满足了,那么我们重新调整一下堆顶的三个元素就可以,还是调用heapify方法,这个方法会自上而下的重新调整堆,使其成为一个大顶堆
- d) S$ s! s( j3 b& c# B- x C# _. D6 v/ I* T
堆排序的性质
6 s. J% L! ~. r( {: t% w* S. v3 E; x5 G% @
中文名称 英文名称 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性/ ` n) A9 r5 b# G+ B
堆排序 Heap n*logn n*logn n*logn 1 不稳定1 [6 y4 x/ ?- m6 ~
上代码3 \, g" ?! E v6 v" D4 K3 D) m
4 \$ J1 \/ V! z( U" \8 X. Q
/**+ l* ^& O/ n/ s8 F& c
* 交换第n和m个元素
8 f% ^' j2 Y! G( G2 n! S/ i' M */
; R) N# `9 {$ d5 f6 D: Fprivate static void swap(int arr[], int n, int m){
* J4 O3 o! _# V( x) l int temp = arr[n];
1 H$ K/ f) X$ @# i. @. \ arr[n] = arr[m];
- Q4 n2 R% c7 `4 L6 r& S arr[m] = temp;/ j9 E9 F' O F
}$ u9 W+ Q: M# l+ ^ J4 B
3 ]/ M+ Z, ?! i; j. E2 N8 d/**/ I3 h8 o+ m0 O/ I% ]' N! L/ G9 w0 Q
* 调整指定节点和其子节点8 C! H: m# t2 s: J
* @param tree 整棵树
% b9 O0 q- A' c# E * @param n 数组长度,树的元素个数
) A) J* a7 N& m * @param i 要调整的节点的下标. k6 z3 U: u4 U& r3 x
*/
( u( y; |' N, w, o6 C& Lprivate static void heapIfy(int tree[], int n, int i){
: h! @6 T( t, i$ { if(i >= n){
/ W8 m. `, c8 x# G o$ O' j return;& u8 ~- [0 b# J
}9 q7 n7 w% m* Q0 j$ e
int c1 = 2 * i + 1;//左子节点的下标
, P; } P# F, r6 }8 k. Y1 B. ^ int c2 = 2 * i + 2;//右子节点的下标
5 G1 s3 R! ^6 u4 {$ v) m int max = i;//假设父节点是最大的
$ c: g6 a# o" D$ c9 \+ Q6 v //找出最大值的下下标
- ^' j+ e8 O; C) j& i, Y. i0 k2 u( Q/ d if(c1 < n && tree[c1] > tree[max]){
/ [" |6 ?' {, o max = c1;
& ?6 x- {2 S" l1 F% w/ Q- q' f/ \ }
: D- s, g' [2 K6 P/ X5 x- Z if(c2 < n && tree[c2] > tree[max]){
; ~1 z; s9 l, t) f max = c2;
3 H3 @' Y% V" r/ _9 t G }$ W0 m I! H/ k8 _ ^5 y
if(max != i){//如果最大值不是父节点,需要做换位置操作& l$ u6 n; R a% o+ q
swap(tree, max, i);
; J" W) e) e/ @( D: ` //此时,i节点被换成最大值了,符合大顶堆的性质" R5 n7 Q( A: U4 \4 a3 o a
//但是换到下面的节点不能保证比他的两个子节点都要大
/ f( I) r1 X+ Z7 P6 R4 `/ A* c/ j ~ //所以被换位置的节点继续调整
& n! d0 `+ R$ P1 Q heapIfy(tree, n, max);; o- `9 G" ~9 n# L% l! H: I
}
. X' I/ u. g' c! E}) n8 U: B0 Z- w8 B! @
: Z6 f3 y) \5 f0 c
/**
- x+ a! w7 _' [0 P4 t$ c8 `: U * 完整构建大顶堆8 q4 V" A4 Y1 J% v( H: C* c# K/ E
* @param arr 用于构建堆的数组
' Z2 T9 {$ `/ m# |( S1 T* W+ u * @param n 堆的最后一个节点的下标 M3 f! \7 |! E& O5 E7 b
*/
! |+ D7 J$ P' hprivate static void buildHeap(int arr[],int n){; I/ d6 E( B P
int lastNode = n - 1;) {6 | y7 o: H5 H
int parent = (lastNode - 1) / 2;
* L: Z% k- ]: Y; d for (int i = parent; i >= 0; i--){
0 Z% k4 ~5 J! E( n heapIfy(arr, n, i);
% ?$ r6 t$ B- `' @! u, `: M }
$ b8 g# l2 i- l, b$ f3 U}' `1 s: f+ W1 o; [, D4 N
9 a/ o" R: j8 o h4 e! f
/**
, @( Q9 s+ R5 a( t0 ^$ \/ t * 堆排序% E% A# l; ?9 B$ M3 S" ~
* @param arr 待排数组; M9 g1 L9 \& N! O% }* W
*/! G3 D+ i' Z5 N+ L1 y7 G4 p
public static void sort(int arr[]){: Z' k, Y+ U0 P$ F
buildHeap(arr, arr.length);//先构造大顶堆
r( T, y" w9 N$ ^" [$ W% b" q //每次构建堆后将根节点和最后一个节点进行交换 R: t6 L; ? o3 m% b% i9 h N& I
//然后砍断最后一个节点0 P5 C# |8 p9 b8 z
//所以从最后一个节点向前循环
d1 [, M' U3 Y k; w% e( z$ [ for (int i = arr.length - 1; i > 0; i--){1 A& F6 M5 a F
swap(arr, 0, i);
5 Q" P% |( ?8 s, [6 A- O heapIfy(arr, i, 0);
8 Q d. z2 A5 M& \' V4 ?+ x }
! u2 E! m3 c& t5 ^/ {3 a/ u, S7 D}
' q8 S6 T4 Y6 p4 X: Z- W; I————————————————
* F4 F, B T& |4 ~& G版权声明:本文为CSDN博主「qq_34912889」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。" s6 N5 r/ `+ l, p; a( E4 _
原文链接:https://blog.csdn.net/qq_34912889/article/details/105690644% T5 a+ V1 T+ p/ |
. I7 e( K3 @) K2 b0 O; ~2 {
- A( _2 f) I( b2 V. J, M$ W |
zan
|