python實現的堆排序算法代碼

python實現的堆排序算法代碼

def heapSort(a): 
    def sift(start, count): 
        root = start


    while root * 2 + 1 < count: 
        child = root * 2 + 1 
        if child < count - 1 and a[child] < a[child + 1]: 
            child += 1 
        if a[root] < a[child]: 
            a[root], a[child] = a[child], a[root] 
            root = child 
        else: 
            return 

count = len(a) 
start = count / 2 - 1 
end = count - 1 

while start >= 0: 
    sift(start, count) 
    start -= 1 

while end > 0: 
    a[end], a[0] = a[0], a[end] 
    sift(0, end) 
    end -= 1 


a = [-8,0,1,3,11,35,68] 
heapSort(a) 
print a # [-8, 0, 1, 3, 11, 35, 68]
 </pre> 

 Recursive sift(and more readable IMHO) Version:
def heapsort(a):


def swap(a,i,j): 
    tmp = a[i] 
    a[i] = a[j] 
    a[j] = tmp   

def siftdown(a, i, size): 
    l = 2*i+1 
    r = 2*i+2 
    largest = i 
    if l <= size-1 and a[l] > a[i]: 
        largest = l 
    if r <= size-1 and a[r] > a[largest]: 
        largest = r 
    if largest != i: 
        swap(a, i, largest) 
        siftdown(a, largest, size) 

def heapify(a, size): 
    p = (size/2)-1 
    while p>=0: 
        siftdown(a, p, size) 
        p -= 1 

size = len(a)         
heapify(a, size) 
end = size-1 
while(end > 0): 
    swap(a, 0, end) 
    siftdown(a, 0, end) 
    end -= 1 </pre>