排序是什么

排序：將一組“無序”的記錄序列調整為“有序”的記錄序列

串列排序

串列排序：將無序串列變為有序串列

輸入：串列

輸出：有序串列

順序的型別：升序（從小到大）與降序（從大到小）

內置排序函式：sort()

常見的排序演算法

排序基礎三人組：冒泡排序 選擇排序 插入排序

排序進階三人組：快速排序 堆排序 歸并排序

其他排序演算法：希爾排序 計數排序 基數排序 桶排序

（可能歸納不全，但保證管用）

冒泡排序

什么是冒泡排序

冒泡排序（Bubble Sort）是一種簡單直觀的排序演算法，它重復地走訪要排序的數列，依次比較兩個元素，如果他們的順序錯誤就把他們交換過來，走訪數列的作業是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成，這個演算法的名字由來是因為越小的元素會經由交換慢慢"浮"到數列的頂端，

簡單來說，串列每兩個相鄰的數，如果前面的比后面的大則交換這兩個數，一趟排序完成后，則無序區減少一個數，有序區增加一個數，（每一趟冒出一個無序區最大的數--->冒泡排序）

圖片來自菜鳥教程

代碼講解

# 冒泡排序初級代碼

import random

def bubble_sort(lst):

    for i in range(len(lst) - 1):  # 表示第i趟,此處也可以直接用len(lst),但是直接用len(lst)會多走了最后一遍

        for j in range(len(lst)-i-1):  # 表示箭頭（下標）可移動的無序區范圍，比如長為10的串列，i取值則是0-9，第二次查找則無序區的長度為10-i(此時是1，第一次是0)-1（-1因為是根據下標查找）=8，因此箭頭范圍0-8

            if lst[j] > lst[j+1]: # 此時是升序排序，>改為<則改為了降序

                lst[j],lst[j+1] = lst[j+1],lst[j]

        print(f"第{i+1}趟后的串列為：{lst}")  # 查看排序程序

 

lst1 = [random.randint(0,10000) for i in range(5)]

print(f"初始串列:{lst1}")

bubble_sort(lst1)

# 結果

# 初始串列:[3053, 8957, 2153, 4502, 2518]

# 第1趟后的串列為：[3053, 2153, 4502, 2518, 8957]

# 第2趟后的串列為：[2153, 3053, 2518, 4502, 8957]

# 第3趟后的串列為：[2153, 2518, 3053, 4502, 8957]

# 第4趟后的串列為：[2153, 2518, 3053, 4502, 8957]

lst2 = [1,2,3,8,7,6,5]

print(f"初始串列:{lst2}")

bubble_sort(lst2)

# 初始串列:[1, 2, 3, 8, 7, 6, 5]

# 第1趟后的串列為：[1, 2, 3, 7, 6, 5, 8]

# 第2趟后的串列為：[1, 2, 3, 6, 5, 7, 8]

# 第3趟后的串列為：[1, 2, 3, 5, 6, 7, 8]

# 第4趟后的串列為：[1, 2, 3, 5, 6, 7, 8]

# 第5趟后的串列為：[1, 2, 3, 5, 6, 7, 8]

# 第6趟后的串列為：[1, 2, 3, 5, 6, 7, 8]

此時我們發現冒泡排序多走路了一趟，第3趟和第6趟一樣，且第3趟已排好，那么如何對代碼進行改進？

代碼優化

# 改進后的代碼

def bubble_sort(lst):

    for i in range(len(lst) - 1):  # 表示第i趟

        exchange = False  # 每一趟做標記

        for j in range(len(lst)-i-1):  # 表示箭頭

            if lst[j] > lst[j+1]: # 此時是升序排序，>改為<則改為了降序

                lst[j],lst[j+1] = lst[j+1],lst[j]

                exchange = True  # 進行了交換，exchange標記為Ture

        print(f"第{i+1}趟后的串列為：{lst}")  # 查看排序程序

        if not exchange: # 如果沒有進行交換，直接回傳，優化的步驟

            return

lst2 = [1,2,3,8,7,6,5]

print("***改進后的冒泡排序***")

print(f"初始串列:{lst2}")

bubble_sort(lst2)

# 結果

# ***改進后的冒泡排序***

# 初始串列:[1, 2, 3, 8, 7, 6, 5]

# 第1趟后的串列為：[1, 2, 3, 7, 6, 5, 8]

# 第2趟后的串列為：[1, 2, 3, 6, 5, 7, 8]

# 第3趟后的串列為：[1, 2, 3, 5, 6, 7, 8]

# 第4趟后的串列為：[1, 2, 3, 5, 6, 7, 8]

冒泡演算法的時間復雜度：O(n2)，兩層查找，

選擇排序

什么是選擇排序

選擇排序（Selection sort）是一種簡單直觀的排序演算法，它的作業原理如下，首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾，以此類推，直到所有元素均排序完畢，

簡單來說，選擇排序就是每一趟排序記錄最小的數，并放到第一個位置，在一趟排序記錄串列中無序區最小的數，放到有序區第二個位置…….以此回圈，直到只剩最后一個數時，此數絕對是最大的數，

