0.產(chǎn)生7000長(zhǎng)度的亂序列表

import random

a_list = list(range(1,7000 + 1))
normal_list = random.sample(a_list, k=len(a_list))
normal_list[:5]

上面一段代碼的運(yùn)行結(jié)果如下，因?yàn)槭请S機(jī)打亂順序，讀者運(yùn)行結(jié)果會(huì)不同：

[2780, 397, 5063, 6494, 1245]

0.1 保存此亂序列表

import pickle

with open('normal_list.pickle', 'wb') as file:
    pickle.dump(normal_list, file)

0.2 加載此亂序列表

import pickle

with open('normal_list.pickle', 'rb') as file:
    normal_list = pickle.load(file)

0.3 計(jì)時(shí)裝飾器

裝飾器是python的高級(jí)用法，初學(xué)者需要單獨(dú)學(xué)習(xí)1天才能理解并且熟練運(yùn)用。
讀者如果不理解本節(jié)內(nèi)容，不影響后續(xù)內(nèi)容的理解。
此裝飾器只是計(jì)算函數(shù)運(yùn)行花費(fèi)的時(shí)間，讀者可以自己用其他方法實(shí)現(xiàn)相同效果。

from time import time

def timer(func):
    def inner(*args,**kwargs):
        start = time()
        result = func(*args,**kwargs)
        end = time()
        usedTime = 1000 * (end - start)
        print("%s function used %.2f ms" %(func.__name__,usedTime))
        return result
    return inner

1.冒泡排序

@timer
def bubble_sort(normal_list):
    length = len(normal_list)
    for i in range(length, 1, -1):
        for j in range(0, i-1):
            if normal_list[j] > normal_list[j+1]:
                normal_list[j], normal_list[j+1] = normal_list[j+1], normal_list[j]
        
with open('normal_list.pickle', 'rb') as file:
    normal_list = pickle.load(file)        
bubble_sort(normal_list)
print(normal_list[:10])
print(normal_list[-10:])

上面一段代碼的運(yùn)行結(jié)果如下：

bubble_sort function used 7858.98 ms
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[6991, 6992, 6993, 6994, 6995, 6996, 6997, 6998, 6999, 7000]

2.選擇排序

@timer
def select_sort(normal_list):
    length = len(normal_list)
    new_list = []
    for i in range(length, 1, -1):
        max_index = 0
        max_value = normal_list[0]
        for j in range(1, i):
            if normal_list[j] > max_value:
                max_value = normal_list[j]
                max_index = j
        normal_list[i-1], normal_list[max_index] = normal_list[max_index], normal_list[i-1] 

with open('normal_list.pickle', 'rb') as file:
    normal_list = pickle.load(file)        
select_sort(normal_list)
print(normal_list[:10])
print(normal_list[-10:])

上面一段代碼的運(yùn)行結(jié)果如下：

select_sort function used 2018.90 ms
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[6991, 6992, 6993, 6994, 6995, 6996, 6997, 6998, 6999, 7000]

3.結(jié)論

雖然冒泡排序和選擇排序的時(shí)間復(fù)雜度都是O(n^2)，但是經(jīng)過實(shí)踐檢驗(yàn)，在python實(shí)現(xiàn)2種排序算法后，選擇排序花費(fèi)的時(shí)間明顯第冒泡排序花費(fèi)的時(shí)間。