信息獲取后通常需要進行處理，處理后的信息其目的是便于人們的應用。信息處理方法有多種，通常由數據的排序，查找，插入，刪除等操作。本章介紹幾種簡單的數據排序算法和高效的排序算法.

本章主要涉及到的知識點有：

簡單排序算法： 學會選擇排序、冒泡排序、桶排序、插入排序的原理以及代碼編寫
高效排序算法： 理解希爾排序，基數排序，快速排序和歸并排序的原理

1. 簡單排序算法

簡單排序算法包括選擇排序、冒泡排序、桶排序和插入排序，本節重點介紹以上四種簡單排序算法。

1.1 選擇排序

基本思想：

每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在待排序的數列的最前，知道全部待排序的數據元素排完。

排序過程：

例如:

初始：[5 4 6 8 7 1 2 3] 第一趟排序后 1 [4 6 8 7 5 2 3] 第二趟排序后 1 2 [6 8 7 5 4 3] 第三趟排序后 1 2 3 [8 7 5 4 6] 第四趟排序后 1 2 3 4 [7 5 8 6] 第五趟排序后 1 2 3 4 5 [7 8 6] 第六趟排序后 1 2 3 4 5 6 [8 7] 第七趟排序后 1 2 3 4 5 6 7 [8] 最后排序結果 1 2 3 4 5 6 7 8

對應代碼：

a = [5, 4, 6, 8, 7, 1, 2, 3] n = len(a) for i in range(n - 1):k = ifor j in range(i + 1, n):if a[j] < a[k]:k = jif k != i:temp = a[i]a[i] = a[k]a[k] = temp print(a)

1.2 冒泡排序

基本思想：
所謂冒泡排序就是依次將兩個相鄰的數進行比較，大的在前面，小的在后面。即先比較第一個數和第二個數，大數在前，小數在后，然后比較第2個數和第3個數，直到比較最后兩個數。第一趟結束后，最小數的數一定在最后。第二趟在第一趟的基礎上重復上述操作。
由于排序過程中總是大數在前，小數在后， 相當于氣泡上升，所以叫冒泡排序。
大數在前，小數在后排序后得到的是降序，小數在前，大數在后排序后得到的是升序結果。
排序過程(降序)

初始數據：4 5 6 1 2 3 第一趟： 比較前兩個數，4比5小，交換位置 5 4 6 1 2 3 比較第2第3個數，4比6小，交換位置 5 6 4 1 2 3 比較第3第4個數，5比1大，位置不變 5 6 4 1 2 3 比較第4第5個數，1比2小，交換位置 5 6 4 2 1 3 比較最后兩個數 ，1比3小，交換位置 5 6 4 2 3 1 第一趟結束 第二趟重復第一趟過程得到 6 5 4 3 2 1 排序完畢。

可以發現，第二趟結束已經排好序了，實際上對于一組數據排n-1趟一定能排好序。因為第i趟都會有前i小的數排序好，n-1趟前n-1小的數已排好序，最后一個數自然也排好序了。

對應代碼：

a = [4, 5, 6, 1, 2, 3] n = len(a) for i in range(n - 1):for j in range(n - i - 1):if a[j] < a[j + 1]:temp = a[j]a[j] = a[j + 1]a[j + 1] = temp print(a)

1.3 桶排序

基本思想：
桶排序的思想是若待排序的記錄的關鍵字在一個明顯有限范圍內（整型）時，可設計有限個有序桶，每個桶只能裝與之對應的值，順序輸出各桶的值，將得到有序的序列。
例如,輸入n個0~9之間的整數，由小到大排序輸出
我們可以準備10個桶依次編號為0~9。輸入的數0入0號桶，1入1號桶，依次類推。
如圖所示：

先準備好10個空桶并編號。
依次輸入8個整數：2，5，6，8，5，2，9，6
每輸入一次就將數放入對應的桶。
輸入完畢后桶內數據如圖所示：

桶排序過程

2號桶內有兩個數字2，5號桶內有兩個數字5，6號桶內有兩個數字6，8號桶內有一個數字8，9號桶內有一個數字9. 然后按桶編號從小到大的順序將桶內數字輸出，得到 2，2，5，5，6，6，8，9 此時就排好續了。

實現代碼：

b={0:0,1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0} n=eval(input("輸入整數n")) for i in range(n):x=eval(input("輸入0~9之間的整數"))b[x]+=1 for key in range(10):while b[key]>0:print(key,end=' ')b[key]-=1

1.4插入排序

