在 List 相關的題型中，有一種叫做「排序」的題型。

排序相關的演算法，其實有很多，從最簡單的「泡沫排序法」、「選擇排序法」、「插入排序法」到進階的「合併排序法」、「快速排序法」等都是屬於排序演算法的範疇。而今天的主題就是「快速排序法」。

「泡沫排序法」、「選擇排序法」、「插入排序法」這三種演算法的原理其實差不多，都是不停地做交換的動作，差別在於交換的對象為何，我們先來介紹這三個排序演算法吧！

泡沫排序法 Bubble Sort

泡沫排序法確保每做完一次迴圈，未排序的數字中，最小的數字必定在數列的最左邊。作法是不斷交換相鄰的兩個元素。

# Given a unsorted list called data
def bubble_sort(data):
    n = len(data)
    for i in range(n):
        for j in range(n-1, i, -1):
            if data[j] < data[j-1]:
                data[j], data[j-1] = data[j-1], data[j]
    return data

選擇排序法 Selection Sort

選擇排序法將數列分成已排序資料與未排序資料，確保每做完一次迴圈，未排序的數字最小者會接在已排序資料的最後方。作法是將未排序數列的第一個數字與數列最小者交換。

def selection_sort(data):
    for i in range(len(data)-1):
        min_value_index = i
        for j in range(i+1, len(data)):
            if data[j] < data[min_value_index] :
                min_value_index = j
        data[i], data[min_value_index] = data[min_value_index], data[i]
    return data

插入排序法 Insertion Sort

插入排序法將數列分成排序資料與未排序資料，每一次迴圈都取未排序資料中的第一者，再將之插入以排序資料中。
註：Python有負數索引值，要特別注意迴圈的終止條件

def insertion_sort(data):
    for i in range(len(data)):
        key_index = i 
        while data[key_index - 1] > data[key_index] and key_index > 0:
              data[key_index - 1], data[key_index] = data[key_index], data[key_index - 1]
              key_index -= 1
    return data

快速排序法 Quick Sort

快入排序法的核心思想就是遞迴，將大單位分成小單位後，再以列表加法將之合起。Python 有列表加法的這個功能，所以在實作的過程為我們省去不少麻煩。

作法大致為：取列表中的最後一個元素作為比較基準（暫且叫做 key），大於 key 的元素與小於 key 的元素各自成一個列表。循環上述，直到每一個子列表都只有 1 或 0個元素。最後再以列表加法將他們全部串在一起（這部分會由遞迴代為執行）

舉個例子：排序 [6, 8, 4, 2, 9]

• [小於 key : 4, 2] + [key : 6] + [大於 key : 8, 9]
• [小於 key : 2] + [key : 4] + [key : 6] + [key : 8] + [大於 key : 9]
• 確認所有子列表都只有 0 或 1 個元素，合併之 ：[2, 4, 6, 8, 9]

def quick_sort(data):
    if len(data) <= 1:
        return data
    else:
        key = data.pop()
        greater_than_key = []
        lower_than_key = []
        for item in data :
            if item > key:
                greater_than_key.append(item)
            else:
                lower_than_key.append(item)
    return quick_sort(lower_than_key) + [key] + quick_sort(greater_than_key)

如果是使用非 Python 語言（e.g. C/C++），我們不會另外再開一個列表／陣列，因為在列表的結合上並不像 Python 的方便。取而代之的方法是形式上分割列表，即紀錄子列表的起始索引值和結束索引值，再將這個索引值範圍內的元素做排序（遞迴）。

熟悉 List 可以幫你省去很多時間，試試自己把上述的演算法都寫出來吧！

下一篇，我們來聊聊「堆疊 Stack」這個資料結構。