這篇文章將為大家詳細講解有關(guān)python堆排序的使用方法，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

創(chuàng)新互聯(lián)專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于網(wǎng)站制作、成都網(wǎng)站建設(shè)、潁上網(wǎng)絡(luò)推廣、微信小程序定制開發(fā)、潁上網(wǎng)絡(luò)營銷、潁上企業(yè)策劃、潁上品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運營等，從售前售中售后，我們都將竭誠為您服務(wù)，您的肯定，是我們最大的嘉獎；創(chuàng)新互聯(lián)為所有大學(xué)生創(chuàng)業(yè)者提供潁上建站搭建服務(wù)，24小時服務(wù)熱線：18982081108，官方網(wǎng)址：chinadenli.net

數(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é)果：

關(guān)于python堆排序的使用方法就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。

文章名稱：python堆排序的使用方法
地址分享：http://chinadenli.net/article14/goppge.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信公眾號、品牌網(wǎng)站設(shè)計、移動網(wǎng)站建設(shè)、ChatGPT、網(wǎng)站設(shè)計、品牌網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)