基本思想：
插入排序是一種簡單的排序方法，其算法的基本思想是：
假設待排序的數據存放在數組a[1…n]中，增加一個哨兵節點x.
a[1]自成一個有序區，無序區為a[2…n]；
從i=2起直至i=n為止，將a[i]放在恰當的位置，使a[1…i]數據序列有序；
x=a[i]
將x與前i-1個數比較，j=i-1;while(x<a[j]) j-=1
將a數組的元素從j位置開始向后移動：for k in range(j,i+1,-1): a[k]=a[k-1]
a[j]=x
生成包含n個數據的有序區。
例如 a=[3 2 4 1 6 5 2 7]

排序過程：

第0步：[3] 2 4 1 6 5 2 7 第1步：[2 3] 4 1 6 5 2 7 第2步：[2 3 4] 1 6 5 2 7 第3步：[1 2 3 4] 6 5 2 7 第4步：[1 2 3 4 6] 5 2 7 第5步：[1 2 3 4 5 6] 2 7 第6步：[1 2 2 3 4 5 6] 7 第7步：[1 2 2 3 4 5 6 7]

插入排序的時間復雜度為O(n*n)。插入排序適用于數據已經排好序，插入一個新數據的情況

實現代碼：

a = [0, 3, 2, 4, 1, 6, 5, 2, 7] n = len(a) for i in range(2, n):x = a[i]j = i - 1while x < a[j]:a[j + 1] = a[j]j -= 1a[j + 1] = x print(a)

**注意：**此數組有效數據從i=1開始，a[0]=0,是為了運算方便補上的。

2. 高效排序算法

第一節介紹了簡單的排序算法，但在實際應用中，簡單的排序算法很難達到效率的要求，所以本節介紹了兩種高效的排序算法，使排序時間復雜度大大減少。

2.1 快速排序

基本思想：
快速排序是一種采用分治法解決問題的一個典型應用,也是冒泡排序的一種改進。它的基本思想是，通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分均比另一部分小，則可分別對這兩部分繼續進行排序，已達到整個序列有序。排序的時間復雜度為O(nlogn),相比于簡單排序算法，運算效率大大提高。

算法步驟：
① 從序列中取出一個數作為中軸數
② 將比這個數大的數放到它的右邊，小于或等于他的數放到它的左邊。
③ 再對左右區間重復第二步，知道各區間只有一個數
例如：對以下10個數進行快速排序：
6 1 2 7 9 3 4 5 10 8
以第一個數為基準數
在初始狀態下，數字6在序列的第1位。我們的目標是將6挪到序列中間的某個位置，假設這個位置是k。現在就需要尋找這個k，并且以第k位為分界點，左邊的數都≤6，右邊的數都≥6。那么如何找到這個位置k呢？
我們要知道，快速排序其實是冒泡排序的一種改進，冒泡排序每次對相鄰的兩個數進行比較，這顯然是一種比較浪費時間的。
而快速排序是分別從兩端開始”探測”的，先從右往左找一個小于6的數，再從左往右找一個大于6的數，然后交換他們。這里可以用兩個變量i和j，分別指向序列最左邊和最右邊。我們為這兩個變量起個好聽的名字“哨兵i”和“哨兵j”。剛開始的時候讓哨兵i指向序列的最左邊，指向數字6。讓哨兵j指向序列的最右邊，指向數字8。

首先哨兵j開始出動。因為此處設置的基準數是最左邊的數，所以需要讓哨兵j先出動，這一點非常重要。哨兵j一步一步地向左挪動，直到找到一個小于6的數停下來。接下來哨兵i再一步一步向右挪動），直到找到一個數大于6的數停下來。最后哨兵j停在了數字5面前，哨兵 i停在了數字7面前

現在交換哨兵i和哨兵j所指向元素的值。交換之后的序列如下。

到此，第一次交換結束。接下來開始哨兵j繼續向左挪動（再友情提醒，每次必須是哨兵j先出發）。他發現了4<6，停下來。哨兵i也繼續向右挪動的，他發現了9>6，停下來。此時再次進行交換，交換之后的序列如下

第二次交換結束。哨兵j繼續向左挪動，他發現了3<6,又停下來。哨兵i繼續向右移動，此時哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。說明此時“探測”結束。我們將基準數6和3進行交換。交換之后的序列如下。

到此第一輪“探測”真正結束。現在基準數6已經歸為，此時以基準數6為分界點，6左邊的數都小于等于6，6右邊的數都大于等于6。
現在我們將第一輪“探測”結束后的序列，以6為分界點拆分成兩個序列，左邊的序列是“3 1 2 5 4”，右邊的序列是“9 7 10 8”。接下來還需要分別處理這兩個序列，因為6左邊和右邊的序列目前都還是混亂的。不過不要緊 ，我們已經掌握了方法，接下來只要模擬剛才的方法分別處理6左邊和右邊的序列即可。
實際上快速排序的每一輪處理其實就是將這一輪的基準數歸為，直到所有的數都歸為為止，排序就結束了。
實現代碼：

