數據的排序是在解決實際問題時經常用到的步驟，也是數據結構的考點之一，下麵介紹10種經典的排序方法。 首先，排序方法可以大體分為插入排序、選擇排序、交換排序、歸併排序和桶排序四大類，其中，插入排序又分為直接插入排序、二分插入排序和希爾排序，選擇排序分為直接選擇排序和堆排序，交換排序分為冒泡排序和快速排 ...
數據的排序是在解決實際問題時經常用到的步驟，也是數據結構的考點之一，下麵介紹10種經典的排序方法。
首先，排序方法可以大體分為插入排序、選擇排序、交換排序、歸併排序和桶排序四大類，其中，插入排序又分為直接插入排序、二分插入排序和希爾排序，選擇排序分為直接選擇排序和堆排序，交換排序分為冒泡排序和快速排序，桶排序以基數排序和計數排序為代表。這些排序方法的時間複雜度和空間複雜度分別如下表所示。
排序方法的穩定性是這樣定義的：在待排序序列中如果存在a[i]和a[j]，a[i]=a[j]&&i<j，如果排序後仍然符合a[i]=a[j]&&i<j，即它們的前後相對位置關係沒有改變，該排序演算法就是穩定的。
(1)直接插入排序
插入排序的基本思想是將數據插入合適的位置。如下所示序列[6,8,1,4,3,9,5,0]，以升序排列為例。
a.6<8，符合升序
b. 8>1，不符合要求，改變1的位置。首先比較1和8，1更小，交換1和8的位置，序列成為[6,1,8,4,3,9,5,0]，然後繼續比較1和6，1更小，交換1和6的位置，序列成為[1,6,8,4,3,9,5,0],註意此時前三個值已經符合升序的要求。
c. 8>4，不符合要求，改變4的位置，按照上面的方法，依次與前面的值比較，分別與8和6交換位置，當比較到1時，1<4，不用交換位置。此時序列成為[1,4,6,8,3,9,5,0]
d.重覆上滿的操作，直到整個序列遍歷完成。
因此，插入排序實際上是保證遍歷過的序列是有序的，然後將下一個訪問到的值，通過比較和交換位置，插入到這個有序序列中，當所有的值都被訪問過後，整個序列就是有序的了。所以這種方法是穩定，空間複雜度為O(1)，最好的時間複雜度為O(n)，代碼如下
def insert_sort(arr):
for i in range(len(arr)-1):
if arr[i+1]<arr[i]:#如果arr[i+1]較小，將其插入到前面升序序列中
for j in range(i+1,0,-1):
if arr[j]<arr[j-1]:#依次將大於arr[i+1]的值向後移動，直到找到不大於arr[i+1]的值
arr[j-1],arr[j]=arr[j],arr[j-1]
else:
break
return arr(2) 二分插入排序
二分插入排序的思想與直接插入排序相同，只是在將數據插入有序序列時，採用了二分查找的思想，即先於中間位置的值進行比較，以縮短查找的時間。代碼如下
def BinaryInsert_sort(arr):
for i in range(1,len(arr)):
if arr[i]<arr[i-1]:
left,right=0,i-1
while left<right:#最終right位置的值是有序序列中第一個不大於arr[i]的值
mid=left+(right-left)//2
if arr[i]<arr[mid]:#
right=mid
else:
left=mid+1
for j in range(i,right,-1):
arr[j],arr[j-1]=arr[j-1],arr[j]
return arr(3) 希爾排序
希爾排序建立在直接插入排序的基礎上，假設序列長度為n，先取一個小於n的整數d1，序列中所有距離為d1的數據為一組，如下圖中，以2為i增量，1，4，5為一組，8，3，0為一組，1，9為1組，然後在組內進行直接插入排序，然後取整數d2,d2<d1，重覆上面的步驟，直到增量減少為1。一般的初次取序列的一半為增量，以後每次減半。這樣通過相隔增量的數，使得數移動時能跨過多個元素，加快速度。代碼如下
def Hill_sort(arr):
d=len(arr)//2
while(d>=1):
for i in range(len(arr)//d):
for j in range(i,len(arr)-d,d):
if arr[j+d]<arr[j]:
for k in range(j+d,i,-d):
if arr[k]<arr[k-d]:
arr[k],arr[k-d]=arr[k-d],arr[k]
d=d//2
return arr因為希爾排序跨距離訪問元素，因此不穩定。空間複雜度為O(1)，最好的時間複雜度為O(n)。
(4) 直接選擇排序
選擇排序的思想是每次從無序的序列中選擇最大或最小的值，並與第一個位置的值交換。如序列l，如果是升序排列，第一次找出l的最小值與l[0]交換，第二次找出l[1:]最小的值，與l[2]交換，以此類推，代碼如下。
def select_sort(arr):
for i in range(len(arr)-1):
minnum=arr[i]
m=i
for j in range(i+1,len(arr)):
if arr[j]<minnum:
minnum=arr[j]
m=j
arr[i],arr[m]=arr[m],arr[i]
return arr直接選擇排序是穩定的，空間複雜度為O(1)，時間複雜度恆定為O(n2),因為原序列是否有序不會影響選擇排序的步驟。
(5) 堆排序
堆排序用到了大頂堆和小頂堆的概念。大頂堆是父節點最大的二叉樹，即arr[i]>=arr[2*i+1]&&arr[i]>=arr[2*i-1]；小頂堆是父節點的值最小的二叉樹，即arr[i]<=arr[2*i+1]&&arr[i]<=arr[2*i-1]。
以升序排序為例，首先建立初始最大堆，以某個節點為入口，向下調整其子節點，使其符合大頂堆的特點。建立初始大頂堆的過程會重覆調整一些節點，是因為父節點和子節點的交換，會影響以子節點為根節點的子樹，如圖中，[9,1,7]子樹原符合要求，6和9交換後，[6,1,7]不符合要求，就要再次調整該子樹。
初始大頂堆建立之後，將根節點的值置換到序列末尾，然後重新調整前面的序列，這時只從根節點向下調整即可，因為初始大頂堆已經形成，如圖中，即便交換了0和4的位置，父節點8也仍舊是最大的。
def heap_sort(arr):
def adjust(arr,node,maxid):
root=node
while True:
child=2*root+1
if child>maxid:
return
child=child+1 if arr[child+1]>arr[child] and child+1<maxid else child#child是兩個孩子中值較大的一個
if arr[root]<arr[child]:
arr[root],arr[child]=arr[child],arr[root]
root=child
else:
return
first=len(arr)//2-1
for node in range(first,-1,-1):
adjust(arr,node,len(arr)-1)
for maxid in range(len(arr)-1,0,-1):
arr[0],arr[maxid]=arr[maxid],arr[0]
adjust(arr,0,maxid-1)堆排序不穩定，空間複雜度為O(1)，但時間複雜度恆定為O(nlogn)。
(6) 冒泡排序
交換排序即通過交換元素位置，使序列有序。冒泡排序是最簡單的交換排序，每次將最大值/最小值依次交換到序列末尾。冒泡排序是穩定的，空間複雜度為O(1)，時間複雜度最好為O(n)。
def bubble_sort(arr):
for i in range(len(arr)-1): # 這個迴圈負責設置冒泡排序進行的次數
for j in range(len(arr)-i-1): # ｊ為列表下標
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr(7) 快速排序
快速排序可以說是使用頻率和考察頻率最高的排序方法。快速排序的基本思想是以序列中的某個值為標準，大於該值的被放在右邊，小於該值放在左邊，然後再繼續對該值左右兩兩邊的序列重覆此步驟，思想很簡單，代碼如下。
import random
def quick_sort(arr,start,end):
if end-start<=0: return
index=random.randrange(start,end+1)
print(index)
arr[end],arr[index]=arr[index],arr[end]
small=start-1
for i in range(start,end):
if arr[i]<arr[end]:
small+=1
if small!=i:#如果small與i不相同，說明有大於arr[end]的值出現，small記錄的是分界線的位置
arr[i],arr[small]=arr[small],arr[i]
small+=1
arr[end],arr[small]=arr[small],arr[end]
print(arr)
quick_sort(arr,start,small-1)
quick_sort(arr,small+1,end)對於python，有一種更加簡單明瞭的實現方式
def qsort(arr):
if len(arr) <= 1: return arr
return qsort([lt for lt in arr[1:] if lt < arr[0]]) + arr[0:1]+ qsort([ge for ge in arr[1:] if ge >= arr[0]]) 快速排序並沒有創建新的數組，但由於實現過程中利用了函數的遞歸調用，需要堆棧空間，所以空間複雜度為O(nlogn)，時間複雜度最好為O(nlogn)。
(8) 歸併排序
歸併排序採用分而治之的思想，將序列分為多個小的序列，對小的序列排序之後，將小序列合併為大的序列，過程如下圖所示。
代碼如下
def merge_sort(arr,start,end):
def merging(l1,l2,lnew=[]):
i,j=0,0
while(i<len(l1) and j<len(l2)):
if l1[i]<l2[j]:
lnew.append(l1[i])
i+=1
else:
lnew.append(l2[j])
j+=1
if i<len(l1):
for num in l1[i:]:
lnew.append(num)
if j<len(l2):
for num in l2[j:]:
lnew.append(num)
return lnew
if end-start>1:#分
mid=start+(end-start)//2
merge_sort(arr,start,mid)
merge_sort(arr,mid,end)
arr[start:end]=merging(arr[start:mid],arr[mid:end],[])#治
return arr歸併排序需要新的數組存放合併後的序列，空間複雜度為O(n)，時間複雜度恆定為O(nlogn)，是穩定的。
(9) 計數排序
桶排序實際上是一類排序方法的總稱。桶排序的思想是將所有數據按照一定的映射關係放到一定數量的桶中，將每個桶里的數據排序，再將所有的桶組合起來，所以不同的映射關係下可以產生不同的桶排序，並且桶排序是基於其他排序演算法的，桶內數據的排序需要使用其他排序演算法。計數排序和基數排序是桶排序的兩種代表。
計數排序是採用的映射關係是最直接的f[i]=i，即一個桶里的數字都是相同的，因此沒有桶內排序的步驟。具體過程為，
1.找出待排序的數組中最大和最小的元素
2.統計數組中每個值為i的元素出現的次數，存入數組C的第i項，這時映射的過程
3.對所有的計數累加，C[i]的含義即是在數組中小於i的元素個數，即為排序後i應放的位置
4.反向填充目標數組：將每個元素i放在新數組的第C(i)項，每放一個 元素就將C(i)減去1。
代碼如下
def count_sort(arr):
crr=[]
m=max(arr)+1
ll=len(arr)
ans=[]
for i in range(ll):#用於存放排序後的數組
ans.append(None)
for i in range(m):#桶
crr.append(0)
for num in arr:#映射的過程，計數
crr[num]+=1
for i in range(1,m):#計數累加
crr[i]=crr[i-1]+crr[i]
for num in arr:#反向填充數組
ans[crr[num]-1]=num
crr[num]-=1
return ans(10) 基數排序
基數排序的映射方法是按照數據特定位上數字放入不同的桶中， 將序列中的數組按照個位放到不同的桶中，然後按照個位0~9的順序依次取出，再按照十位放到不同的桶中，…….直到達到數據的最高位，最後一次將數據取出時，排序完成，例如：
實現代碼
def radix_sort(arr):
def compare(basis,arr):#以數組basis為依據的插入排序
for i in range(1,len(basis)):
if basis[i]<basis[i-1]:
for j in range(i,0,-1):
if basis[j-1]>basis[j]:
basis[j],basis[j-1]=basis[j-1],basis[j]
arr[j],arr[j-1]=arr[j-1],arr[j]
else:
break
upnum=max(arr)
tmp=1
while(tmp<upnum):
basis=[num//tmp%10 for num in arr]
compare(basis,arr)
tmp*=10
return arr註意基數排序在桶內排序時，一定要採用穩定的排序方法，這樣才可以利用之前的排序結果，否則之前的排序是無意義的。
