大部分小伙伴在學(xué)習(xí)一段時間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學(xué)習(xí)網(wǎng)教學(xué)中心。

文章標題：創(chuàng)新互聯(lián)Python教程：python堆排序如何使用呢？
文章出自：http://uogjgqi.cn/article/dpjijos.html