這是一個有效的堆排序？

在過去的6個小時裏，我一直在閱讀關於構建heapsort的教程和學術資料。我終於在Python中對一些整數列表進行了原型化。但是，我不完全確定我的解決方案是否構成有效的堆排序。這是一個非常簡單的解決方案，絕對可以改進，但我想知道它是否有效。令人困惑的是，每個人似乎都有自己的'首選'實現這種算法的方式。這是一個有效的堆排序？

非常感謝提前。

def heapsort(array): 
    array = heapify(array) 
    array = insert(array, 9999) 
    print(array) 

def heapify(array): 
    end = len(array) 
    i = 0 
    j = 0 
    while i < end: 
     while j < end: 
      if array[i] > array[j]: 
       array = swap(array, i, j) 
      j += 1 
     i += 1 
     j = i 
    return array 

def insert(array, x): 
    array.append(x) 
    return heapify(array) 


def swap(array, a, b): 
    temp = array[a] 
    array[a] = array[b] 
    array[b] = temp 
    return array 

def main(array): 
    heapsort(array) 

if __name__ == '__main__': 
    array = [3, 1, 2, 4, 6, 7, 9, 0] 
    main(array)

來源

2015-06-01 Tom

「但我想知道它是否有效。」 - 用測試數據運行它！（包括上升/下降，隨機，小集合，大集合），但這不會證明它是正確的，它至少會顯示任何明顯的缺陷。 –

'def swap（array，a，b）：array [a]，array [b] = array [b]，array [a]' – Veedrac

請注意Python有一個heapq模塊可以測試。 – Veedrac

您的heapify（）應該比較堆（樹結構）中父/子的元素。它們在陣列內的相對位置是

ChildIndex = 2 * Parent Index + [0|1] # two children per parent

按照索引進入數組。這在您的實施中並不明顯。

來源

2015-06-01 01:17:57 javadba

你寫的東西似乎是Selection Sort。

堆排序將數組排列成一個堆（最簡單的二進制堆），它是一個結構，其中找到最小元素的時間是O（1）並且除去最小元素是O（log n ）並且元素的插入也是O（log n）。然後重複取這個最小的元素來產生排序的順序。

來源

2015-06-01 01:23:37 moreON

氣泡排序比較相鄰的元素。這是選擇數組未排序部分中的最小元素。它恰好將該元素的最終位置用作當前發現的最小臨時存儲，而不是一些額外的臨時變量。 – moreON

這是一個有效的堆排序？

回答

相關問題