十大經典排序算法--python實作

文章目錄

• 一、算法分類
• 二、算法複雜度
• 三、排序算法
• • 3.1 冒泡排序
  • • 3.1.1 算法描述
    • 3.1.2 動圖示範
    • 3.1.3 說明
    • 3.1.4 代碼實作
  • 3.2 選擇排序
  • • 3.2.1 算法步驟
    • 3.2.2 動圖示範
    • 3.2.3 代碼實作
  • 3.3 插入排序
  • • 3.3.1 算法步驟
    • 3.3.2 動圖示範
    • 3.3.3 代碼實作
  • 3.4 希爾排序
  • • 3.4.1 算法步驟
    • 3.4.2 動圖示範
    • 3.4.3 代碼實作
  • 3.5 歸并排序
  • • 3.5.1 算法步驟
    • 3.5.2 動圖示範
    • 3.5.3 代碼實作
  • 3.6 快速排序
  • • 3.6.1 算法步驟
    • 3.6.2 動圖示範
    • 3.6.3 代碼實作
  • 3.7 堆排序
  • • 3.7.1 算法步驟
    • 3.7.2 動圖示範
    • 3.7.3 代碼實作
  • 3.8 計數排序
  • • 3.8.1 算法步驟
    • 3.8.2 動圖示範
    • 3.8.3 代碼實作
  • 3.9 桶排序
  • • 3.9.1 說明
    • 3.9.2 圖像示範
    • 3.9.3 代碼實作
  • 3.10 基數排序
  • • 3.10.1 算法比較
    • 3.10.2 LSD基數排序動圖示範
    • 3.10.3 代碼實作

一、算法分類

十種常見排序算法可以分為兩大類：

• 比較類排序：通過比較來決定元素間的相對次序，由于其時間複雜度不能突破O(nlogn)，是以也稱為非線性時間比較類排序。
• 非比較類排序：不通過比較來決定元素間的相對次序，它可以突破基于比較排序的時間下界，以線性時間運作，是以也稱為線性時間非比較類排序。

二、算法複雜度

穩定：如果a原本在b前面，而a=b，排序之後a仍然在b的前面。

不穩定：如果a原本在b的前面，而a=b，排序之後 a 可能會出現在 b 的後面。

時間複雜度：對排序資料的總的操作次數。反映當n變化時，操作次數呈現什麼規律。

空間複雜度：是指算法在計算機内執行時所需存儲空間的度量，它也是資料規模n的函數。

三、排序算法

3.1 冒泡排序

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

3.1.1 算法描述

• 比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
• 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對，這樣在最後的元素應該會是最大的數；
• 針對所有的元素重複以上的步驟，除了最後一個；
• 重複步驟1~3，直到排序完成。

3.1.2 動圖示範

3.1.3 說明

最快：當輸入的資料已經是正序時（都已經是正序了，不需要冒泡排序）

最慢：當輸入的資料是反序時（寫一個for 循環反序輸出資料即可）

3.1.4 代碼實作

def bubbleSort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr
           

優化版：

def bubbleSort(arr):
    for i in range(len(arr) - 1, 0, -1):  # 反向周遊
        for j in range(0, i):  # 由于最右側的值已經有序，不再比較，每次都減少周遊次數
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr
           

• 冒泡排序第1次周遊後會将最大值放到最右邊，這個最大值也是全局最大值。
• 标準冒泡排序的每一次周遊都會比較全部的元素，雖然最右側的值已經是最大值了。
• 改進之後，每次周遊後的最大值，次大值，等等會固定在右側，避免了重複比較。

3.2 選擇排序

選擇排序是一種簡單直覺的排序算法，無論什麼資料進去都是 O(n²) 的時間複雜度。是以用到它的時候，資料規模越小越好。唯一的好處可能就是不占用額外的記憶體空間。

3.2.1 算法步驟

• 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
• 再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。
• 重複第二步，直到所有元素均排序完畢。

3.2.2 動圖示範

3.2.3 代碼實作

def selectionSort(arr):
    for i in range(len(arr) - 1):
        # 記錄最小數的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小數時，将 i 和最小數進行交換
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr
           

3.3 插入排序

