冒泡排序

时间复杂度为O（n^2）

基本思想

经过n-1趟子排序完成的，第i趟子排序从第1个数至第n-i个数，若第i个数比后一个数大（则升序，小则降序）则交换两数。

 

举例：

第一趟：50与10比较，50>10,交换；50与30比较，50>30,交换；50与20比较，50>20,交换；50与40比较，50>40,交换。

 第二趟：10与30比较，10<30,不交换；30与20比较，30>20,交换；30与40比较，30<40,不交换，结束：

 
第三趟：10与20比较，10<20,不交换；20与30比较，20<30,不交换，结束：

 第四趟：10与20比较，10<20,不交换，结束：

排序完成~

 

 可以看出每一趟都是最大的数往上冒，故称为冒泡排序。

 

实现要点：

1.需经过n-1趟

2.第i趟，只对第1个数到第n+1-i个数排序

 

 

from time import time
import random

def bubble_sort(original_list):
    before_time = time()
    length = len(original_list)
    for i in range(1, length):
        for j in range(length - i):
            if original_list[j] > original_list[j + 1]:
                original_list[j], original_list[j + 1] = original_list[j + 1], original_list[j]
    after_time = time()
    print u'冒泡排序消耗时间为：', after_time - before_time
    return original_list

 

 

 

注：range(n)，从0到n-1（不包括n）；range(1,n)，从1到n-1；range(n,0,-1)，从n到1（包括n，不包括0）。

Python交换两个变量，不需要使用中间变量（打包解包原理）。

带标志的冒泡排序

从上面的例子看到：第二趟子排序后，就已经是从小到大的顺序，不需要再进行子排序了。

 

不需要再进行子排序的标志是：第i趟，没有交换发生。

 

因此，可以设置一个标志来判断是否发生了交换。

 

def bubble_sort(original_list):
    before_time = time()
    length = len(original_list)
    for i in range(1, length):
        exchange = True
        for j in range(length - i):
            if original_list[j] > original_list[j + 1]:
                original_list[j], original_list[j + 1] = original_list[j + 1], original_list[j]
                exchange = False
        if exchange:
            break
    after_time = time()
    print u'冒泡排序消耗时间为：', after_time - before_time
    return original_list

 

记录最后交换位置的冒泡排序

再举个例子

 

原始 ：  30，20，10，5  ，40，50

第一趟：20，10，5  ，30，40，50

 

第二趟的详细过程是，

20大于10，交换：   10，20，5  ，30，40，50

20大于5  ，交换：   10，5  ，20，30，40，50

20小于30，不交换：10，5  ，20，30，40，50

30小于40，不交换：10，5  ，20，30，40，50

 

发现第一趟中30与5发生交换后，以后没再交换位置了，已经是从小到大的顺序。而这时候如果记录下做最后交换的位置，第二趟就可以少比较一次。最后一次就没必要发生。程序再改进为：

 

 

def bubble_sort(original_list):
    before_time = time()
    length = poz = last = len(original_list)
    for i in range(1, length):
        exchange = True
        for j in range(1, last):
            if original_list[j] < original_list[j - 1]:
                original_list[j], original_list[j - 1] = original_list[j - 1], original_list[j]
                exchange = False
                poz = j
        last = poz
        print i,u'趟：',original_list
        if exchange or last == 1:
            break
    after_time = time()
    print u'冒泡排序消耗时间为：', after_time - before_time
    return original_list

 

 

Review代码，有几个问题:

1. 标志exchange失去了它原来的作用（可以下if exchange or last == 1语句中输出exchange的值看到）。

2. 最外层for循环也失去了它原有的意义（控制代码进行n-1次子排序）

 

重构代码：

 

def bubble_sort2(original_list):
    before_time = time()
    last = len(original_list)
    while last > 1:
        poz = 0
        for j in range(1, last):
            if original_list[j] < original_list[j - 1]:
                original_list[j], original_list[j - 1] = original_list[j - 1], original_list[j]
                poz = j
        last = poz
    after_time = time()
    print u'冒泡排序消耗时间为：', after_time - before_time
    return original_list

 

 

作者：Tim http://huaxia524151.iteye.com 转载请注明出处~