堆：二叉堆是一个数组，近似完全二叉树，树上每个结点对应数组中的一个元素。除了最底层外，该树是完全满的，而且是从左到右填充。
最大堆：除了根结点以外的所有结点i，都要满足：A[PARENT(i)]>=A[i];
最小堆：除了根结点以外的所有结点i，都要满足：A[PARENT(i)]<=A[i];
堆的应用：堆排序、优先队列
可以实现原址的排序。
|
#!/usr/bin/env python # -*- coding:UTF-8 -*- import math
heapSize = 0
def PARENT(i): return math.floor((i-1)/2)
def LEFT(i): return 2*i+1
def RIGHT(i): return 2*i+2
def maxHeapify(A,i): global heapSize l = LEFT(i) r = RIGHT(i) if l < heapSize and A[l] > A[i]: largest = l else: largest = i
if r < heapSize and A[r] > A[largest]: largest = r
if largest != i: tmp = A[i] A[i] = A[largest] A[largest] = tmp maxHeapify(A,largest)
def buildMaxHeap(A): global heapSize heapSize = len(A) for i in range(math.floor(len(A)/2),-1,-1): maxHeapify(A,i)
def heap_sort(A): global heapSize buildMaxHeap(A) for i in range(len(A)-1,0,-1): tmp = A[0] A[0] = A[i] A[i] = tmp heapSize = heapSize - 1 maxHeapify(A,0)
if __name__ == ‘__main__‘: A = [9,3,5,2,3,5,7,8,9,1,11,20,0,2] print(A) heap_sort(A) print(A) |
快速排序也是运用分治思想。分为三个步骤：
分解：将A[p,r]数组分为两个子数组，A[p,q-1]和A[q+1,r],其中A[p,q-1]中的元素都<=A[q].
A[q+1,r]中的元素都>=A[q]. 计算下标q也是划分过程一部分。
解决：通过递归调用快速排序，对子数组A[p,q-1]和A[q+1,r]进行排序。
合并：因为子数组是原址排序的，所以不需要合并。最后A[p,r]已经排序好。
|
#!/usr/bin/env python # -*- coding:UTF-8 -*-
def partition(A,p,r): x = A[r] i = p-1 for j in range(p,r): if A[j]<=x: i += 1 tmp = A[i] A[i] = A[j] A[j] = tmp tmp = A[i+1] A[i+1] = A[r] A[r] = tmp return i + 1
def quick_sort(A,p,r): if p < r: q = partition(A,p,r) quick_sort(A,p,q-1) quick_sort(A,q+1,r)
if __name__ == ‘__main__‘: A = [9,3,5,2,3,5,7,8,9,1,11,20,0,2] print(A) quick_sort(A,0,len(A)-1) print(A) |
最坏时间复杂度：
期望时间复杂度：
原文：https://www.cnblogs.com/sunnypoem/p/10864052.html