2 zhaifangqing zhaifangqing 于 2017.04.14 13:51 提问

CSDN Python学习班 大习题 100C

阅读以下冒泡法排序代码,尝试写出优化代码,提高代码运行效率。

from random import randint

def bubbleSort(lst):
    length = len(lst)
    for i in range(0, length):
        for j in range(0, length-i-1):
            #比较相邻两个元素大小,并根据需要进行交换
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]

lst = [randint(1, 100) for i in range(20)]
print('Before sort:\n', lst)
bubbleSort(lst)
print('After sort:\n', lst)

11个回答

qq_29594393
qq_29594393   Ds   Rxr 2017.04.14 14:37

冒泡排序最简单的优化,加一个标识,是不是进行过元素的交换,如果没有(说明排序已经完成),后面的就不再继续排序

 def bubbleSort(lst):
    length = len(lst)
        flag =true
    for i in range(0, length):
          if flag==true:
                flag=false
        for j in range(0, length-i-1):
        #比较相邻两个元素大小,并根据需要进行交换
          if lst[j] > lst[j+1]:
            temp=lst[j]
                        lst[j]=lst[j+1]
                        lst[j+1]=temp
                        flag =true
qq_38686327
qq_38686327 简单明了
4 个月之前 回复
caozhy
caozhy 不错
8 个月之前 回复
u011606457
u011606457   2017.04.14 14:36
for i in range(0, length):
    min = i;
    for j in range(i+1, length):
        #比较相邻两个元素大小,并根据需要进行交换
        if lst[min] > lst[j]:
            min = j
    lst[i], lst[min] = lst[min], lst[i]
YoungQuant
YoungQuant   2017.05.23 00:19

不好意思,上面一贴忘记改函数名字了,上面测试数据不正确!
为了了解自己的差距有多大,我改成计算20000个数的列表,还是他的厉害啊!
图片说明

u011606457
u011606457   2017.04.14 14:34

加一个变量min,记录最小值的下标,减少交换次数

 for i in range(0, length):
        min = i;
        for j in range(i+1, length):
            #比较相邻两个元素大小,并根据需要进行交换
            if lst[min] > lst[j]:
                min = j
                lst[i], lst[min] = lst[min], lst[i]
mengyidan
mengyidan   2017.04.14 14:42

上面这位同学厉害了~

ljheee
ljheee   Rxr 2017.04.14 15:37

冒泡排序,现在在一般情况下,都不使用了

qq_33732703
qq_33732703   2017.04.14 15:39

图片说明

 import time
from random import randint
start=time.time()
def bubbleSort(lst):
    length=len(lst)
    for i in range(0,length):
        for j in range(0,length-i-1):
            if lst[j]>lst[j+1]:
                lst[j],lst[j+1]=lst[j+1],lst[j]
lst=[randint(1,100) for i in range(20)]
print('Before')
print(lst)
bubbleSort(lst)
print('After')
print(lst)
end=time.time()
print('time1:',end-start)
print('--------------------------------------')
start=time.time()
def mysort(lst):
    length=len(lst)
    b=[]
    for i in range(length):
        b.append(lst.pop(lst.index(min(lst))))
    return b
lst=[randint(1,100) for i in range(20)]
print('Before')
print(lst)
lst=mysort(lst)
print('After')
print(lst)
end=time.time()
print('time2:',end-start)
print('--------------------------------------')

start=time.time()
lst=[randint(1,100) for i in range(20)]
print('Before')
print(lst)
print('After')
print(sorted(lst))
end=time.time()
print('time3:',end-start)
pipisorry
pipisorry   2017.04.14 18:56

加一个变量min,记录最小值的下标,减少交换次数实际是简单选择排序,可以认为已经不是冒泡排序了。
另一种改进是记录上次交换的最后位置L,L后面的都是有序的(后面部分有序),因为没有发生交换。可知这个改进的特殊情况就是添加swap变量判断是不是整个都有序。
i = len(x) - 1 # 需要进行比较的j的最大索引
while (i > 0):
last_swap = 0
for j in range(0, i):
if x[j] > x[j + 1]: # 升序
# if x[j] < x[j + 1]: # 降序
x[j], x[j + 1] = x[j + 1], x[j]
last_swap = j
i = last_swap

pipisorry
pipisorry   2017.04.14 19:02

加一个变量min,记录最小值的下标,减少交换次数实际是简单选择排序,可以认为已经不是冒泡排序了。
另一种改进是记录上次交换的最后位置L,L后面的都是有序的(后面部分有序),因为没有发生交换。可知这个改进的特殊情况就是添加swap变量判断是不是整个都有序。

     i = len(x) - 1  # 需要进行比较的j的最大索引
    while (i > 0):
        last_swap = 0
        for j in range(0, i):
            if x[j] > x[j + 1]:  # 升序
                # if x[j] < x[j + 1]:  # 降序
                x[j], x[j + 1] = x[j + 1], x[j]
                last_swap = j
        i = last_swap
YoungQuant
YoungQuant   2017.05.22 00:24

设计思路:重新生成一个新列表,以减少比较的时间
图片说明
跟楼上“天字三号”的速度差不多,测试了3次,一次他快,一次我快,一次打平,可能和cpu不稳定有关系吧!
图片说明
图片说明
图片说明

 print '以下是原算法'
start=time.time()
def bubbleSort(list):
    length = len(list)
    for i in range(0, length):
        for j in range(0, length-i-1):
            #比较相邻两个元素大小,并根据需要进行交换
            if list[j] > list[j+1]:
                list[j], list[j+1] = lst[j+1], lst[j]
lst = [randint(1, 100) for i in range(20)]
print('Before sort:\n', lst)
bubbleSort(lst)
print('After sort:\n', lst)
print 'time1=',time.time()-start

print '_________________________________________________________'
print '以下是我的改进算法'
start=time.time()
def bubbleSort(lst):
    global checklist
    length = len(lst)
    checklist=[]
    for i in range(0, length):
        checklist+=[min(lst)]
        lst.remove(min(lst))
lst = [randint(1, 100) for i in range(20)]
print('Before sort:\n', lst)
bubbleSort(lst)
print('After sort:\n', checklist)
print 'time2=',time.time()-start
print '\n\n'

共11条数据 1 尾页
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!