快捷導(dǎo)航

Python實(shí)現(xiàn)的堆排序算法示例

更新時(shí)間：2018年04月29日 11:17:23 作者：Vam.Dora.L

這篇文章主要介紹了Python實(shí)現(xiàn)的堆排序算法,結(jié)合實(shí)例形式分析了堆排序的原理及Python定義與使用堆排序算法的相關(guān)操作技巧,需要的朋友可以參考下

本文實(shí)例講述了Python實(shí)現(xiàn)的堆排序算法。分享給大家供大家參考，具體如下：

堆排序的思想: 堆是一種數(shù)據(jù)結(jié)構(gòu)，可以將堆看作一棵完全二叉樹(shù)，這棵二叉樹(shù)滿足，任何一個(gè)非葉節(jié)點(diǎn)的值都不大于（或不小于）其左右孩子節(jié)點(diǎn)的值。將一個(gè)無(wú)序序列調(diào)整為一個(gè)堆，就可以找出這個(gè)序列的最大值（或最小值），然后將找出的這個(gè)值交換到序列的最后一個(gè)，這樣有序序列就元素就增加一個(gè)，無(wú)序序列元素就減少一個(gè)，對(duì)新的無(wú)序序列重復(fù)這樣的操作，就實(shí)現(xiàn)了排序。

堆排序的執(zhí)行過(guò)程：

1.從無(wú)序序列所確定的完全二叉樹(shù)的第一個(gè)非葉子節(jié)點(diǎn)開(kāi)始，從右至左，從下至上，對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行調(diào)整，最終將得到一個(gè)大頂堆。

對(duì)節(jié)點(diǎn)的調(diào)整方法：將當(dāng)前節(jié)點(diǎn)（假設(shè)為a）的值與其孩子節(jié)點(diǎn)進(jìn)行比較，如果存在大于a的值的孩子節(jié)點(diǎn)，則從中選出最大的一個(gè)與a交換。當(dāng)a來(lái)到下一層的時(shí)候重復(fù)上述過(guò)程，直到a的孩子節(jié)點(diǎn)的值都小于a為止

2.將當(dāng)前無(wú)序序列中的第一個(gè)元素（反映在數(shù)中是根節(jié)點(diǎn)b），與無(wú)序序列中的最后一個(gè)元素交換（假設(shè)為c），b進(jìn)入有序序列，到達(dá)最終位置。無(wú)序序列元素減少1個(gè)，有序序列元素增加1個(gè)，此時(shí)只有節(jié)點(diǎn)c可能不滿足堆的定義，對(duì)其進(jìn)行調(diào)整。

3.重復(fù)2 的過(guò)程，直到無(wú)序序列的元素剩下一個(gè)時(shí)排序結(jié)束。

# -*- coding:utf-8 -*-
# 堆排序適用于記錄數(shù)很多的情況
from collections import deque
# 這里需要說(shuō)明元素的存儲(chǔ)必須要從1開(kāi)始
# 涉及到左右節(jié)點(diǎn)的定位，和堆排序開(kāi)始調(diào)整節(jié)點(diǎn)的定位
# 在下標(biāo)0處插入0，它不參與排序
L = deque([49,38,65,97,76,13,27,49])
L.appendleft(0)
#L = [0,49,38,65,97,76,13,27,49]
def element_exchange(numbers,low,high):
  temp = numbers[low]
  # j 是low的左孩子節(jié)點(diǎn)(cheer!)
  i = low
  j = 2*i
  while j<=high:
    # 如果右節(jié)點(diǎn)較大，則把j指向右節(jié)點(diǎn)
    if j<high and numbers[j]<numbers[j+1]:
      j = j+1
    if temp<numbers[j]:
      # 將numbers[j]調(diào)整到雙親節(jié)點(diǎn)的位置上
      numbers[i] = numbers[j]
      i = j
      j = 2*i
    else:
      break
  # 被調(diào)整節(jié)點(diǎn)放入最終位置
  numbers[i] = temp
def top_heap_sort(numbers):
  length = len(numbers)-1
  # 指定第一個(gè)進(jìn)行調(diào)整的元素的下標(biāo)
  # 它即該無(wú)序序列完全二叉樹(shù)的第一個(gè)非葉子節(jié)點(diǎn)
  # 它之前的元素均要進(jìn)行調(diào)整
  # cheer up！
  first_exchange_element = length/2
  #建立初始堆
  print first_exchange_element
  for x in range(first_exchange_element):
    element_exchange(numbers,first_exchange_element-x,length)
  # 將根節(jié)點(diǎn)放到最終位置，剩余無(wú)序序列繼續(xù)堆排序
  # length-1 次循環(huán)完成堆排序
  for y in range(length-1):
    temp = numbers[1]
    numbers[1] = numbers[length-y]
    numbers[length-y] = temp
    element_exchange(numbers,1,length-y-1)
if __name__=='__main__':
  top_heap_sort(L)
  for x in range(1,len(L)):
    print L[x],

運(yùn)行結(jié)果：