上篇文章學(xué)習(xí)了算法入門——順序查找、二分查找，這篇文章我們學(xué)習(xí)算法入門——冒泡排序、選擇排序。

冒泡排序

冒泡排序是將列表中每?jī)蓚€(gè)相鄰的元素作對(duì)比，當(dāng)前面的元素比后面的元素大時(shí)，則交換這兩個(gè)元素。當(dāng)然，也可以當(dāng)前面的元素比后面的元素小時(shí)，就進(jìn)行交換。

其基本原理如下圖所示：

如上圖所示，每循環(huán)一次就可以把列表中最大的元素放在最后面，也就是每一趟把最大的元素放在最后面。

在冒泡排序中，想要排序完成，最壞的情況是執(zhí)行列表長(zhǎng)度-1趟。

示例代碼如下：

def bubble_sort(li):
    for i in range(len(li)-1):  # 第i趟
        for j in range(len(li)-i-1):    # 箭頭
            if li[j]>li[j+1]:          # 當(dāng)前面的元素大于后面的元素，則進(jìn)行交換
                li[j],li[j+1]=li[j+1],li[j]
        print(li)
bubble_sort([3,2,5,4,1])

運(yùn)行結(jié)果如下：

當(dāng)我們需要降序排序時(shí)，只需要把第四行代碼的大于號(hào)改為小于號(hào)即可。

冒泡排序的時(shí)間復(fù)雜度為：O(n2)

優(yōu)化冒泡排序

當(dāng)我們要排序的列表是已經(jīng)按順序排好了的，那么當(dāng)我們使用上面的代碼進(jìn)行排序時(shí)，是不是做了無(wú)用功呢？那么我們可以創(chuàng)建一個(gè)標(biāo)志位，當(dāng)執(zhí)行一趟沒(méi)有發(fā)生變化時(shí)，就認(rèn)為該列表已經(jīng)按照順序排好了，示例代碼如下：

def bubble_sort(li):
    for i in range(len(li)-1):  # 第i趟
        exchange=False                  # 沒(méi)有進(jìn)行交換
        for j in range(len(li)-i-1):    # 箭頭
            if li[j]>li[j+1]:
                li[j],li[j+1]=li[j+1],li[j]
                exchange = True         # 進(jìn)行了交換
        if exchange==False:             # 當(dāng)exchange=False時(shí)，表示沒(méi)有進(jìn)行交換，則退出循環(huán)
            return
        print(li)
bubble_sort([3,2,1,4,5,6])

運(yùn)行結(jié)果如下圖所示：

選擇排序

簡(jiǎn)單的選擇排序是創(chuàng)建一個(gè)新列表，每次循環(huán)遍歷得出列表中最小的元素，把最小的元素保存新列表中并在舊列表中刪除最小的元素，示例代碼如下：

def select_sort_simple(li):
    li_new=[]              # 新列表保存排好序的元素
    for i in range(len(li)):
        min_val=min(li)           # 通過(guò)min函數(shù)來(lái)獲取列表最小的元素
        li_new.append(min_val)   # 將最小的元素保存在新列表中
        li.remove(min_val)      # 將最小的元素在舊列表中刪除
        print('新列表元素：',li_new,'舊列表元素',li)
    return li_new

li=[1,3,52,5,2,5,8,7,9]
print(select_sort_simple(li))

運(yùn)行結(jié)果如下：

時(shí)間復(fù)雜度是不是O(n平方)呢，答案是不是的，因?yàn)樵诶锩嫔婕傲薬ppend()、remove()方法，這兩個(gè)時(shí)間復(fù)雜度不為O(1)。

當(dāng)原列表中有相同的元素時(shí)，remove()會(huì)把相同元素都刪除，同時(shí)，在空間復(fù)雜度中，假設(shè)一個(gè)列表的內(nèi)存為1GB，那么新建的列表內(nèi)存也為1GB，這樣使原來(lái)內(nèi)存為1GB的程序變?yōu)?GB。

優(yōu)化選擇排序

優(yōu)化選擇排序是首先假設(shè)列表的第一個(gè)元素是最小元素，在循環(huán)遍歷其他元素作對(duì)比，當(dāng)其他元素比假設(shè)元素小時(shí)，則交換兩者位置。示例代碼如下：

li = [2, 1, 52, 5, 3, 8, 7, 9]
def select_sort(li):
    for i in range(len(li) - 1):
        min_loc = i                         # 假設(shè)i為最小值的下標(biāo)
        for j in range(i + 1, len(li)):     # 循環(huán)遍歷
            if li[j] < li[min_loc]:
                min_loc = j                # 獲取最小的值下標(biāo)
        if min_loc != i:
            li[i], li[min_loc] = li[min_loc], li[i]  # 將下標(biāo)為i的值與最小值的下標(biāo)交換位置
        print(li)
select_sort(li)

運(yùn)行結(jié)果如下：

優(yōu)化后的選擇排序時(shí)間復(fù)雜度為：O(n2)

好了，關(guān)于算法入門——冒泡排序、選擇排序就學(xué)到這里了，下篇文章我們學(xué)習(xí)算法入門——插入排序、快速排序。

公眾號(hào)：白巧克力LIN

該公眾號(hào)發(fā)布Python、數(shù)據(jù)庫(kù)、Linux、Flask、自動(dòng)化測(cè)試、Git、算法等相關(guān)文章！