排序 in Python

介紹

本節內容將介紹幾種常見的排序演算法（主要包含冒泡排序，選擇排序，插入排序，希爾排序，歸併排序，快速排序，堆排序，桶排序）的演算法原理，演算法複雜度的分析，以及如何實現。

知識點

冒泡排序
選擇排序
插入排序
希爾排序
歸併排序
快速排序
堆排序
計數排序
桶排序

排序演算法

所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。排序演算法，就是如何使得記錄按照要求排列的方法。排序演算法在很多領域得到相當地重視，尤其是在大量數據的處理方面。一個優秀的演算法可以節省大量的資源。

註：定義來自百度百科。

在學習演算法的時候，需要學會理解演算法是如何實現的，掌握其演算法的原理，以及如何判斷演算法的優越性。

我們將在接下來的內容，逐步理解這些簡單的搜索演算法。

冒泡排序

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

演算法原理

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

複雜度分析

最壞複雜度: 時間複雜度為 O(n^2)

最好複雜度：時間複雜度為 O(n)

平均複雜度: 時間複雜度為 O(n^2)

實現

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

參考代碼

注意：請務必自己獨立思考解決問題之後再對照參考答案，一開始直接看參考答案收穫不大。

def bubble_sort(sequence): for i in range(1,len(sequence)): for j in range(0,len(sequence)-i): if sequence[j]>sequence[j+1]: sequence[j],sequence[j+1]=sequence[j+1],sequence[j] return sequence if __name__ == __main__: sequence= [12, 27, 46, 16, 25, 37, 22, 29, 15, 47, 48, 34] print(sequence) print(bubble_sort(sequence))

選擇排序

選擇排序是一種簡單直觀的排序演算法，無論什麼數據進去都是 O(n^2) 的時間複雜度。所以用到它的時候，數據規模越小越好。唯一的好處可能就是不佔用額外的內存空間了吧

演算法原理

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

複雜度分析

最壞複雜度: 時間複雜度為 O(n^2)

最好複雜度：時間複雜度為 O(n^2)

平均複雜度: 時間複雜度為 O(n^2)

實現

def select_sort(sequence): for i in range(len(sequence)-1): minIndex=i #記錄最小數的索引 for j in range(i+1,len(sequence)): if sequence[j]<sequence[minIndex]: minIndex=j sequence[minIndex],sequence[i]=sequence[i],sequence[minIndex] #將該數放到已排序序列的末尾 return sequence

插入排序

插入排序（Insertion Sort）的演算法描述是一種簡單直觀的排序演算法。它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。

演算法原理

從第一個元素開始，該元素可以認為已經被排序
取出下一個元素，在已經排序的元素序列中從後向前掃描
如果該元素(已排序)大於新元素，將該元素移到下一位置
重複步驟 3，直到找到已排序的元素小於或者等於新元素的位置
將新元素插入到該位置後
重複步驟 2-5

複雜度分析

最壞複雜度: 時間複雜度為 O(n^2)

最好複雜度：時間複雜度為 O(n^2)

平均複雜度: 時間複雜度為 O(n^2)

實現

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

希爾排序

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

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

插入排序在對幾乎已經排好序的數據操作時，效率高，既可以達到線性排序的效率
但插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位。

演算法原理

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

選擇一個增量序列 t1,t2,...,tk,其中 ti>tj,tk=1
按增量序列的個數 k，對序列進行 k 趟排序
每趟排序，根據對應的增量 ti,將待排序序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

複雜度分析

最壞複雜度: 時間複雜度為 O(n(logn)^2)

最好複雜度：時間複雜度為 O(nlogn)

平均複雜度: 取決於間隔序列

實現

def shell_sort(sequence): gap=len(sequence) while gap >1: gap=gap//2 for i in range(gap,len(sequence)): for j in range(i%gap,i,gap): if sequence[i]<sequence[j]: sequence[i],sequence[j]=sequence[j],sequence[i] return sequence

歸併排序

歸併排序是建立在歸併操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱為 2-路歸併

演算法原理

歸併排序基本思想是：

把長度為 n 的輸入序列分成兩個長度為 n/2 的子序列
對這兩個子序列分別採用歸併排序
將兩個排序好的子序列合併成一個最終的排序序列

複雜度分析

最壞複雜度: 時間複雜度為 O(nlogn)

最好複雜度：時間複雜度為 O(nlogn)

平均複雜度: 時間複雜度為 O(nlogn)

實現