插入排序的代碼實作雖然沒有冒泡排序和選擇排序那麼簡單粗暴，但它的原理應該是最容易了解的了，因為隻要打過撲克牌的人都應該能夠秒懂。插入排序是一種最簡單直覺的排序算法，它的工作原理是通過建構有序序列，對于未排序資料，在已排序序列中從後向前掃描，找到相應位置并插入。

插入排序和冒泡排序一樣，也有一種優化算法，叫做拆半插入。

3.3.1 算法步驟

• 将第一待排序序列第一個元素看做一個有序序列，把第二個元素到最後一個元素當成是未排序序列。
• 從頭到尾依次掃描未排序序列，将掃描到的每個元素插入有序序列的适當位置。（如果待插入的元素與有序序列中的某個元素相等，則将待插入元素插入到相等元素的後面。）

3.3.2 動圖示範

3.3.3 代碼實作

def insertionSort(arr):
    for i in range(len(arr)):
        preIndex = i-1
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex+1] = arr[preIndex]
            preIndex-=1
        arr[preIndex+1] = current
    return arr
           

3.4 希爾排序

希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩定排序算法。

希爾排序是基于插入排序的以下兩點性質而提出改進方法的：

• 插入排序在對幾乎已經排好序的資料操作時，效率高，即可以達到線性排序的效率；
• 但插入排序一般來說是低效的，因為插入排序每次隻能将資料移動一位；

希爾排序的基本思想是：先将整個待排序的記錄序列分割成為若幹子序列分别進行直接插入排序，待整個序列中的記錄"基本有序"時，再對全體記錄進行依次直接插入排序。

3.4.1 算法步驟

選擇一個增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

按增量序列個數 k，對序列進行 k 趟排序；

每趟排序，根據對應的增量 ti，将待排序列分割成若幹長度為 m 的子序列，分别對各子表進行直接插入排序。僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

3.4.2 動圖示範

3.4.3 代碼實作

def shellSort(arr):
    import math
    gap=1
    while(gap < len(arr)/3):
        gap = gap*3+1
    while gap > 0:
        for i in range(gap,len(arr)):
            temp = arr[i]
            j = i-gap
            while j >=0 and arr[j] > temp:
                arr[j+gap]=arr[j]
                j-=gap
            arr[j+gap] = temp
        gap = math.floor(gap/3)
    return arr
           

3.5 歸并排序

歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。

作為一種典型的分而治之思想的算法應用，歸并排序的實作由兩種方法：

• 自上而下的遞歸（所有遞歸的方法都可以用疊代重寫，是以就有了第 2 種方法）；
• 自下而上的疊代；

3.5.1 算法步驟

• 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并後的序列；
• 設定兩個指針，最初位置分别為兩個已經排序序列的起始位置；
• 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置；
• 重複步驟 3 直到某一指針達到序列尾；
• 将另一序列剩下的所有元素直接複制到合并序列尾。

3.5.2 動圖示範

3.5.3 代碼實作

def mergeSort(arr):
    import math
    if(len(arr)<2):
        return arr
    middle = math.floor(len(arr)/2)
    left, right = arr[0:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(right))

def merge(left,right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0));
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0));
    return result
           

3.6 快速排序

快速排序是由東尼·霍爾所發展的一種排序算法。在平均狀況下，排序 n 個項目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因為它的内部循環（inner loop）可以在大部分的架構上很有效率地被實作出來。

快速排序使用分治法（Divide and conquer）政策來把一個串行（list）分為兩個子串行（sub-lists）。

快速排序又是一種分而治之思想在排序算法上的典型應用。本質上來看，快速排序應該算是在冒泡排序基礎上的遞歸分治法。

快速排序的名字起的是簡單粗暴，因為一聽到這個名字你就知道它存在的意義，就是快，而且效率高！它是處理大資料最快的排序算法之一了。雖然 Worst Case 的時間複雜度達到了 O(n²)，但是人家就是優秀，在大多數情況下都比平均時間複雜度為 O(n logn) 的排序算法表現要更好，這是因為快速排序的最壞運作情況是 O(n²)，比如說順序數列的快排。但它的平攤期望時間是 O(nlogn)，且 O(nlogn) 記号中隐含的常數因子很小，比複雜度穩定等于 O(nlogn) 的歸并排序要小很多。是以，對絕大多數順序性較弱的随機數列而言，快速排序總是優于歸并排序。

