QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1480|回复: 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
    # U$ X) N- B6 E4 M' I$ I& O
    十大经典排序算法之堆排序(Java语言)
    9 D2 f( m. \9 l$ J2 _. Z0 y* W& }文章目录
    3 |0 T0 h1 c/ g+ \: ]
    + _6 Y" \9 x7 P$ \! p; p* P; Q什么是堆4 q4 O: L& x6 _+ g
    如何进行堆排序呢
    ( ~& o% n; i9 C7 h/ [用数组构建一个堆
    ; L! E) G6 X/ r0 A7 z% W上代码
    6 u$ Z( R. ^1 q4 Y什么是堆) C; \: l* n, L+ u% y
    9 K# [0 K+ {1 O( V0 q. H
    在了解什么是堆之前一定要先了解什么是完全二叉树
    ' ~& @: [$ u& J7 f8 f看一下百度百科的介绍
    ( Z! p) f+ u- Y
    & B6 c6 r' T: q5 y/ D若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
    & M" d. _$ M/ B- w0 Q/ C8 X( i百度百科拗口版性质介绍,能看懂上面的就行,下面的大概看下
    / D4 s( N& ^, i. k0 }0 E% Z6 V' e: c
    完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
    9 c* |. y/ t7 _$ X& u3 K8 g) W(1)所有的叶结点都出现在第k层或k-l层(层次最大的两层)
    * |: c* d' p1 y$ O% i- Y: _(2)对任一结点,如果其右子树的最大层次为L,则其左子树的最大层次为L或L+l。
    1 m6 [9 z" a, n3 O: }( ]一棵二叉树至多只有最下面的两层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,则此二叉树成为完全二叉树,并且最下层上的结点都集中在该层最左边的若干位置上,而在最后一层上,右边的若干结点缺失的二叉树,则此二叉树成为完全二叉树。
    ( }2 D7 v1 e3 f; |3 G那么在了解到什么是完全二叉树之后,我们再来看什么是堆
    ' j* T4 Q+ R3 [% f  t7 D堆有以下两个性质* h! {# r! @# M2 E  K
    , ~5 I0 X5 a  d1 L7 s# B4 e7 U
    1 堆中某个节点的值总是不大于或不小于其父节点的值;7 w) i. _, }& b9 f
    2 堆总是一棵完全二叉树。
    ( j  u& V" R, H* G其中堆顶就对应二叉树的根& M1 x# o7 x8 T

      K+ F$ H& K+ _* E8 G堆又分为大顶堆和小顶堆,根据堆的第一个性质来进行区分* F' H+ [; u7 W

    , E1 }; J6 ]8 x. o0 d当堆中某个节点的值总是大于它的子节点的时候这个堆为大顶堆,反之为小顶堆
    7 I5 B& H' J) G  ]0 Z' k如何进行堆排序呢& ?  L# f5 z) R/ c* M! p$ B1 \

    - W" K( Z* ]  @) x( ?8 I+ T堆排序,其实就是每次构造出一个大顶堆或者小顶堆,然后取出堆顶的值,再将剩下的值重新构造成大顶堆或者小顶堆,最终到堆里的值全部取出来,取出来的数就是排好序的& ~1 d5 ^  e1 O. m
    8 o0 ^  |" a, D8 m6 F
    用数组构建一个堆
    1 h0 k/ g8 C! g8 g) t0 `+ v) p! o
    8 k5 t# V& B( d% K* p: R因为堆是一颗完全二叉树,所以我们可以用数组来对其进行存储
    - n- V/ z! B4 F, T9 E8 T) L0 ~! ]对于用数组存储的二叉树,我们可以用如下方法来定义:
    $ S# s1 l- e' x5 P' i8 r- y假设当前节点的下标为 n3 s8 D: O/ m# t" w$ w# z
    " n; L% I" B+ F4 L
    1、那么他的左子节点的下标 2*n + 1$ ~4 E+ I( H$ `( r
    2、那么他的右子节点的下标 2*n + 2
    3 ^* \2 d( D! e/ f3、他左边的节点是 n-1,如果当前节点是第 h 层的最左节点,那么第h-1层的最右节点的下标就是 n-1* D2 o  H6 S" y3 j
    4、根据1、2可以推出来n节点的父节点是 (n-1)/2,不管当前节点是父节点的左子节点还是右子节点,都用 (n-1)/2就行了,因为整型数字相除小数点后面的会被截断
    + |8 T. y6 y+ s那么有了上面四条性质,我们就可以开始动手了: n; C6 q- g/ l/ d! T

    ' x# ?+ o- o' t% D2 z5 P8 |1、假设我们要构建的堆是大顶堆,那么根据大顶堆的性质,任意节点都比它的左右子节点要大,所以我们肯定有个heapify方法,该方法调整指定节点和其子节点的位置,并且继续调整被调整的子节点和孙子节点的关系,直到没有调整或者到数的最底层
    7 X9 b8 b5 B2 Y( D+ m; p* }2、然后我们要有构造大顶堆的方法,构造大顶堆就是从最后一个节点的父节点开始调整,接设最后一个节点的父节点是n,那么我们就将n,n-1,n-2 ··· ··· 0,这些节点逐次,从大到小调用heapify方法,这些节点都调整完成后,大顶堆就构造完成了
    . E) Q- V- G. G+ v+ ]5 S: k& q3、接下来就开始将堆顶和堆尾互换,并砍断堆尾的操作了,由于互换之前,这是一个符合条件的大顶堆,但是换完只有只有一个堆顶这里不满足了,那么我们重新调整一下堆顶的三个元素就可以,还是调用heapify方法,这个方法会自上而下的重新调整堆,使其成为一个大顶堆. r6 G& o( ]$ A5 p" c7 O- N

    ) V( {7 u( y) Q  @8 |堆排序的性质2 q4 S5 p6 R: Y, F

    1 K, N; Y9 g  g' K  M* @7 Q( ]中文名称        英文名称        平均时间复杂度        最坏时间复杂度        最好时间复杂度        空间复杂度        稳定性
    5 \8 r' N$ B: B& ^+ Z堆排序        Heap        n*logn        n*logn        n*logn        1        不稳定
    ' U2 ~2 B/ d" n& _0 E! Z( t上代码
    : G% y1 w- c! E! i' u' g" |
    " n: A- J0 K' l. Q6 a4 p/**3 _$ v5 O! k1 b: \
    * 交换第n和m个元素
    5 K* _( }- r# x7 ]+ }( W: X */
    5 K; E. l" `2 R1 y9 D+ o4 zprivate static void swap(int arr[], int n, int m){
    $ [& K( h4 J6 w1 Q6 l7 w    int temp = arr[n];
    ( m5 y! a+ x* l' v    arr[n] = arr[m];9 K4 b) t/ a4 N+ o! _
        arr[m] = temp;) B, J. `+ M8 e; ^; q
    }
    0 ^! s: l5 e. m7 w+ ^/ K7 g& F# K4 n  g2 w
    /**
    5 r: y, {7 O" R0 \) S( v% [5 L. p * 调整指定节点和其子节点" @, C) b- _; i0 u; k
    * @param tree 整棵树/ V+ }( K# X( C" j2 S3 \9 {
    * @param n 数组长度,树的元素个数' d/ C# g( {# y# [
    * @param i 要调整的节点的下标+ S  Y" L$ v* ?! a7 O
    */
    - H/ f. L' ?, M1 D' kprivate static void heapIfy(int tree[], int n, int i){
    3 v3 F: z7 N# I, c2 p+ m( ]    if(i >= n){5 Q( M7 [2 C8 i! k9 {! m$ z
            return;
    2 \  k1 C: [7 Y% |, X    }# ?7 ?; t/ Y* N$ X6 F0 S8 d% a
        int c1 = 2 * i + 1;//左子节点的下标
    " n8 v) T& U8 ?* i( }, y! j    int c2 = 2 * i + 2;//右子节点的下标! w4 m; }4 l- H! U9 E
        int max = i;//假设父节点是最大的
    ! h' `# `& s/ R5 I    //找出最大值的下下标
    ( ~  l" B) ~% N7 d    if(c1 < n && tree[c1] > tree[max]){  ~) @! H- t0 S2 u2 h  Z* O5 ?
            max = c1;) D6 W* J6 V' v2 f) A, g
        }
    2 j- F, A$ G* [4 S2 Y    if(c2 < n && tree[c2] > tree[max]){. P4 k& ?# {: ^4 e
            max = c2;& K/ p" a1 x( M# j  v, Z( l
        }  W  s1 y# u0 l& P9 b: A8 L" y
        if(max != i){//如果最大值不是父节点,需要做换位置操作5 E$ C+ ^) y: p3 Z" D1 g
            swap(tree, max, i);$ Q: ?4 l$ Q0 w) b" j
            //此时,i节点被换成最大值了,符合大顶堆的性质1 F' }: r" @' I, \. P, |
            //但是换到下面的节点不能保证比他的两个子节点都要大& s8 ]# z$ g/ \  Y  [# P
            //所以被换位置的节点继续调整
    ; _. K$ D# l6 ~' _$ f) r7 `        heapIfy(tree, n, max);
    6 V% h+ B  s6 A6 E( L. r, N    }
    " O/ T4 G6 }- P1 B, Y  Y: L  z}
    : I6 J) C" v" M% Z* v- Y( u. X2 x
    ; T, d1 j/ |: h! q& z( Q! q/**7 w" ]( k) C$ U. E# e4 P/ O2 `+ D
    * 完整构建大顶堆0 [( A! L& s0 k6 w
    * @param arr 用于构建堆的数组
    . J8 Z) y, f% Y * @param n 堆的最后一个节点的下标2 H" }9 ?) w2 n2 D$ y& ]: G
    *// h) i4 P! u6 s& W+ C
    private static void buildHeap(int arr[],int n){0 J& g1 V) A4 @" t# @
        int lastNode = n - 1;4 l* E" o  z' x0 l8 _* l: c+ M
        int parent = (lastNode - 1) / 2;
    4 R8 ~9 ]6 ?+ q* S" U7 V$ s% r    for (int i = parent; i >= 0; i--){% W( M0 ?8 ?/ g
            heapIfy(arr, n, i);
    2 R! D! J* E- ]# C) ~- p$ ]7 {    }+ u/ q, p5 r- C$ h" X; ~
    }' L2 L, i# S( h; T* W
    , P- C% W4 _: ~- O) z
    /**
    5 j- K- ^5 P4 D5 Q; q( C * 堆排序0 ?. ?7 m( ~9 z/ k/ ~; D' ^. f
    * @param arr 待排数组3 R( v! O! j% E0 D. J
    */
    ; l6 {1 c/ V6 Ipublic static void sort(int arr[]){8 R. k$ R- n" S. Y9 [
        buildHeap(arr, arr.length);//先构造大顶堆* k% C4 k6 V6 L: K( y/ p" x7 ~
        //每次构建堆后将根节点和最后一个节点进行交换( \9 m$ l; K% C, @* @9 b! D/ o  u
        //然后砍断最后一个节点7 a0 ^- v* p& D$ h9 e
        //所以从最后一个节点向前循环/ F9 [: o# H8 g2 \9 I' w0 v
        for (int i = arr.length - 1; i > 0; i--){& j% I: W& R/ ]+ o7 h4 |
            swap(arr, 0, i);
    ; w' Q2 x4 \1 o$ f! R        heapIfy(arr, i, 0);. u$ j, U% ~& H
        }+ ~6 M8 C3 p# H& f7 Q( \+ R3 t
    }+ i- @# E6 Q1 P+ [
    ————————————————
    + N. y; ?" Z7 c5 d3 V版权声明:本文为CSDN博主「qq_34912889」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。1 Q% J" E5 n! _4 F8 H
    原文链接:https://blog.csdn.net/qq_34912889/article/details/105690644
    ' x2 ?0 V7 U' L8 q" W! I
    7 e( F$ ]$ a+ Z( t- X4 ~! F# `
    4 u' f- Y3 J. e/ Y/ [
    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, 2026-6-10 06:34 , Processed in 0.264526 second(s), 51 queries .

    回顶部