import math def merge_sort(sequence): if(len(sequence)<2): return sequence mid=math.floor(len(sequence)/2) left,right=sequence[0:mid],sequence[mid:] return merge(merge_sort(left),merge_sort(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

快速排序

快速排序的基本思想：通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。

演算法原理

歸併排序基本思想是：使用分治法來把一個串（list）分為兩個子串（sub-lists）

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

複雜度分析

最壞複雜度: 時間複雜度為 O(n^2)

最好複雜度：時間複雜度在 O(n) 和 O(nlogn)中間

平均複雜度: 時間複雜度為 O(nlogn)

實現

def quick_select(sequence): def recursive(begin,end): if begin>end: return left,right=begin,end pivot=sequence[left] while left < right: while left<right and sequence[right]>pivot: right=right-1 while left<right and sequence[left]<=pivot: left=left+1 sequence[left], sequence[right] = sequence[right], sequence[left] sequence[left], sequence[begin] = pivot, sequence[left] recursive(begin, left - 1) recursive(right + 1, end)

recursive(0, len(sequence) - 1)
return sequence

堆排序

堆排序（Heapsort）的基本思想：是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。

演算法原理

堆排序基本思想是：

將初始待排序關鍵字序列(R1,R2...Rn)構建成大頂堆，此堆為初始的無序區。
將堆頂元素 R1與最後一個元素 R[n]交換，此時得到新的無序區(R1,R2,...Rn-1)和新的有序區(Rn),且滿足 R[1,2...n-1]<=R[n]。
由於交換後新的堆頂 R1可能違反堆的性質，因此需要對當前無序區(R1,R2,...Rn-1)調整為新堆，然後再次將 R1與無序區最後一個元素交換，得到新的無序區(R1,R2...Rn-2)和新的有序區(Rn-1,Rn)。不斷重複此過程直到有序區的元素個數為 n-1，則整個排序過程完成。

複雜度分析

最壞複雜度: 時間複雜度為 O(nlogn)

最好複雜度：時間複雜度在 O(nlogn)

平均複雜度: 時間複雜度為 O(nlogn)

實現

import random def heap_sort(sequence): def heap_adjust(parent): child = 2 * parent + 1 # left child while child < len(heap): if child + 1 < len(heap): if heap[child + 1] > heap[child]: child =child+ 1 # right child if heap[parent] >= heap[child]: break heap[parent], heap[child] = heap[child], heap[parent] parent, child = child, 2 * child + 1

heap, sequence = sequence.copy(), []
for i in range(len(heap) // 2, -1, -1):
heap_adjust(i)
while len(heap) != 0:
heap[0], heap[-1] = heap[-1], heap[0]
sequence.insert(0, heap.pop())
heap_adjust(0)
return sequence
if __name__ == __main__:
sequence= [random.randint(1,10000) for i in range(50)]
print(sequence)
print(heap_sort(sequence))

計數排序

計數排序(Counting Sort)不是基於比較的排序演算法，其核心在於將輸入的數據值轉化為鍵存儲在額外開闢的數組空間中。作為一種線性時間複雜度的排序，計數排序要求輸入的數據必須是有確定範圍的整數

演算法原理

計數排序基本思想是：

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

複雜度分析

最壞複雜度: 時間複雜度為 O(n+k)

最好複雜度：時間複雜度在 O(n+k)

平均複雜度: 時間複雜度為 O(n+k)

實現

import random def counting_sort(sequence): if sequence == []: return [] sequence_len=len(sequence) sequence_max=max(sequence) #找出待排序的數組中最大的元素 sequence_min=min(sequence) #找出待排序的數組中最小的元素 counting_arr_length=sequence_max-sequence_min+1 counting_arr=[0]*counting_arr_length for number in sequence: counting_arr[number-sequence_min]+=1 #統計數組中元素出現次數 for i in range(1,counting_arr_length): #計數累加 counting_arr[i]=counting_arr[i]+counting_arr[i-1] ordered=[0]*sequence_len for i in range(sequence_len-1,0,-1): #反向填充目標數組 ordered[counting_arr[sequence[i]-sequence_min]-1]=sequence[i] counting_arr[sequence[i]-sequence_min]-=1 return ordered if __name__ == __main__: sequence=[random.randint(1,10000) for i in range(500)] print(sequence) print(counting_sort(sequence))

桶排序

桶排序是計數排序的升級版。它利用了函數的映射關係，高效與否的關鍵就在於這個映射函數的確定。桶排序 (Bucket sort)的工作的原理：假設輸入數據服從均勻分佈，將數據分到有限數量的桶裏，每個桶再分別排序（有可能再使用別的排序演算法或是以遞歸方式繼續使用桶排序進行排）

演算法原理

計數排序基本思想是：

設置一個定量的數組當作空桶
遍歷輸入數據，並且把數據一個一個放到對應的桶裏去
對每個不是空的桶進行排序
從不是空的桶裏把排好序的數據拼接起來

複雜度分析

最壞複雜度: 時間複雜度為 O(n+k)

最好複雜度：時間複雜度在 O(n)

平均複雜度: 時間複雜度為 O(n)

實現

import math import random DEFAULT_BUCKET_SIZE = 5 def insertion_sort(sequence): for index in range(1,len(sequence)): while(index>0 and sequence[index-1]>sequence[index]): sequence[index],sequence[index-1]=sequence[index-1],sequence[index] index=index-1 return sequence def bucket_sort(sequence, bucketSize=DEFAULT_BUCKET_SIZE): if(len(sequence) == 0): return [] minValue = sequence[0] maxValue = sequence[0] for i in range(0, len(sequence)): if sequence[i] < minValue: minValue = sequence[i] #尋找最小值 elif sequence[i] > maxValue: maxValue = sequence[i] #尋找最大值 bucketCount = math.floor((maxValue - minValue) / bucketSize) + 1 #桶的初始化 buckets = [] for i in range(0, bucketCount): buckets.append([]) for i in range(0, len(sequence)): #遍曆數據，將數據依次放進桶中 buckets[math.floor((sequence[i] - minValue) / bucketSize)].append(sequence[i]) sortedArray = [] for i in range(0, len(buckets)): #將每一個不是空的桶進行排序 insertion_sort(buckets[i]) for j in range(0, len(buckets[i])): sortedArray.append(buckets[i][j]) return sortedArray if __name__ == __main__: sequence=[random.randint(1,10000) for i in range(50)] print(sequence) print(bucket_sort(sequence))