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)