QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1323|回复: 0
打印 上一主题 下一主题

十大经典排序算法之堆排序(Java语言)

[复制链接]
字体大小: 正常 放大
杨利霞        

5273

主题

82

听众

17万

积分

  • TA的每日心情
    开心
    2021-8-11 17:59
  • 签到天数: 17 天

    [LV.4]偶尔看看III

    网络挑战赛参赛者

    网络挑战赛参赛者

    自我介绍
    本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。

    群组2018美赛大象算法课程

    群组2018美赛护航培训课程

    群组2019年 数学中国站长建

    群组2019年数据分析师课程

    群组2018年大象老师国赛优

    跳转到指定楼层
    1#
    发表于 2020-4-23 15:00 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta

    5 S6 q1 k6 ~3 B9 k' j, s十大经典排序算法之堆排序(Java语言)
    8 `2 ^' j1 Y3 P2 C# w! V文章目录
    * H- J2 k& |# E: l2 [# F2 l( n% h6 S/ x( f4 z' p  p4 k
    什么是堆, O% f) o. W" R- h% s
    如何进行堆排序呢
    0 v' v" U) h* ?6 J* m7 D5 f/ g5 @用数组构建一个堆( ~5 Y! Z) i6 c( ]; H; y
    上代码
    0 A  k+ E' K8 @9 w/ S什么是堆; b! l; E" f$ P6 ?( m! @  s3 u

    # s1 W# r' [& B1 q/ r在了解什么是堆之前一定要先了解什么是完全二叉树3 U, A8 }* A2 f
    看一下百度百科的介绍" g( H! H- D) b- h/ U& t$ V6 j8 d
    # U0 l$ e/ X1 k
    若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
    , D& t8 t3 z9 G百度百科拗口版性质介绍,能看懂上面的就行,下面的大概看下
    - L6 g% L( P5 s9 ]% p& G; W4 ]; D' U" G, }" e* M
    完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
    : X5 P3 c- ?& D3 b; `/ J6 k. b  p(1)所有的叶结点都出现在第k层或k-l层(层次最大的两层)
    / O0 n( J- }: X- G# z5 }(2)对任一结点,如果其右子树的最大层次为L,则其左子树的最大层次为L或L+l。
    - L4 j4 r5 A' t$ _, H一棵二叉树至多只有最下面的两层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,则此二叉树成为完全二叉树,并且最下层上的结点都集中在该层最左边的若干位置上,而在最后一层上,右边的若干结点缺失的二叉树,则此二叉树成为完全二叉树。
    8 x! l+ B7 r' x那么在了解到什么是完全二叉树之后,我们再来看什么是堆
    7 D2 j( E0 O% t/ w" E0 y* L堆有以下两个性质9 F9 _6 l% [2 O7 z7 J
    # n7 E2 J& b9 _! e6 s: _
    1 堆中某个节点的值总是不大于或不小于其父节点的值;
    9 G) a3 q4 p  R& R2 堆总是一棵完全二叉树。8 N: L- y  g. C2 c5 }& {2 P0 q
    其中堆顶就对应二叉树的根
    ! S# p% Q% J" U' g! `7 m) d1 z4 c( F; `& w# ]: Q
    堆又分为大顶堆和小顶堆,根据堆的第一个性质来进行区分$ I7 A, W7 Y' P1 B/ q$ c$ D$ ]
    $ u0 i0 ]! p0 J% e1 m. q+ @
    当堆中某个节点的值总是大于它的子节点的时候这个堆为大顶堆,反之为小顶堆& i! ^( j( z, w/ E% W
    如何进行堆排序呢( D# s5 i+ l% Q$ w3 \
    7 Z+ f- L% k& W2 \! _. _
    堆排序,其实就是每次构造出一个大顶堆或者小顶堆,然后取出堆顶的值,再将剩下的值重新构造成大顶堆或者小顶堆,最终到堆里的值全部取出来,取出来的数就是排好序的0 o, j7 B0 _$ k, d

    / r/ H: O7 q2 U9 |用数组构建一个堆! E% w' _7 H2 o5 ~" a! M1 w0 n8 h

      j( ], m; h2 V/ I% z. H1 G( r因为堆是一颗完全二叉树,所以我们可以用数组来对其进行存储
    8 |# T; u0 w* A: m对于用数组存储的二叉树,我们可以用如下方法来定义:
    + _0 \* ]. n! U8 c0 B4 ^6 k假设当前节点的下标为 n( s& V5 Q) f; }% t( Y5 K; A0 P- r
    - B( K- m1 Q! v0 |$ w
    1、那么他的左子节点的下标 2*n + 1+ |8 d) P1 N# T+ \) `/ U9 _3 ?
    2、那么他的右子节点的下标 2*n + 2
    & Z9 K" c* u, [: C+ r# Y8 |3、他左边的节点是 n-1,如果当前节点是第 h 层的最左节点,那么第h-1层的最右节点的下标就是 n-15 N7 w+ Y! g4 ?
    4、根据1、2可以推出来n节点的父节点是 (n-1)/2,不管当前节点是父节点的左子节点还是右子节点,都用 (n-1)/2就行了,因为整型数字相除小数点后面的会被截断% x1 f% G( X8 ~4 q4 P8 n
    那么有了上面四条性质,我们就可以开始动手了
    9 C. D: E) j: S, J
    4 S# Z# I# S1 n( [1、假设我们要构建的堆是大顶堆,那么根据大顶堆的性质,任意节点都比它的左右子节点要大,所以我们肯定有个heapify方法,该方法调整指定节点和其子节点的位置,并且继续调整被调整的子节点和孙子节点的关系,直到没有调整或者到数的最底层7 t7 C0 D. a1 T' H: \& B  R
    2、然后我们要有构造大顶堆的方法,构造大顶堆就是从最后一个节点的父节点开始调整,接设最后一个节点的父节点是n,那么我们就将n,n-1,n-2 ··· ··· 0,这些节点逐次,从大到小调用heapify方法,这些节点都调整完成后,大顶堆就构造完成了
    , [- `* \$ p2 i3、接下来就开始将堆顶和堆尾互换,并砍断堆尾的操作了,由于互换之前,这是一个符合条件的大顶堆,但是换完只有只有一个堆顶这里不满足了,那么我们重新调整一下堆顶的三个元素就可以,还是调用heapify方法,这个方法会自上而下的重新调整堆,使其成为一个大顶堆
    5 T; b" ]3 |2 Q5 q. p1 N( z' c( z3 p, j3 K7 R1 a/ `
    堆排序的性质
    2 r6 S2 T9 ~8 t( `; Y2 w$ O
    7 U! [  ~- |; z0 T% P中文名称        英文名称        平均时间复杂度        最坏时间复杂度        最好时间复杂度        空间复杂度        稳定性
    4 S# u4 e+ `1 ^4 N; M堆排序        Heap        n*logn        n*logn        n*logn        1        不稳定
    5 X' I4 o1 q0 a, Q/ r: q6 a6 [上代码! t) t. ]! K3 _

    . V: u$ v' g! w3 I: Q2 w4 f  ]2 t/*** S  p' J* J7 D
    * 交换第n和m个元素
    3 C* C+ k  ~3 F) ]# f% f2 h: [$ } */
    - Z+ T2 D& ]: R+ b& o) |9 m+ wprivate static void swap(int arr[], int n, int m){
    , ^# B" m7 N7 ^) x+ ^  _$ b    int temp = arr[n];% }+ U) a! W1 _) l
        arr[n] = arr[m];' G, J) n9 @- B7 w- S4 `
        arr[m] = temp;# R' x& _# I# s5 |9 U$ B- O" B
    }
    " j  ~# ]* f, M, M4 K8 b6 d) X( q: D
    /**
    , z4 r7 b( Y% ] * 调整指定节点和其子节点
    - y6 _! M+ a' c5 {3 x6 A- b4 d5 @ * @param tree 整棵树
    ( W1 T3 `3 @: {* j * @param n 数组长度,树的元素个数9 h4 I9 G" K0 o' W! P% q
    * @param i 要调整的节点的下标
    4 K  D0 N6 K  F. o) S' y- I */0 d. L; S" A0 a# _
    private static void heapIfy(int tree[], int n, int i){
    4 ]' _, U0 C0 Z( ^4 Q4 N    if(i >= n){9 K$ E: t" z$ r: z! z
            return;
    " \1 b( s" q, C$ W! L    }
    : j9 Y! g9 @' W- e* d9 {+ H+ G    int c1 = 2 * i + 1;//左子节点的下标: \8 p, i2 \# k" a, P
        int c2 = 2 * i + 2;//右子节点的下标
    9 w! O) \7 P% Y. i    int max = i;//假设父节点是最大的/ W: {: I. C8 I
        //找出最大值的下下标
    ) s+ h8 z) m" j* Y* G% n- [( s    if(c1 < n && tree[c1] > tree[max]){
    $ i7 l' E# v$ I/ ]( @1 U        max = c1;' C, {6 P# p& x: W% r0 H! N
        }
    , [( k( i' A/ P* q9 q    if(c2 < n && tree[c2] > tree[max]){
    1 G; a2 f, ~' f: ~        max = c2;0 t( u3 f8 O7 Z" z( p+ G" A
        }
    4 |2 m" r$ B. I    if(max != i){//如果最大值不是父节点,需要做换位置操作
    / g0 H) [  p9 {. G" Y        swap(tree, max, i);
    ) L3 A+ i2 H3 S7 j        //此时,i节点被换成最大值了,符合大顶堆的性质. t7 t3 b8 J4 S# ]0 h
            //但是换到下面的节点不能保证比他的两个子节点都要大
    ( k! U% J" c! E6 a) R" ^4 G        //所以被换位置的节点继续调整7 \: \1 T/ B1 C4 X' j/ d+ A" m+ ^
            heapIfy(tree, n, max);8 V2 q. N5 [& _$ I5 X5 K3 `
        }$ X3 b. M; O  G8 `, O" R; Q
    }
      L8 h2 [! R* m; m$ z6 w9 o: B- a0 B8 g: B  q6 t) a. h; F/ {
    /**; U6 {4 N7 E' ], h* w
    * 完整构建大顶堆
    * R2 C( n( t" } * @param arr 用于构建堆的数组9 z8 J$ d2 z# y8 S0 ]: y( J  y
    * @param n 堆的最后一个节点的下标8 l3 s/ K$ N$ ]; e# w0 g
    */
    $ ]4 E5 b3 J  i& e) l3 m% `private static void buildHeap(int arr[],int n){
    , F# k7 h  m8 D/ ]    int lastNode = n - 1;
    9 a6 z9 A0 A+ l' K: R' `6 ~, T8 A    int parent = (lastNode - 1) / 2;2 u* H3 k+ F  J+ O, g
        for (int i = parent; i >= 0; i--){
    1 i) H5 t* M" i+ b0 g3 f, M        heapIfy(arr, n, i);
    " `5 ^* \$ N7 R. T8 K    }3 B2 h8 H7 N$ t
    }
    4 Q8 M% |* U" {3 |+ C
    1 q5 h) U3 H) F; q4 j4 E  ?9 u/**
    % }4 d$ p+ K8 s9 K% F * 堆排序5 S2 H  w8 b. H' X6 j" A. Y# X2 L
    * @param arr 待排数组9 R# Q7 v2 q% p! v/ D3 Z
    */
    " {/ l& w, V2 C1 O4 L2 t: Apublic static void sort(int arr[]){
    ! z+ u! c% |, \, Y* C    buildHeap(arr, arr.length);//先构造大顶堆1 f0 g( Q  m! @9 P
        //每次构建堆后将根节点和最后一个节点进行交换! K& z: d; m8 P" h
        //然后砍断最后一个节点
    * k4 f+ A* s6 Z7 ]    //所以从最后一个节点向前循环/ e" {( c5 W: D0 p# Q  j4 W
        for (int i = arr.length - 1; i > 0; i--){1 B% `  J0 H' d
            swap(arr, 0, i);1 s- ^% s$ _% n
            heapIfy(arr, i, 0);
    6 I" z. r# B0 K    }9 g  j4 j$ w5 g  l- {
    }0 O: [& {  K7 U* j& Q0 Y
    ————————————————
      X: p! Q/ \. b. F2 v# d3 q版权声明:本文为CSDN博主「qq_34912889」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。' W# _' n) H2 o6 u/ N" R' H' s
    原文链接:https://blog.csdn.net/qq_34912889/article/details/105690644: Q/ t  c9 R- U3 \, G9 s( e9 z' _
    , \# n. x3 K) m; w
    3 J; ]+ c5 }/ f- V# h
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2025-8-2 12:34 , Processed in 0.460588 second(s), 51 queries .

    回顶部