快捷導(dǎo)航

Python實(shí)現(xiàn)堆排序的方法詳解

更新時(shí)間：2016年05月03日 11:40:13 作者：阿涵-_-

這篇文章主要介紹了Python實(shí)現(xiàn)堆排序的方法,結(jié)合實(shí)例形式詳細(xì)分析了堆排序的原理,實(shí)現(xiàn)方法與相關(guān)注意事項(xiàng),需要的朋友可以參考下

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

堆排序作是基本排序方法的一種，類似于合并排序而不像插入排序，它的運(yùn)行時(shí)間為O(nlogn)，像插入排序而不像合并排序，它是一種原地排序算法，除了輸入數(shù)組以外只占用常數(shù)個(gè)元素空間。

堆（定義）：（二叉）堆數(shù)據(jù)結(jié)構(gòu)是一個(gè)數(shù)組對象，可以視為一棵完全二叉樹。如果根結(jié)點(diǎn)的值大于（小于）其它所有結(jié)點(diǎn)，并且它的左右子樹也滿足這樣的性質(zhì)，那么這個(gè)堆就是大（?。└选?/p>

我們假設(shè)某個(gè)堆由數(shù)組A表示，A[1]為樹的根，給定某個(gè)結(jié)點(diǎn)的下標(biāo)i，其父結(jié)點(diǎn)、左孩子、右孩子的下標(biāo)都可以計(jì)算出來：

PARENT(i):
return i/2
LEFT(i):
return 2i
RIGHT(i):
return 2i+1

堆排序Python實(shí)現(xiàn)

所謂堆排序的過程，就是把一些無序的對象，逐步建立起一個(gè)堆的過程。
下面是用Python實(shí)現(xiàn)的堆排序的代碼：

def build_max_heap(to_build_list):
  """建立一個(gè)堆"""
  # 自底向上建堆
  for i in range(len(to_build_list)/2 - 1, -1, -1):
    max_heap(to_build_list, len(to_build_list), i)
def max_heap(to_adjust_list, heap_size, index):
  """調(diào)整列表中的元素以保證以index為根的堆是一個(gè)最大堆"""
  # 將當(dāng)前結(jié)點(diǎn)與其左右子節(jié)點(diǎn)比較，將較大的結(jié)點(diǎn)與當(dāng)前結(jié)點(diǎn)交換，然后遞歸地調(diào)整子樹
  left_child = 2 * index + 1
  right_child = left_child + 1
  if left_child < heap_size and to_adjust_list[left_child] > to_adjust_list[index]:
    largest = left_child
  else:
    largest = index
  if right_child < heap_size and to_adjust_list[right_child] > to_adjust_list[largest]:
    largest = right_child
  if largest != index:
    to_adjust_list[index], to_adjust_list[largest] = \
    to_adjust_list[largest], to_adjust_list[index]
    max_heap(to_adjust_list, heap_size, largest)
def heap_sort(to_sort_list):
  """堆排序"""
  # 先將列表調(diào)整為堆
  build_max_heap(to_sort_list)
  heap_size = len(to_sort_list)
  # 調(diào)整后列表的第一個(gè)元素就是這個(gè)列表中最大的元素，將其與最后一個(gè)元素交換，然后將剩余的列表再調(diào)整為最大堆
  for i in range(len(to_sort_list) - 1, 0, -1):
    to_sort_list[i], to_sort_list[0] = to_sort_list[0], to_sort_list[i]
    heap_size -= 1
    max_heap(to_sort_list, heap_size, 0)
if __name__ == '__main__':
  to_sort_list = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
  heap_sort(to_sort_list)
  print to_sort_list

更多關(guān)于Python相關(guān)內(nèi)容可查看本站專題：《Python正則表達(dá)式用法總結(jié)》、《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python Socket編程技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》、《Python入門與進(jìn)階經(jīng)典教程》及《Python文件與目錄操作技巧匯總》

希望本文所述對大家Python程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: