算法:冒泡排序(python版)

时间:2024-01-14 14:54:44

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   |