1.将n个元素从大到小排序后,选择第k个大的元素
#!/usr/bin/env python
#coding -*- utf:8 -*-
#冒泡排序选第k个元素
import random
import time def select_k():
n = int(input("所要生成的数组的长度:"))
arraya = []
for i in range(n):
x = random.choice(range(100))
arraya.append(x)
print("所生成的数组(未排序):", arraya)
arrayb = bubble_sort(arraya)
print("排序后的数组:", arrayb)
k = int(input("选择第几个元素:")) #从大到小第k个元素
result = arrayb[k-1]
return result def bubble_sort(a):
for i in range(len(a)):
for j in range(i,len(a)):
if a[i]<a[j]:
tmp = a[i]
a[i] = a[j]
a[j] = tmp
return a if __name__=='__main__':
t0 = time.clock() print("第k个元素是:",select_k()) #第二次调用clock()减去第一次调用clock()即为程序执行的时间
print("程序执行的时间:",time.clock()-t0)
2.泡排序前k个元素,后面的元素逐个和第k个元素比较,如果小于则忽略,如果大于则加入到正确的位置并移除最后一个元素
#!/usr/bin/env python
#coding -*- utf:8 -*-
#冒泡排序前k个元素,后面的元素逐个和第k个元素比较,如果小于则忽略,如果大于则
#加入到正确的位置并移除最后一个元素 import random
import time def select_k():
n = int(input("所要生成的数组的长度:"))
k = int(input("选择第几个元素:"))
arraya = []
for i in range(n):
x = random.choice(range(100))
arraya.append(x)
print("所生成的数组(未排序):", arraya)
arrayb = bubble_sort(arraya[:k])
print("前k个元素排序后的数组:", arrayb) for i in range(k, n):
if(arrayb[-1]<arraya[i]):
arrayb.append(arraya[i])
arrayb = bubble_sort(arrayb)
arrayb.pop() #返回第k个大的元素
result = arrayb[-1]
return result def bubble_sort(a):
for i in range(len(a)):
for j in range(i,len(a)):
if a[i]<a[j]:
tmp = a[i]
a[i] = a[j]
a[j] = tmp
return a if __name__=='__main__':
t0 = time.clock()
print("第k个大的元素是:",select_k()) #第二次调用clock()减去第一次调用clock()即为程序执行的时间
print("程序执行的时间:",time.clock()-t0)
3.时间对比
方法一:
N | 10 | 100 | 1000 | 5000 | 10000 | 20000 |
T | 0.0 | 0.001 | 0.06 | 1.17 | 4.65 | 18.25 |
方法二:
N | 10 | 100 | 1000 | 5000 | 10000 | 20000 |
T | 0.0 | 0.0 | 0.0 | 0.02 | 0.02 | 0.03 |