建站
咨詢
售后
建站咨詢
新聞中心
大部分小伙伴在學(xué)習(xí)一段時(shí)間python后，對(duì)python都有一定的認(rèn)知了，那今天來(lái)跟大家說(shuō)一些進(jìn)階性的內(nèi)容——堆排序，一起來(lái)看下吧~
在新絳等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供網(wǎng)站制作、成都做網(wǎng)站 網(wǎng)站設(shè)計(jì)制作按需開發(fā),公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),成都品牌網(wǎng)站建設(shè),成都營(yíng)銷網(wǎng)站建設(shè),外貿(mào)網(wǎng)站建設(shè),新絳網(wǎng)站建設(shè)費(fèi)用合理。
數(shù)據(jù)結(jié)構(gòu) - 堆
介紹堆排序之前，先介紹數(shù)據(jù)結(jié)構(gòu) - 堆，堆是一個(gè)完全二叉樹，并且滿足堆的性質(zhì)：子結(jié)點(diǎn)的值總小于（或者大于）其父節(jié)點(diǎn)的值。一般來(lái)說(shuō)，堆使用數(shù)組來(lái)存儲(chǔ)，并且根據(jù)某個(gè)元素在數(shù)組中的位置可以推斷出其子結(jié)點(diǎn)和父節(jié)點(diǎn)的位置。
第n個(gè)元素(從0開始計(jì)數(shù))的左結(jié)點(diǎn)是2*n+1，右結(jié)點(diǎn)是2*n+2；其父結(jié)點(diǎn)是floor((n - 1)/2)
堆排序的思路
根據(jù)堆的定義可知，根是堆的元素或者最小元素，首先將數(shù)組調(diào)整為大頂堆，那么第0個(gè)元素就是元素，將第0個(gè)和最后一個(gè)元素（暫且稱為第n個(gè)元素）交換位置，然后再將0~n-1個(gè)元素調(diào)整為堆，將第0個(gè)元素和第n-1元素交換，依次循環(huán)下去~
聽(tīng)起來(lái)很復(fù)雜，但只要花點(diǎn)時(shí)間，讀完這篇文章，一定可以明白堆排序，下面一點(diǎn)點(diǎn)拆解~
如何將數(shù)組調(diào)整為堆
思路：從最后一個(gè)結(jié)點(diǎn)的父節(jié)點(diǎn)開始處理，假設(shè)一共有n個(gè)元素，那么最后一個(gè)結(jié)點(diǎn)的父節(jié)點(diǎn)是第(n-1)/2個(gè)元素，找到其子節(jié)點(diǎn)中值節(jié)點(diǎn)，然后根其自身比較，如果自身值比子節(jié)點(diǎn)小，那么交換位置。
循環(huán)上述過(guò)程，從第(n-1)/2 一直遍歷到第0個(gè)元素就完成了堆的構(gòu)建。
Python代碼如下所示：
def make_heap(array): last_p = (len(array)-1)/2 while(last_p>=0): child = 2*last_p+1 if(child+1 < len(array)): if(array[child] < array[child+1]): child = child+1 if(child < len(array) and array[child] > array[last_p]): tmp = array[last_p] array[last_p] = array[child] array[child] = tmp last_p=last_p-1 print(array[0])
完整邏輯
構(gòu)建堆是堆排序中重要環(huán)節(jié)之一，構(gòu)建完堆之后應(yīng)該將第0個(gè)元素和最后一個(gè)元素交換位置，然后將前n-1個(gè)元素構(gòu)建堆，再將第0個(gè)和倒數(shù)第二個(gè)交換...
其中涉及到一些細(xì)節(jié)，只有自己親自動(dòng)手編碼才能掌握了解，這里給出一份DEMO
完整代碼如下：
# -*- coding: UTF-8 -*- import math def make_heap(array,n): last_p = (n-1)/2 while(last_p>=0): child = 2*last_p+1 if(child+1 < n): if(array[child] < array[child+1]): child = child+1 if(child < n and array[child] > array[last_p]): tmp = array[last_p] array[last_p] = array[child] array[child] = tmp last_p=last_p-1 def swap_i_j(array,i,j): array[i],array[j] = array[j],array[i] def heap_sort(array): n = len(array) while(n>0): make_heap(array,n) print(n,array) swap_i_j(array,0,n-1) print(n,array) n = n-1 array = [16,7,8,20,17,3] heap_sort(array) print(array)
輸出結(jié)果：
如需了解更多python實(shí)用知識(shí)，點(diǎn)擊進(jìn)入PyThon學(xué)習(xí)網(wǎng)教學(xué)中心。
網(wǎng)站題目：創(chuàng)新互聯(lián)Python教程：python堆排序如何使用呢？
新聞來(lái)源：http://www.dlmjj.cn/article/dpjijos.html
