? 基礎排序算法

????????冒泡排序

思想就是將相鄰元素兩兩比較，當一個元素大于右側相鄰元素時，交換他們的位置，小于右側元素時，位置不變，最終序列中的最大元素，像氣泡一樣，到了最右側。

?

這時冒泡排序第一輪結束，數列最右側元素9的位置可認為是一個有序區，有序區目前有一個元素.

第二輪排序結束后，數列右側的有序區有了兩個元素.

?由于該排序算法每一輪都要遍歷所有元素，平均時間復雜度為O(n*n)

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]:   # 降序就改一下符號li[j],li[j+1]=li[j+1],li[j]   li=[random.randint(1,100) for i in range(20)]
bubble_sort(li)
print(li)

如果在某一趟排序中列表沒有發生變化,認為已經排好序，這時如果for循環遍歷就極大浪費時間，我們可以加每一趟遍歷前加一個標志位，在交換元素的代碼處加一個修改標志位，這樣就可以避免最壞情況出現.

def bubble_sort(li):for i in range(len(li)-1):exchange=Falsefor j in range(len(li)-i-1):if li[j]>li[j+1]:li[j],li[j+1]=li[j+1],li[j]exchange=Trueprint(li)  # 看每一趟的變化if not exchange:return

????????選擇排序

基礎思想為將列表中最小元素依次遍歷篩選出來，最終得到一個有序列表

def select_sort_simple(li):li_new=[]for i in range(len(li)):   # 一共需要拿i次min_val=min(li)li_new.append(min_val)li.remove(min_val)return li_new

這個算法雖然簡單但是浪費內存，我們可以在列表內部遍歷，找到最小元素后與第一個元素交換位置，左側有序區就有了第一個元素.

def select_sort(li):for i in range(len(li)-1):   # i趟,每次都把最小的放到前邊交換min_loc=i   # 默認第一個最小,與后邊遍歷比較for j in range(i+1,len(li)):if li[j]<li[min_loc]:min_loc=j    # 目前的最小元素索引li[i],li[min_loc]=li[min_loc],li[i]return li

? ? ? ? 插入排序

?

^ 初始時手里(有序區)只有一張牌(默認為元素第一個值)。

^ 每次從無序區(列表右側區)摸一張牌(依次遍歷)，插入到有序區的正確(按大小)位置。

def insert_sort(li):for i in range(1,len(li)):  # 功n-1趟,i表示摸到牌的下標tmp=li[i]  # 每次摸的牌j=i-1      # 手里最右側的while j>=0 and li[j]>tmp:    # 一直往左走li[j+1]=li[j]    # 右移j-=1li[j+1]=tmp   # 選好位置了

可以看出插入排序時間復雜度為O(n*n)

?

?