def qsort(l,r):if(l>r):return Nonetmp=a[l] i=lj=rwhile i!=j:while(a[j]>=tmp and j>i):j-=1while(a[i]<=tmp and j>i):i+=1if(j>i):t=a[i]a[i]=a[j]a[j]=ta[l]=a[i]a[i]=tmpqsort(l,i-1)qsort(i+1,r)

2.2歸并排序

基本思想：
歸并排序是由遞歸實現的，主要是分而治之的思想，也就是通過將問題分解成多個容易求解的局部性小問題來解開原本的問題的技巧。
另外，歸并排序在合并兩個已排序數組時，如果遇到了相同的元素，只要保證前半部分數組優先于后半部分數組， 相同元素的順序就不會顛倒。所以歸并排序屬于穩定的排序算法。

每次分別排左半邊和右半邊，不斷遞歸調用自己，直到只有一個元素遞歸結束，開始回溯，調用merge函數，合并兩個有序序列，再合并的時候每次給末尾追上一個最大int這樣就不怕最后一位的數字不會被排序。
排序過程：

代碼實現：

def MergeSort(lists):if len(lists) <= 1:return listsnum = int( len(lists) / 2 )left = MergeSort(lists[:num])right = MergeSort(lists[num:])return Merge(left, right) def Merge(left,right):r, l=0, 0result=[]while l<len(left) and r<len(right):if left[l] <= right[r]:result.append(left[l])l += 1else:result.append(right[r])r += 1result += list(left[l:])result += list(right[r:])return result print MergeSort([1, 2, 3, 4, 5, 6, 7, 90, 21, 23, 45])

2.3基數排序：

基本思想：
基數排序（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達到排序的作用。參考桶排序。
基數排序算法不依靠直接比較元素排序。而是采用分配式排序，單獨處理元素的每一位。從最高位向最低位處理稱為：最高位優先（MSD）反之稱為：最低位優先(LSD)。
下面以最低位優先為例：
（1）準備10個容器，編號0-9，對應數字0-9。 容器是有序的(按添加順序)
（2）然后按待排序元素的某一位上的數字(比如:個位/十位/百位)將其存放到對應容器中（數字相同,如: 個位是數字1時, 就把這個元素放在1號桶），所有元素這樣處理完后,再從0號容器開始依次到9號容器, 將其中的元素順序取出放回原數組，然后再從下一位開始…(比如個位處理完后, 再處理十位/百位…最高位)
基數排序，可以稱之為，進階版的桶排序。
排序過程：
這個圖片的來源

代碼實現：

import mathdef sort(a, radix=10):"""a為整數列表， radix為基數"""K = int(math.ceil(math.log(max(a), radix))) # 用K位數可表示任意整數bucket = [[] for i in range(radix)] # 不能用 [[]]*radixfor i in range(1, K+1): # K次循環for val in a:bucket[val%(radix**i)/(radix**(i-1))].append(val) # 析取整數第K位數字 （從低到高）del a[:]for each in bucket:a.extend(each) # 桶合并bucket = [[] for i in range(radix)]

2.4 希爾排序

基本思想：
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。希爾排序是非穩定排序算法。同時也突破了之前內排序算法復雜度為O(n2)的限制。
希爾排序是基于插入排序的以下兩點性質而提出改進方法的：

插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率
插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位
該方法的基本思想是：先將整個待排元素序列分割成若干個子序列（由相隔某個“增量”的元素組成的）分別進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的，因此希爾排序在時間效率上比前兩種方法有較大提高。

其中增量序列的選擇是非常關鍵的，但通常我們取步長為n/2（數組長度的一般）然后一直取半直到1。

算法過程：

圖片是之前看到的，如果有人知道出處，希望可以在評論區中指出，感謝。
實現代碼：

a = [56,52,-96,-53,23,-789,520] #測試案例 b = len(a) #列表長度 gap = b // 2 #初始步長設置為總長度的一半 while gap >= 1:for i in range (b):j = iwhile j>=gap and a[j-gap] > a[j]: #在每一組里面進行直接插入排序a[j],a[j-gap] = a[j-gap],a[j]j-= gapgap=gap//2 #更新步長 print(a)

總結

以上是生活随笔為你收集整理的写代码？程序猿？你不能不懂的八大排序算法的Python实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。