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