lowb三人組

• 冒泡
• 選擇
• 插入
• 算法關(guān)鍵點(diǎn)：有序區(qū)，無序區(qū)

冒泡：

• 首先，列表每兩個(gè)相鄰的數(shù)，如果前面的比后面的大，那么交換這兩個(gè)數(shù)。
• 關(guān)鍵點(diǎn)：趟，無序區(qū)

# 如果冒泡排序中，執(zhí)行了一趟而沒有交換位置，那么它已經(jīng)是有序狀態(tài)，可以直接結(jié)束算法。
def bubble_sort(li):
    for i in range(len(li)-1):
        # i代表趟
        # 第 i 趟時(shí)：無序區(qū)range(len(li)-i) 
        # 因?yàn)樽詈笠粋€(gè)是固定的不需要再比較再挪動(dòng)so -1
        flag = False
        for j in range(len(li)-i-1):
            if li[j] > li[j+1]:
                li[j],li[j+1] = li[j+1],li[j]
                flag = True
        if not flag:
            return

選擇：

• 在一堆大小不一的球中，進(jìn)行選擇(以從小到大，先選最小球?yàn)槔?。
  1. 選擇一個(gè)基準(zhǔn)球。
  2. 將剩下的球與基準(zhǔn)球比較如果小于基準(zhǔn)求，則交換位置。
  3. 第一輪過后，獲得最小的球。
  4. 執(zhí)行123步。

時(shí)間復(fù)雜度：O(n^2).  需要進(jìn)行的比較次數(shù)為第一輪 n-1，n-2....1, 總的比較次數(shù)為 n*(n-1)/2

# 與冒泡只有一點(diǎn)點(diǎn)差別
import random
def select_sort(li):
    for i in range(len(li)-1):
        min_loc = i 
        for j in range(i+1,len(li)-i-1):
            if li[j] > li[min_loc]:
                min_loc = j
            else:
                li[i],li[min_loc] = li[min_loc],li[i]

插入

• 思路：
  1. 列表被分為有序區(qū)和無序區(qū)兩個(gè)部分。最初有序區(qū)只有一個(gè)元素。
  2. 每次從無序區(qū)拿出一個(gè)元素，插入到有序區(qū)的位置，直到無序區(qū)變空。
  3. 在有序區(qū)，它也會(huì)依次去比較，把最小的排在最前面位置。
• 時(shí)間復(fù)雜度:

o(n^2)

# 思路：列表被分為有序去和無序區(qū)。最初有序區(qū)只有一個(gè)元素。
#      每次從無序區(qū)選擇一個(gè)元素，插入到有序區(qū)的位置，直到無序區(qū)變空。

from timewrap import exe_time
import random

@exe_time
def insert_sort(li):
    for i in range(1,len(li)):
        # i 是無序區(qū)第一張牌，默認(rèn)0位有序
        tmp = li[i] # tmp就是無序區(qū)的第一個(gè)元素,即摸到的牌
        j = i - 1   # 有序區(qū)的最后一個(gè)元素的索引
        while j >= 0 and tmp < li[j]:
            # j >= 0  如果沒有這句，index 會(huì) outof。
            # 因?yàn)槲乙炎钚〉闹捣旁谧钋懊妫峭ㄟ^和前面一個(gè)值比較來的位置。
            # 但是第一個(gè)元素前面沒有值了，所以只能通過判斷來讓最小的值放在索引為0的位置上。
            li[j+1] = li[j]
            j -= 1
        li[j+1] = tmp


# n 是我拿到的值，
# J 是n前面的一個(gè)值，就是要比的值。
# 其實(shí)你看似放在某某前面，但其實(shí)是放在某某某的后面。
li = list(range(100))
random.shuffle(li)
print(li)
insert_sort(li)
print(li)

到這，排序lowB三人組完結(jié)。????????????

下一篇寫快速排序