欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Heap Sort 实现(MIT Algorithm Course) 博客分类: python pythonheapsortalgorithm 

程序员文章站 2024-03-15 08:05:11
...
根据算法导论实现。有个小缺陷,heapsort中result是逆序排序。

def parent(i):
	return i%2;

def left(i):
	return 2*i+1;

def right(i):
	return 2*(i+1);

def maxHeapify(numList,i):
    l = left(i);
    r = right(i);
    if l<= len(numList)-1 and numList[l] > numList[i]:
        largest = l;
    else:
        largest = i;
    if r<= len(numList)-1 and numList[r] > numList[largest]:
        largest = r;
    if largest != i:
        numList[i], numList[largest] = numList[largest], numList[i]; #swap
        maxHeapify(numList,largest);

def buildMaxHeap(numList):
    heapsize = len(numList);
    for i in range(len(numList)//2-1,-1,-1):
        maxHeapify(numList,i);

def heapSort(numList):
    global alist;
    alist = numList;
    result= [];
    buildMaxHeap(alist);
    for i in range(len(alist)-1,0,-1):
        alist[0], alist[i] = alist[i], alist[0];
        #print(alist[i]);
        #print(i);
        result.append(alist.pop(i));
        maxHeapify(alist,0);
    result.append(alist.pop());
    return result;


从*找到的一种实现方式
def swap(i, j):                    
    sqc[i], sqc[j] = sqc[j], sqc[i] 

def heapify(end,i):   
    l=2 * i + 1  
    r=2 * (i + 1)   
    max=i   
    if l < end and sqc[i] < sqc[l]:   
        max = l   
    if r < end and sqc[max] < sqc[r]:   
        max = r   
    if max != i:   
        swap(i, max)   
        heapify(end, max)   

def heap_sort():     
    end = len(sqc)   
    start = end // 2 - 1 # use // instead of /
    for i in range(start, -1, -1):   
        heapify(end, i)   
    for i in range(end-1, 0, -1):   
        swap(i, 0)   
        heapify(i, 0)   

sqc = [2, 7, 1, -2, 56, 5, 3]
heap_sort()
print(sqc)