此演算法的關鍵點時：有序區和無序區以及無序區最小數的位置，

圖片來自菜鳥教程

代碼講解

簡單易理解的選擇排序

def select_sort_simple(lst):

    new_lst = []

    for i in range(len(lst)):

        min_val = min(lst)

        new_lst.append(min_val)

        lst.remove(min_val)

    return new_lst

 

lst1 = [3,2,4,13,11,8]

result = select_sort_simple(lst1)

print(result)

# 結果

# [2, 3, 4, 8, 11, 13]

思考：該代碼有什么不足之處？或需要改進的地方？

1.建立新的串列占用了記憶體

2.時間復雜度較大，O(n^2)

接下來我們對串列進行優化

優化后的選擇排序代碼

def select_sort(lst):

    for i in range(len(lst) - 1):  # i代表第幾趟

        min_location = i # 最小位置的標記，第一次默認最小的數為無序區的第一個，即下標為i

        for j in range(i+1,len(lst)): # 從i開始相當于自己和自己比了一次，此步驟多余，因此從i+1開始

            if lst[j] < lst[min_location]:

                min_location = j

        lst[i],lst[min_location] = lst[min_location],lst[i] # 最小的值和有序區的最后一個值進行交換

        print(f"第{i + 1}趟后的串列為：{lst}")

 

 

lst1 = [3,2,4,13,11,8]

select_sort(lst1)

# 結果

# 第1趟后的串列為：[2, 3, 4, 13, 11, 8]

# 第2趟后的串列為：[2, 3, 4, 13, 11, 8]

# 第3趟后的串列為：[2, 3, 4, 13, 11, 8]

# 第4趟后的串列為：[2, 3, 4, 8, 11, 13]

# 第5趟后的串列為：[2, 3, 4, 8, 11, 13]

選擇排序的時間復雜度：O(n2)(兩層回圈)

插入排序

什么是插入排序？

先舉個生活實體

假設，你的手上有一副排好順序的牌（有序區），此時你需要從還沒摸完的牌（無序區）里摸一張牌，插入到已有牌的手里，直到摸完牌（從無序去），最后手上的牌（有序區）也排好序了，

插入排序（英語：Insertion Sort）的作業原理是通過構建有序序列，對于未排序資料，在已排序序列中從后向前掃描，找到相應位置并插入，

圖片來自菜鳥教程

代碼講解

def insert_sort(lst):

    for i in range(1,len(lst)):  # i表示摸到的牌的下標

        tmp = lst[i] # tmp代表摸到的牌

        j = i - 1 # j代表的是手里的牌的下標，手上自動已有第一張牌

        while lst[j] > tmp and j >= 0: # 需要移動有序區牌的情況

            lst[j+1] = lst[j]

            j -= 1

        lst[j+1] = tmp  # lst[j+1]是用來存放要插入的牌

        print(f"第{i}趟的串列：{lst}")

 

lst1 = [3,2,5,8,6,9,7]

print(f"原串列{lst1}")

insert_sort(lst1)

# 結果原串列[3, 2, 5, 8, 6, 9, 7]

# 第1趟的串列：[2, 3, 5, 8, 6, 9, 7]

# 第2趟的串列：[2, 3, 5, 8, 6, 9, 7]

# 第3趟的串列：[2, 3, 5, 8, 6, 9, 7]

# 第4趟的串列：[2, 3, 5, 6, 8, 9, 7]

# 第5趟的串列：[2, 3, 5, 6, 8, 9, 7]

# 第6趟的串列：[2, 3, 5, 6, 7, 8, 9]

插入排序時間復雜度：O(n2)

冒泡排序、選擇排序、插入排序小總結

1.三種排序方法的時間復雜度都是O(n2)

2.三種演算法都屬于原地排序，為創建新的串列

3.效率較低

思考：三種演算法效率如何體現

現在利用裝飾器，以冒泡排序為例子計算一下運算時間

from runtime import *

 

@runtime

def bubble_sort(lst):

    for i in range(len(lst) - 1):  # 表示第i趟

        exchange = False  # 每一趟做標記

        for j in range(len(lst)-i-1):  # 表示箭頭

            if lst[j] > lst[j+1]: # 此時是升序排序，>改為<則改為了降序

                lst[j],lst[j+1] = lst[j+1],lst[j]

                exchange = True  # 進行了交換，exchange標記為Ture

        # print(f"第{i+1}趟后的串列為：{lst}")  # 查看排序程序

        if not exchange: # 如果沒有進行交換，直接回傳，優化的步驟

            return

 

lst = list(range(10000))

random.shuffle(lst)

bubble_sort(lst)

# 結果

# bubble_sort執行用時12.76702880859375s

我們發現當串列長度比較長時，冒泡排序需要的時間很長（相對于機器的運算）

那么是否有時間復雜度更低的排序演算法呢？

答案是肯定有的，明天超超來解密！