CSDN Python学习班 大习题

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

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)

加一个变量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]

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]

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

 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

上面这位同学厉害了~

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

 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)

加一个变量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

加一个变量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

设计思路：重新生成一个新列表，以减少比较的时间

跟楼上“天字三号”的速度差不多，测试了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'

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

主体思路还是加入一个flag标识

#优化后的冒泡排序
 def bubbleSort(lst):
    length = len(lst)
    count = 0
    for i in range(0, length):
        flag = True
        for j in range(0, length - i - 1):
            count += 1
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]
                flag = False

        if flag:
            print(count)
            break