幾種基礎排序演算法的python實現
- 2019 年 10 月 6 日
- 筆記
最近利用晚上閑下來的時間整理了一些基礎的排序演算法，這些排序演算法一般的就是在學習數據結構的時候都是要求掌握的，作為一個開發者來說，會排序那是最基礎的技能，也是最重要的技能，下面我們就一起來看看吧！
插入排序
插入排序思想：每一趟將一個待排序元素，按其排序碼大小插入到前面已經排好序的一組元素的適當位置上，直到所有待排序元素元素全部插入為止
思路：
假定前i個構成的子序列是處於已排序的情況下進行排序的，然後將第i個元素與前i個構成的子序列逆序進行比較，如果是要升序排序，則比較第i個元素是否比j=i-1(i-1需要>=0)的元素大，如果是則第i個元素的位置（即j+1的位置上）保持不動，反之則將j=i-1的元素放置到i的位置，再進行第i個元素與j=i-2(i-2需要>=0)的,依次進行，如果第i個元素剛好比j=i-3大，則將第i個元素插入到j=i-2（即j+1的位置）上。
程式碼：
def insertion_sort(a): l = len(a) j = 0 for i in range(1, l): temp = a[i] for j in range(i - 1, -1, -1): if temp < a[j]: # 如果第i個元素大於前i個元素中的第j個 a[j + 1] = a[j] # 則第j個元素先後移1位 else: # 如果第i個元素小於等於前i個元素中的第j個則結束循環 break a[j + 1] = temp # 將i個元素賦值給空著的位置 for i in range(0, l): print(a[i])
快速排序
思路：
任意選取一個數據（通常選用數組的第一個數）作為關鍵數據，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序。
一趟快速排序的演算法是：
1）設置兩個變數i、j，排序開始的時候：i=0，j=N-1；
2）以第一個數組元素作為關鍵數據，賦值給key，即key=A[0];
3）從j開始向前搜索，即由後開始向前搜索(j–)，找到第一個小於key的值A[j]，將A[j]和A[i]互換；
4）從i開始向後搜索，即由前開始向後搜索(i++)，找到第一個大於key的A[i]，將A[i]和A[j]互換；
5）重複第3、4步，直到i=j； (3,4步中，沒找到符合條件的值，即3中A[j]不小於key,4中A[i]不大於key的時候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進行交換的時候i， j指針位置不變。另外，i==j這一過程一定正好是i+或j-完成的時候，此時令循環結束）
程式碼，使用遞歸演算法來實現：
def quick_sort(arr, low, high): # temp = a[0] i = low j = high if i >= j: return arr temp = arr[i] while i < j: while i < j and arr[j] >= temp: j = j - 1 arr[i] = arr[j] while i < j and arr[i] <= temp: i = i + 1 arr[j] = arr[i] arr[i] = temp quick_sort(arr, low, i - 1) quick_sort(arr, j + 1, high) return arr
冒泡排序
思路：
比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。
針對所有的元素重複以上的步驟，除了最後一個。
持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。
程式碼：
def bubble_sort(arr): length = len(arr) while length > 0: for i in range(length - 1): if arr[i] > arr[i + 1]: arr[i] = arr[i] + arr[i + 1] arr[i + 1] = arr[i] - arr[i + 1] arr[i] = arr[i] - arr[i + 1] length -= 1
選擇排序
思路：
每一趟從待排序的數據元素中選出最小（最大）的元素，順序放在待排序的數列最前，直到全部待排序的數據元素全部排完。
例子： [4, 2, 3] 找出最小的：2,與第一個元素交換 [2, 4, 3] 找出最小的：3，與第二個元素交換 [2, 3, 4]
程式碼：
def selection_sort(a): for j in range(0,len(a)-1): count = j #記錄最小元素下標 #每次找出最小元素 for i in range(j,len(a)-1): if a[count] > a[i+1]: count = i+1 #python特有的交換值方法，交換最小元素和待排序元素中最前一個 a[j], a[count] = a[count], a[j] for i in range(0,len(a)): print(a[i])
堆排序
先介紹一下堆，堆是具有以下性質的完全二叉樹：每個結點的值都大於或等於其左右孩子結點的值，稱為大頂堆；或者每個結點的值都小於或等於其左右孩子結點的值，稱為小頂堆。如下圖：
思路：
將待排序序列構造成一個大頂堆，此時，整個序列的最大值就是堆頂的根節點。將其與末尾元素進行交換，此時末尾就為最大值。然後將剩餘n-1個元素重新構造成一個堆，這樣會得到n個元素的次小值。如此反覆執行，便能得到一個有序序列了
堆排序是利用堆這種數據結構而設計的一種排序演算法，堆排序是一種選擇排序，它的最壞，最好，平均時間複雜度均為O(nlogn)，它也是不穩定排序。首先簡單了解下堆結構。
在排序之前我們需要構造一個大頂堆，之後再使用堆排序
程式碼：
def adjustHead(a, i, l): temp = a[i] #取出當前元素 k = 2*i + 1 #從左子節點開始，即2*i+1 while k < l: if k+1 < l & a[k] < a[k+1]: #若果左子節點小於右子節點，k指向右子節點 k=k+1 if a[k] > temp: a[i] = a[k] i = k else: break k = 2*k + 1 #把該節點當作父節點，繼續操作 a[i] = temp #將父節點值賦值給該子節點 def heap_sort(arr): l = len(arr) for i in range(int(l/2-1), -1, -1): adjustHead(arr,i,l) # 交換堆頂和最後一個元素，並調整堆結構 for j in range(l-1, 0, -1): arr[0], arr[j] = arr[j], arr[0] #將堆頂元素和末尾元素進行交換 adjustHead(arr, 0, j) #重新對對進行調整 for k in range(0,l): print(arr[k])
基數排序
基數排序又稱為「桶子法」，從低位開始將待排序的數按照這一位的值放到相應的編號為0~9的桶中。等到低位排完得到一個子序列，再將這個序列按照次低位的大小進入相應的桶中，一直排到最高位為止，數組排序完成。
思路：
(1)遍歷序列找出最大的數(為的是確定最大的數是幾位數)；
(2)開闢一個與數組大小相同的臨時數組tmp；
(3)用一個count數組統計原數組中某一位(從低位向高位統計)相同的數據出現的次數；
(4)用一個start數組計算原數組中某一位(從最低位向最高位計算)相同數據出現的位置；
(5)將桶中數據從小到大用tmp數組收集起來；
(6)重複(3)(4)(5)直到所有位都被統計並計算過，用tmp收集起來；
(7)將tmp數組拷回到原數組中；
程式碼：
import math def radix_sort(arr): radix = 10 #基數 # k可以表示任意整數 k = int(math.ceil(math.log(max(arr),radix))) #math.log對arr中最大的數取對數，log(max(arr),10),並對其取整得到最大值的位數 bucket =[[] for i in range(radix)] for i in range(1, k+1): for value in arr: # 析取整數第k位數字（從低到高）10**2位10的二次方 bucket[int(value%(radix**i)/(radix**(i-1)))].append(value) del arr[:] for each in bucket: arr.extend(each) #桶合併 bucket = [[]for i in range(radix)]