3.6.1 算法步驟

• 從數列中挑出一個元素，稱為 “基準”（pivot）;
• 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處于數列的中間位置。這個稱為分區（partition）操作；
• 遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序；

3.6.2 動圖示範

3.6.3 代碼實作

def quickSort(arr, left=None, right=None):
    left = 0 if not isinstance(left,(int, float)) else left
    right = len(arr)-1 if not isinstance(right,(int, float)) else right
    if left < right:
        partitionIndex = partition(arr, left, right)
        quickSort(arr, left, partitionIndex-1)
        quickSort(arr, partitionIndex+1, right)
    return arr

def partition(arr, left, right):
    pivot = left
    index = pivot+1
    i = index
    while  i <= right:
        if arr[i] < arr[pivot]:
            swap(arr, i, index)
            index+=1
        i+=1
    swap(arr,pivot,index-1)
    return index-1

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]
           

3.7 堆排序

堆排序（Heapsort）是指利用堆這種資料結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法：

• 大頂堆：每個節點的值都大于或等于其子節點的值，在堆排序算法中用于升序排列；

• 小頂堆：每個節點的值都小于或等于其子節點的值，在堆排序算法中用于降序排列；

  堆排序的平均時間複雜度為 Ο(nlogn)。

3.7.1 算法步驟

• 建立一個堆 H[0……n-1]；
• 把堆首（最大值）和堆尾互換；
• 把堆的尺寸縮小 1，并調用 shift_down(0)，目的是把新的數組頂端資料調整到相應位置；
• 重複步驟 2，直到堆的尺寸為 1。

3.7.2 動圖示範

3.7.3 代碼實作

def buildMaxHeap(arr):
    import math
    for i in range(math.floor(len(arr)/2),-1,-1):
        heapify(arr,i)

def heapify(arr, i):
    left = 2*i+1
    right = 2*i+2
    largest = i
    if left < arrLen and arr[left] > arr[largest]:
        largest = left
    if right < arrLen and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        swap(arr, i, largest)
        heapify(arr, largest)

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def heapSort(arr):
    global arrLen
    arrLen = len(arr)
    buildMaxHeap(arr)
    for i in range(len(arr)-1,0,-1):
        swap(arr,0,i)
        arrLen -=1
        heapify(arr, 0)
    return arr
           

3.8 計數排序

計數排序的核心在于将輸入的資料值轉化為鍵存儲在額外開辟的數組空間中。作為一種線性時間複雜度的排序，計數排序要求輸入的資料必須是有确定範圍的整數。

計數排序的特征:

當輸入的元素是 n 個 0 到 k 之間的整數時，它的運作時間是 Θ(n + k)。計數排序不是比較排序，排序的速度快于任何比較排序算法。

由于用來計數的數組C的長度取決于待排序數組中資料的範圍（等于待排序數組的最大值與最小值的差加上1），這使得計數排序對于資料範圍很大的數組，需要大量時間和記憶體。例如：計數排序是用來排序0到100之間的數字的最好的算法，但是它不适合按字母順序排序人名。但是，計數排序可以用在基數排序中的算法來排序資料範圍很大的數組。

通俗地了解，例如有 10 個年齡不同的人，統計出有 8 個人的年齡比 A 小，那 A 的年齡就排在第 9 位,用這個方法可以得到其他每個人的位置,也就排好了序。當然，年齡有重複時需要特殊處理（保證穩定性），這就是為什麼最後要反向填充目标數組，以及将每個數字的統計減去 1 的原因。

3.8.1 算法步驟

• 找出待排序的數組中最大和最小的元素
• 統計數組中每個值為i的元素出現的次數，存入數組C的第i項
• 對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）
• 反向填充目标數組：将每個元素i放在新數組的第C(i)項，每放一個元素就将C(i)減去1

3.8.2 動圖示範

3.8.3 代碼實作

