Python天天美味(32) - python資料結構與算法之堆排序

選擇排序原理是先選出最小的數，與第一個數交換，然後從第二個數開始再選擇最小的數與第二個數交換，……

def selection_sort(data):

    for i in range(len(data) - 1):

        min = data[i]

        k = i

        for j in range(i, len(data)):

            if data[j] < min:

                min = data[j]

                k = j

        if i <> k:

            data[i], data[k] = data[k], data[i]

堆排序的原理将數組調整成堆，然後将堆頂元素與最後一個元素交換，然後将最後一個節點剔除出堆，再将剩下的數組調整成堆，然後再交換堆頂元素與最後一個元素……

def heap_adjust(data, s, m):

    if 2 * s > m:

        return

    temp = s - 1

    if data[2*s - 1] > data[temp]:

        temp = 2 * s - 1

    if 2 * s <= m - 1 and data[2*s] > data[temp]:

        temp = 2 * s

    if temp <> s - 1:

        data[s - 1], data[temp] = data[temp], data[s - 1]

        heap_adjust(data, temp + 1, m)

def heap_sort(data):

    m = len(data) / 2

    for i in range(m, 0, -1):

        heap_adjust(data, i, len(data))

    data[0], data[-1] = data[-1], data[0]

    for n in range(len(data) - 1, 1, -1):

        heap_adjust(data, 1, n)

        data[0], data[n - 1] = data[n - 1], data[0]

堆排序的效率還是蠻高的，結果如下：

selection_sort 0:00:02.219000

heap_sort 0:00:00.157000

<a target="_blank" href="http://www.cnblogs.com/coderzh/archive/2008/12/07/1349735.html">Python 天天美味(33) - 五分鐘了解元類（Metaclasses）[轉]</a>

本文轉自CoderZh部落格園部落格，原文連結：http://www.cnblogs.com/coderzh/archive/2008/09/22/1296195.html，如需轉載請自行聯系原作者