heap:
take klog(n) time
code is as follow"
def siftdown(A, start, end):root = startchild = 2 * root + 1while child <= end:if child + 1 <= end and A[child] < A[child + 1]:child += 1if A[root] < A[child]:A[child], A[root] = A[root], A[child]root = childelse:returndef heapify(A, count):start = (count – 2) / 2while start >= 0:siftdown(A, start, count – 1)start = start -1#def heapsort(A):#count = len(A)#heapify(A, len(A))#end = count – 1#while end > 0:#A[end], A[0] = A[0], A[end]#end -= 1#siftdown(A, 0, end)#return Adef topk(A, k):count = len(A)heapify(A, len(A))end = len(A) – 1while end > 0 and k > 0:A[end], A[0] = A[0], A[end]end -= 1k -= 1siftdown(A, 0, end)return A[end + s1:] #def drawmax(A):A = [3, 4, 5, 1, 2, 0]print topk(A, 3)
quick select take O(n) time find k values
import randomdef partition(num, pivotIndex, left, right):pivot = num[pivotIndex]num[pivotIndex], num[right] = num[right], num[pivotIndex]storeIndex = leftfor i in range(left, right):if num[i]< pivot:num[storeIndex], num[i] = num[i], num[storeIndex]storeIndex += 1num[storeIndex], num[right] = num[right], num[storeIndex]return storeIndexdef quickselect(num, k):left = 0right = len(num) – 1while True:pivotIndex = random.randint(left,right)pivotNewIndex = partition(num, pivotIndex,left, right)dist = pivotNewIndex – leftif dist == k:return num[pivotNewIndex]elif dist > k:right = pivotNewIndex – 1else:k -= (dist+1)left = pivotNewIndex + 1num =[8, 9,0,1,2,3,6,7]print quickselect(num,3)
，就得加倍付出汗水，赢得场场精彩
