十大排序演算法總結（Python3實現）
- 2020 年 1 月 12 日
- 筆記
目錄
一、概述
排序演算法大概是hello world之後最經典的編程題目了，但這並不意味著簡單如hello world一樣的輸入輸出。排序的各種解決方法涵蓋了幾乎所有基本的演算法思想，你可以在任意一本演算法分析與設計的書籍中輕易找到排序演算法的例子；同時，熟練掌握各種排序演算法可以加深對各種數據結構的理解與運用，對編程能力也會起到很好的鍛煉效果。
小編在學習了數據結構、演算法分析設計、C/C++、Java、Python等之後，回顧所學發現見到最多的還是各種排序演算法，故決定做個總結。閱讀參考網上各路大神的部落格之後，寫下這篇部落格與大家交流。
基本的排序演算法在經過前人嘔心瀝血的研究下基本可以分為以下十種，當然除此之外，還有結合多種演算法思想基於他們的改進變種。在插入、選擇、交換這三大類基於比較的排序演算法中，時間複雜度會隨著優化程度在O(n^2)~O(nlogn)之間變化，希爾排序、快速排序、堆排序分別代表著傑出的優化策略。基於分治遞歸思想的歸併排序將待排數據像二叉樹一樣分化至最簡單的一個數排序問題，子問題合併時間複雜度可控制在O(n)，不難想到整體時間複雜度取決於樹的深度，即達到O(nlogn)。計數排序、桶排序、基數排序三種線性時間排序演算法本質上運用了相同的思想：先將數據按一定映射關係分組（桶），然後桶內排序，順序輸出。三種姑且稱為『桶』排序演算法在分組函數使用上不同，導致分組粒度不同，帶來的額外空間開銷出現差異。這三種排序演算法適用於數據滿足一定的條件，否則額外的空間開銷將無法承受。
#時間複雜度指平均時間複雜度
#n：數據規模 ；k：『桶』個數
二、演算法簡介及程式碼展示
1.冒泡排序
冒泡排序對數據操作n-1輪，每輪找出一個最大（小）值。
操作指對相鄰兩個數比較與交換，每輪會將一個最值交換到數據列首（尾），像冒泡一樣。
每輪操作O(n)次，共O（n）輪，時間複雜度O(n^2)。
額外空間開銷出在交換數據時那一個過渡空間，空間複雜度O(1)。
def BubbleSort(ls): n=len(ls) if n<=1: return ls for i in range (0,n): for j in range(0,n-i-1): if ls[j]>ls[j+1]: (ls[j],ls[j+1])=(ls[j+1],ls[j]) return ls x=input("請輸入待排序數列：n") y=x.split() arr=[] for i in y: arr.append(int(i)) arr=BubbleSort(arr) #print(arr) print("數列按序排列如下：") for i in arr: print(i,end=' ')2.簡單選擇排序
簡單選擇排序同樣對數據操作n-1輪，每輪找出一個最大（小）值。
操作指選擇，即未排序數逐個比較交換，爭奪最值位置，每輪將一個未排序位置上的數交換成已排序數，即每輪選一個最值。
每輪操作O(n)次，共O（n）輪，時間複雜度O(n^2)。
額外空間開銷出在交換數據時那一個過渡空間，空間複雜度O(1)。
def SelectSort(ls): n=len(ls) if n<=1: return ls for i in range(0,n-1): minIndex=i for j in range(i+1,n): #比較一遍，記錄索引不交換 if ls[j]<ls[minIndex]: minIndex=j if minIndex!=i: #按索引交換 (ls[minIndex],ls[i])=(ls[i],ls[minIndex]) return ls x=input("請輸入待排序數列：n") y=x.split() arr=[] for i in y: arr.append(int(i)) arr=SelectSort(arr) #print(arr) print("數列按序排列如下：") for i in arr: print(i,end=' ')3.簡單插入排序
簡單插入排序同樣操作n-1輪，每輪將一個未排序樹插入排好序列。
開始時默認第一個數有序，將剩餘n-1個數逐個插入。插入操作具體包括：比較確定插入位置，數據移位騰出合適空位
每輪操作O(n)次，共O（n）輪，時間複雜度O(n^2)。
額外空間開銷出在數據移位時那一個過渡空間，空間複雜度O(1)。
def InsertSort(ls): n=len(ls) if n<=1: return ls for i in range(1,n): j=i target=ls[i] #每次循環的一個待插入的數 while j>0 and target<ls[j-1]: #比較、後移，給target騰位置 ls[j]=ls[j-1] j=j-1 ls[j]=target #把target插到空位 return ls x=input("請輸入待排序數列：n") y=x.split() arr=[] for i in y: arr.append(int(i)) arr=InsertSort(arr) #print(arr) print("數列按序排列如下：") for i in arr: print(i,end=' ')4.堆排序
堆排序基於比較交換，是冒泡排序的優化。具體涉及大（小）頂堆的建立與調整。
大頂堆指任意一個父節點都不小於左右兩個孩子節點的完全二叉樹，根節點最大。
堆排序首先建立大頂堆（找出一個最大值），然後用最後一個葉子結點代替根節點後做大頂堆的調整（再找一個最大值），重複
以數組（列表）實現大頂堆時，從上到下，從左到右編號。父節點序號為n，則左右孩子節點序號分別為2*n+1、2*n+2
大頂堆的調整：將僅有根節點不滿足條件的完全二叉樹，調整為大頂堆的過程。
大頂堆調整方法：將根節點與較大一個兒子節點比較，不滿足條件則交換。
若發生交換，將被交換兒子節點視作根節點重複上一步
大頂堆的建立：從最後一個非葉子節點開始到根節點結束的一系列大頂堆調整過程。
堆排序的初始建堆過程比價複雜，對O(n)級別個非葉子節點進行堆調整操作O(logn)，時間複雜度O(nlogn)；之後每一次堆調整操作確定一個數的次序，時間複雜度O(nlogn)。合起來時間複雜度O(nlogn)
額外空間開銷出在調整堆過程，根節點下移交換時一個暫存空間，空間複雜度O(1)
def HeapSort(ls): def heapadjust(arr,start,end): #將以start為根節點的堆調整為大頂堆 temp=arr[start] son=2*start+1 while son<=end: if son<end and arr[son]<arr[son+1]: #找出左右孩子節點較大的 son+=1 if temp>=arr[son]: #判斷是否為大頂堆 break arr[start]=arr[son] #子節點上移 start=son #繼續向下比較 son=2*son+1 arr[start]=temp #將原堆頂插入正確位置 ####### n=len(ls) if n<=1: return ls #建立大頂堆 root=n//2-1 #最後一個非葉節點（完全二叉樹中） while(root>=0): heapadjust(ls,root,n-1) root-=1 #掐掉堆頂後調整堆 i=n-1 while(i>=0): (ls[0],ls[i])=(ls[i],ls[0]) #將大頂堆堆頂數放到最後 heapadjust(ls,0,i-1) #調整剩餘數組成的堆 i-=1 return ls ######### x=input("請輸入待排序數列：n") y=x.split() arr=[] for i in y: arr.append(int(i)) arr=HeapSort(arr) #print(arr) print("數列按序排列如下：") for i in arr: print(i,end=' ') 5.快速排序
快速排序基於選擇劃分，是簡單選擇排序的優化。
每次劃分將數據選到基準值兩邊，循環對兩邊的數據進行劃分，類似於二分法。
演算法的整體性能取決於劃分的平均程度，即基準值的選擇，此處衍生出快速排序的許多優化方案，甚至可以劃分為多塊。
基準值若能把數據分為平均的兩塊，劃分次數O(logn)，每次劃分遍歷比較一遍O(n)，時間複雜度O(nlogn)。
額外空間開銷出在暫存基準值，O(logn)次劃分需要O(logn)個，空間複雜度O(logn)
def QuickSort(ls): def partition(arr,left,right): key=left #劃分參考數索引,默認為第一個數，可優化 while left<right: while left<right and arr[right]>=arr[key]: right-=1 while left<right and arr[left]<=arr[key]: left+=1 (arr[left],arr[right])=(arr[right],arr[left]) (arr[left],arr[key])=(arr[key],arr[left]) return left def quicksort(arr,left,right): #遞歸調用 if left>=right: return mid=partition(arr,left,right) quicksort(arr,left,mid-1) quicksort(arr,mid+1,right) #主函數 n=len(ls) if n<=1: return ls quicksort(ls,0,n-1) return ls x=input("請輸入待排序數列：n") y=x.split() arr=[] for i in y: arr.append(int(i)) arr=QuickSort(arr) #print(arr) print("數列按序排列如下：") for i in arr: print(i,end=' ') 6.希爾排序
希爾排序是插入排序的高效實現，對簡單插入排序減少移動次數優化而來。
簡單插入排序每次插入都要移動大量數據，前後插入時的許多移動都是重複操作，若一步到位移動效率會高很多。
若序列基本有序，簡單插入排序不必做很多移動操作，效率很高。
希爾排序將序列按固定間隔劃分為多個子序列，在子序列中簡單插入排序，先做遠距離移動使序列基本有序；逐漸縮小間隔重複操作，最後間隔為1時即簡單插入排序。
希爾排序對序列劃分O(n)次，每次簡單插入排序O(logn)，時間複雜度O(nlogn)
額外空間開銷出在插入過程數據移動需要的一個暫存，空間複雜度O(1)
def ShellSort(ls): def shellinsert(arr,d): n=len(arr) for i in range(d,n): j=i-d temp=arr[i] #記錄要出入的數 while(j>=0 and arr[j]>temp): #從後向前，找打比其小的數的位置 arr[j+d]=arr[j] #向後挪動 j-=d if j!=i-d: arr[j+d]=temp n=len(ls) if n<=1: return ls d=n//2 while d>=1: shellinsert(ls,d) d=d//2 return ls x=input("請輸入待排序數列：n") y=x.split() arr=[] for i in y: arr.append(int(i)) arr=ShellSort(arr) #print(arr) print("數列按序排列如下：") for i in arr: print(i,end=' ') 7.歸併排序
歸併排序運用分治遞歸思想：將大問題分為較小的子問題，分而治之；遞歸調用同樣的方法解決子問題。最終將序列的排序問題分治為一個數的排序問題，關鍵在於如何將子問題答案合併為問題答案。
兩個有序序列合併為一個有序序列，藉助一個暫存數組（列表），兩個序列元素依次比較填入暫存列表，形成一個有序序列。
歸併排序劃分子問題採用二分法，共需O(logn)次劃分，當然需要相當次合併；每次合併遍歷比較O(n)。時間複雜度O(nlogn)。
額外空間開銷出在合併過程中的一個暫存數組，空間複雜度O(n)。
def MergeSort(ls): #合併左右子序列函數 def merge(arr,left,mid,right): temp=[] #中間數組 i=left #左段子序列起始 j=mid+1 #右段子序列起始 while i<=mid and j<=right: if arr[i]<=arr[j]: temp.append(arr[i]) i+=1 else: temp.append(arr[j]) j+=1 while i<=mid: temp.append(arr[i]) i+=1 while j<=right: temp.append(arr[j]) j+=1 for i in range(left,right+1): # !注意這裡，不能直接arr=temp,他倆大小都不一定一樣 arr[i]=temp[i-left] #遞歸調用歸併排序 def mSort(arr,left,right): if left>=right: return mid=(left+right)//2 mSort(arr,left,mid) mSort(arr,mid+1,right) merge(arr,left,mid,right) n=len(ls) if n<=1: return ls mSort(ls,0,n-1) return ls x=input("請輸入待排序數列：n") y=x.split() arr=[] for i in y: arr.append(int(i)) arr=MergeSort(arr) #print(arr) print("數列按序排列如下：") for i in arr: print(i,end=' ') 8.計數排序
計數排序用待排序的數值作為計數數組（列表）的下標，統計每個數值的個數，然後依次輸出即可。
計數數組的大小取決於待排數據取值範圍，所以對數據有一定要求，否則空間開銷無法承受。
計數排序只需遍歷一次數據，在計數數組中記錄，輸出計數數組中有記錄的下標，時間複雜度為O(n+k)。
額外空間開銷即指計數數組，實際上按數據值分為k類（大小取決於數據取值），空間複雜度O(k)。
def CountSort(ls): n=len(ls) num=max(ls) count=[0]*(num+1) for i in range(0,n): count[ls[i]]+=1 arr=[] for i in range(0,num+1): for j in range(0,count[i]): arr.append(i) return arr x=input("請輸入待排序數列：n") y=x.split() arr=[] for i in y: arr.append(int(i)) arr=CountSort(arr) #print(arr) print("數列按序排列如下：") for i in arr: print(i,end=' ') 9.桶排序
桶排序實際上是計數排序的推廣，但實現上要複雜許多。
桶排序先用一定的函數關係將數據劃分到不同有序的區域（桶）內，然後子數據分別在桶內排序，之後順次輸出。
當每一個不同數據分配一個桶時，也就相當於計數排序。
假設n個數據，劃分為k個桶，桶內採用快速排序，時間複雜度為O(n)+O(k * n/k*log(n/k))=O(n)+O(n*(log(n)-log(k))),
顯然，k越大，時間複雜度越接近O(n)，當然空間複雜度O(n+k)會越大，這是空間與時間的平衡。
def BucketSort(ls): ##############桶內使用快速排序 def QuickSort(ls): def partition(arr,left,right): key=left #劃分參考數索引,默認為第一個數，可優化 while left<right: while left<right and arr[right]>=arr[key]: right-=1 while left<right and arr[left]<=arr[key]: left+=1 (arr[left],arr[right])=(arr[right],arr[left]) (arr[left],arr[key])=(arr[key],arr[left]) return left def quicksort(arr,left,right): #遞歸調用 if left>=right: return mid=partition(arr,left,right) quicksort(arr,left,mid-1) quicksort(arr,mid+1,right) #主函數 n=len(ls) if n<=1: return ls quicksort(ls,0,n-1) return ls ###################### n=len(ls) big=max(ls) num=big//10+1 bucket=[] buckets=[[] for i in range(0,num)] for i in ls: buckets[i//10].append(i) #劃分桶 for i in buckets: #桶內排序 bucket=QuickSort(i) arr=[] for i in buckets: if isinstance(i, list): for j in i: arr.append(j) else: arr.append(i) for i in range(0,n): ls[i]=arr[i] return ls x=input("請輸入待排序數列：n") y=x.split() arr=[] for i in y: arr.append(int(i)) arr=BucketSort(arr) #print(arr) print("數列按序排列如下：") for i in arr: print(i,end=' ') 10.基數排序
基數排序進行多輪按位比較排序，輪次取決於最大數據值的位數。
先按照個位比較排序，然後十位百位以此類推，優先順序由低到高，這樣後面的移動就不會影響前面的。
基數排序按位比較排序實質上也是一種劃分，一種另類的『桶』罷了。比如，第一輪按各個位比較，按個位大小排序分別裝入10個『桶』中，『桶』中個位相同的數據視作相等，桶是有序的，按序輸出，後面輪次接力完成排序。
基數排序『桶』內數據在劃分桶時便已排序O(n)，k個桶，時間複雜度為O(n*k)。
額外空間開銷出在數據劃分入桶過程，桶大小O(n+k)，空間複雜度O(n+k)。
import math def RadixSort(ls): def getbit(x,i): #返回x的第i位（從右向左，個位為0）數值 y=x//pow(10,i) z=y%10 return z def CountSort(ls): n=len(ls) num=max(ls) count=[0]*(num+1) for i in range(0,n): count[ls[i]]+=1 arr=[] for i in range(0,num+1): for j in range(0,count[i]): arr.append(i) return arr Max=max(ls) for k in range(0,int(math.log10(Max))+1): #對k位數排k次,每次按某一位來排 arr=[[] for i in range(0,10)] for i in ls: #將ls（待排數列）中每個數按某一位分類（0-9共10類）存到arr[][]二維數組（列表）中 arr[getbit(i,k)].append(i) for i in range(0,10): #對arr[]中每一類（一個列表） 按計數排序排好 if len(arr[i])>0: arr[i]=CountSort(arr[i]) j=9 n=len(ls) for i in range(0,n): #順序輸出arr[][]中數到ls中，即按第k位排好 while len(arr[j])==0: j-=1 else: ls[n-1-i]=arr[j].pop() return ls x=input("請輸入待排序數列：n") y=x.split() arr=[] for i in y: arr.append(int(i)) arr=RadixSort(arr) #print(arr) print("數列按序排列如下：") for i in arr: print(i,end=' ') 11.#程式碼說明
1.十個排序演算法都用函數封裝，函數輸入整數列表，返回整數列表。
2.測試時輸入以空格間隔的整數數列，split處理input採集的字元串，再經數據類型轉換後變為整數列表後調用函數；
輸出時採用循環逐個輸出。
3.三個線性排序演算法中調用前面其他演算法時直接複製過去，可能造成程式碼冗餘
4.十個演算法程式碼均經過簡單數據測試，未發現問題。
三、感悟總結
1.存在即有理。十種排序演算法在時間、空間複雜度，實現難度，穩定性等指標上存在較大差異，但並沒有最好最壞之說，適合的才是最好的。
2.三種O(n^2)平均時間複雜度的排序演算法在空間複雜度、穩定性方面表現較好，甚至在特定情況下即便考慮時間複雜度也是最佳選擇。
3.堆排序初始建堆過程較複雜，僅建堆時間複雜度就達到O(nlogn)，但之後的排序開銷穩定且較小，所以適合大量數據排序。
4.希爾排序性能看似很好，但實際上他的整體性能受步長選取影響較大，插入排序本質也使他受數據影響較大。
5.歸併排序在平均和最壞情況下時間複雜度都表現良好O(nlogn)，但昂貴的空間開銷大O(n)。
6.快速排序大名鼎鼎，又有個好名字，但最壞情況下時間複雜度直逼O(n^2)，遠不如堆排序和歸併排序。
7.基於比較排序的演算法（如前七種）時間複雜度O(nlogn)已是下限。
8.三種線性時間複雜度排序演算法雖然在速度上有決定性的優勢，但也付出了沉重的空間代價，有時數據的特點讓這種空間代價變得無法承受。所以他們的應用對數據本身有著特定的要求。
9.關於穩定性，希爾排序、快速排序和堆排序這三種排序演算法無法保障。三種演算法因為劃分（子序列、大小端、左右孩子）後各自處理無法保證等值數據的原次序。
10.小編水平有限，難免有錯誤，大家相互交流。
11.C++版
2018.4.8
參考文獻： 面試中的排序演算法總結 Pickle http://www.cnblogs.com/wxisme/ 十大經典排序演算法總結 秦至 https://www.cnblogs.com/jztan/p/5878630.html