def countingSort(arr, maxValue):
    bucketLen = maxValue+1
    bucket = [0]*bucketLen
    sortedIndex =0
    arrLen = len(arr)
    for i in range(arrLen):
        if not bucket[arr[i]]:
            bucket[arr[i]]=0
        bucket[arr[i]]+=1
    for j in range(bucketLen):
        while bucket[j]>0:
            arr[sortedIndex] = j
            sortedIndex+=1
            bucket[j]-=1
    return arr
           

3.9 桶排序

桶排序是計數排序的更新版。它利用了函數的映射關系，高效與否的關鍵就在于這個映射函數的确定。為了使桶排序更加高效，我們需要做到這兩點：

• 在額外空間充足的情況下，盡量增大桶的數量

• 使用的映射函數能夠将輸入的 N 個資料均勻的配置設定到 K 個桶中

  同時，對于桶中元素的排序，選擇何種比較排序算法對于性能的影響至關重要。

3.9.1 說明

最快：當輸入的資料可以均勻的配置設定到每一個桶中。

最慢：當輸入的資料被配置設定到了同一個桶中。

3.9.2 圖像示範

元素分布在桶中：

然後，元素在每個桶中排序：

3.9.3 代碼實作

"""
程式說明：
    桶排序
    1）在額外空間充足的情況下，盡量增大桶的數量
    2）使用的映射函數能夠将輸入的 N 個資料均勻的配置設定到 K 個桶中
      個人了解，如果都是整數還可以用計數排序來計數統計然後排序，但是如果是一個連續空間内的排序，即統計的是一個浮點類型的數組成
      的數組，那麼，就無法開辟一個對應的空間使其一一對應的存儲。此時，我們需要建立一個帶有存儲範圍的空間，來存儲一定範圍内的元素
    空間複雜度：O(n)
    時間複雜度: O(n)
    穩定
"""
def bucket_sort_simplify(arr, max_num):
    """
    簡化版
    """
    buf = {i: [] for i in range(int(max_num)+1)}  # 不能使用[[]]*(max+1)，這樣建立的空間中各個[]是共享記憶體的
    arr_len = len(arr)
    for i in range(arr_len):
        num = arr[i]
        buf[int(num)].append(num)  # 将相應範圍内的資料加入到[]中
    arr = []
    for i in range(len(buf)):
        if buf[i]:
            arr.extend(sorted(buf[i]))  # 這裡還需要對一個範圍内的資料進行排序，然後再進行輸出
    return arr


if __name__ == "__main__":
    lis = [3.1, 4.2, 3.3, 3.5, 2.2, 2.7, 2.9, 2.1, 1.55, 4.456, 6.12, 5.2, 5.33, 6.0, 2.12]
    print(bucket_sort_simplify(lis, max(lis)))
           

3.10 基數排序

基數排序是一種非比較型整數排序算法，其原理是将整數按位數切割成不同的數字，然後按每個位數分别比較。由于整數也可以表達字元串（比如名字或日期）和特定格式的浮點數，是以基數排序也不是隻能使用于整數。

3.10.1 算法比較

基數排序 vs 計數排序 vs 桶排序

基數排序有兩種方法：

這三種排序算法都利用了桶的概念，但對桶的使用方法上有明顯差異：

• 基數排序：根據鍵值的每位數字來配置設定桶；
• 計數排序：每個桶隻存儲單一鍵值；
• 桶排序：每個桶存儲一定範圍的數值；

3.10.2 LSD基數排序動圖示範

3.10.3 代碼實作

def radix_sort(s):
    """基數排序"""
    i = 0 # 記錄目前正在排拿一位，最低位為1
    max_num = max(s)  # 最大值
    j = len(str(max_num))  # 記錄最大值的位數
    while i < j:
        bucket_list =[[] for _ in range(10)] #初始化桶數組
        for x in s:
            bucket_list[int(x / (10**i)) % 10].append(x) # 找到位置放入桶數組
        print(bucket_list)
        s.clear()
        for x in bucket_list:   # 放回原序列
            for y in x:
                s.append(y)
        i += 1

if __name__ == '__main__':
    a = [334,5,67,345,7,345345,99,4,23,78,45,1,3453,23424]
    radix_sort(a)
    print(a)