找出最小或者最大的几个数我使用的是堆排序,效率为0(nlgn)
构建小顶堆返回末尾的k个数 或者 构建大顶堆返回前k个数
#!/usr/bin/env python3 def heap_sort(ary, num):
def siftdown(ary, e, begin, end):
i,j = begin, begin*2+1
while j < end:
if j+1 < end and ary[j+1] < ary[j]:
j += 1
if e < ary[j]:
break
ary[i] = ary[j]
i,j = j,j*2+1
ary[i] = e end = len(ary)
for i in range(end//2-1, -1, -1):
siftdown(ary, ary[i], i, end) #方法1
for i in range(end-1, -1, -1):
e = ary[i]
ary[i] = ary[0]
siftdown(ary, e, 0, i)
return ary[:-num-1:-1] #方法2
"""
li = []
for i in range(num):
if len(ary) > i:
li.append(ary[0])
e = ary[end-1-i]
siftdown(ary, e, 0, end-1-i)
else:
break
return li
""" if __name__ == '__main__':
a = [4,5,1,6,2,7,3,8]
num = int(input("最小的k个数:"))
print(heap_sort(a,num))