說明：
用Python實作十大排序演算法，僅有簡單解釋，無演算法的詳細介紹，
相關術語：
穩定排序：如果a原本在b的前面，且a==b，排序之后a仍然在b的前面，則為穩定排序，
非穩定排序：如果a原本在b的前面，且a==b，排序之后a可能不在b的前面，則為非穩定排序，
原地排序：指在排序程序中不申請多余的存盤空間，只利用原來存盤待排資料的存盤空間進行比較和交換，
非原地排序：需要利用額外的陣列來輔助排序，
排序演算法（默認從小到大進行排序）：
選擇排序、插入排序、冒泡排序、希爾排序、歸并排序、快速排序、堆排序、基數排序、桶排序、基數排序
1.選擇排序
步驟：
1.找到陣列中最小的元素
2.將它和陣列中的第一個元素交換位置
3.在剩下的元素中找到最小的元素，將它與陣列中的第二個元素交換位置
4.重復以上操作，直到將整個陣列排序
def selectSort(arr): length = len(arr) for i in range(length-1): min_index = i for j in range(i+1,length): if arr[j] < arr[min_index]: min_index = j arr[i], arr[min_index] = arr[min_index], arr[i] return arr
性質：時間復雜度：O(n2)、空間復雜度：O(1)、非穩定排序、原地排序
2.插入排序
步驟：
1.從陣列的第2個元素開始抽取
2.將它與左邊的第一個元素比較，如果左邊第一個元素比它大，則繼續與左邊第二個元素比較，直到遇到不比它大的元素，插入到該元素的右邊
3.繼續抽取第3、4、5……n個元素，重復步驟2，選擇適當的位置插入
def insertSort(arr): length = len(arr) for i in range(1,length): j = i - 1 while j >= 0 and arr[j] > arr[i]: j -= 1 t = arr.pop(i) arr.insert(j+1,t) return arr
性質：時間復雜度：O(n2)、空間復雜度：O(1)、穩定排序、原地排序
3.冒泡排序
步驟：
1.把第一個元素和第二個元素進行比較，如果第一個比第二個大，則交換他們的位置
2.比較第二個元素和第三個元素，如果第二個比第三個大，則交換位置
3.一直比較到陣列的最后一個元素，這樣一趟交換下來，最后一個元素就會是最大的數
4.除去最后一個元素，對剩余的元素重復以上操作，直到排序完成
def bubbleSort(arr): length = len(arr) for i in range(length): for j in range(length-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr
性質：時間復雜度：O(n2)、空間復雜度：O(1)、穩定排序、原地排序
4.希爾排序
步驟：
1.將較大的資料集分為若干小組，比如第一組：[0,h,2h,3h……]、第二組：[1,h+1,2h+1……]……(這里h為增量)
2.輪流對每一小組進行插入排序，使得整個陣列部分有序
3.令h=h/2，重新進行分組，輪流對每一小組進行插入排序
4.重復3操作，直到h=1,即整個陣列被分為一組
5.對這一組資料進行排序
def ShellSort(arr): length = len(arr) gap = length // 2 while gap > 0: for i in range(gap,length): insertI(arr,gap,i) gap = gap // 2 return arr def insertI(arr,gap,i): temp = arr[i] j = i - gap while j >= 0 and temp < arr[j]: arr[j+gap] = arr[j] j = j - gap arr[j+gap] = temp
性質：時間復雜度：O(nlogn)、空間復雜度：O(1)、非穩定排序、原地排序
5.歸并排序
步驟：
1.將待排序的陣列分為兩個后分別排好序，再將排好序的兩個陣列合并成一個有序陣列
2.可以將陣列一直分割，直到陣列的大小為1，此時只有一個元素，那么該陣列即為有序的
3.再將兩個大小為1的陣列合并成一個大小為2的，再把大小為2的陣列合并成一個大小為4的……直到全部合并
def mergerSort(arr): n = len(arr) if n == 1: return arr mid = n // 2 left = mergerSort(arr[:mid]) right = mergerSort(arr[mid:]) return mergeArray(left,right) #合并兩個有序陣列 def mergeArray(arr1,arr2): n1 = len(arr1) n2 = len(arr2) temp = [] i = 0 j = 0 while i <= n1-1 and j <= n2-1: if arr1[i] < arr2[j]: temp.append(arr1[i]) i += 1 else: temp.append(arr2[j]) j += 1 if i <= n1-1: temp.extend(arr1[i:]) if j <= n2-1: temp.extend(arr2[j:]) return temp
性質：時間復雜度：O(nlogn)、空間復雜度：O(n)、穩定排序、非原地排序
6.快速排序
步驟：
1.選取陣列的某個元素，稱之為主元
2.將大于等于主元的元素放到主元的右邊，將小于主元的元素放到主元的左邊
3.主元把陣列分成了兩部分，采用遞回，對左右兩部分分別采取1、2步驟，直到子陣列只有1個或0個元素
def quickSort(arr): return q_sort(arr, 0, len(arr)-1) #選取第一個元素作為主元 def q_sort(arr, left, right): if left < right: mid = Partition(arr, left, right) arr = q_sort(arr, left, mid - 1) arr = q_sort(arr, mid + 1, right) return arr def Partition(arr, left, right): pivot = arr[left] i = left + 1 j = right while i <= j: while i <= j and arr[i] < pivot: i += 1 while i <= j and arr[j] > pivot: j -= 1 if i >= j: break arr[i],arr[j] = arr[j], arr[i] arr[left] = arr[j] arr[j] = pivot return j
性質：時間復雜度：O(nlogn)、空間復雜度：O(logn)、非穩定排序、原地排序
7.堆排序
堆頂的元素是堆的最大值或最小值，這里考慮大頂堆，
步驟：
1.將堆頂元素與最后一個元素互換
2.破壞了堆的特性后，將剩余元素再次構成一個大頂堆
3.將堆頂元素與最后第二個元素互換
4.重復以上操作，直到剩余一個元素，則完成排序
def headSort(arr): #構建堆 length = len(arr) t = (length - 2) // 2 for i in range(t,-1,-1): #下標不包含-1 downHead(arr,i,length-1) #互換后下沉進行堆排序 for i in range(length-1,0,-1): arr[0], arr[i] = arr[i], arr[0] downHead(arr,0,i-1) return arr def downHead(arr,parent,length): temp = arr[parent] #左孩子 child = 2 * parent + 1 while child <= length: #定位到較大的孩子 if child + 1 <= length and arr[child+1] > arr[child]: child += 1 if temp > arr[child]: break arr[parent] = arr[child] parent = child child = 2 * parent + 1 arr[parent] = temp
性質：時間復雜度：O(nlogn)、空間復雜度：O(1)、非穩定排序、原地排序
8.計數排序
計數排序適合最大值和最小值的差值不是很大的排序
步驟：
1.找出陣列中的最大值和最小值
2.構建一個長度為(max-min+1)的連續陣列A
3.統計陣列中每個元素出現的次數，存入A中
4.再把臨時陣列A中的資料從小到大匯總起來，出現幾次就輸出幾次
def countSort(arr): min_arr = min(arr) max_arr = max(arr) len = max_arr - min_arr + 1 temp = [0] * len result = [] for t in arr: temp[t-min_arr] = temp[t-min_arr] + 1 for i in range(min_arr,max_arr+1): p = [i]*temp[i-min_arr] result.extend(p) return result
性質：時間復雜度：O(n+k)、空間復雜度：O(k)、穩定排序、非原地排序（k為臨時陣列的大小）
9.桶排序
當數列取值范圍過大，或者不是整數時，不能適用計數排序
步驟：
1.創建若干個桶，確定每一個桶的區間范圍，里面可以承載一個或多個元素
2.遍歷原數列，把元素對號入座放入各個桶中
3.每個桶內部的元素分別排序
4.遍歷所有桶，輸出所有元素
def bucketSort(arr): n = len(arr) min_arr = min(arr) max_arr = max(arr) result = [] #創建n個桶 new_list = [[] for _ in range(n)] #區間跨度大小 length = (max_arr - min_arr) // (n - 1) for data in arr: index = int((data - min_arr) // (length + 1)) new_list[index].append(data) for i in range(n): new_list[i].sort() for i in range(n): for j in range(len(new_list[i])): result.append(new_list[i][j]) return result
性質：時間復雜度：O(n+k)、空間復雜度：O(n+k)、穩定排序、非原地排序（k為桶的個數）
10.基數排序
步驟：
1.先以個位數的大小來對資料進行排序，接著以十位數的大小來對資料進行排序，接著是百位數……
2.在以某位數進行排序時，需要準備0-9的10個桶，把相同數值的數放在同一個桶里
def radioSort(arr): #計算最大值是幾位數 num = 1 max_arr = max(arr) while max_arr // 10 > 0: max_arr = max_arr // 10 num += 1 for i in range(1,num+1): bucket = [[] for _ in range(10)] for j in range(len(arr)): radio = (arr[j] // int(pow(10,i-1))) % 10 bucket[radio].append(arr[j]) k = 0 for i in range(10): for j in range(len(bucket[i])): arr[k] = bucket[i][j] k += 1 return arr
性質：時間復雜度：O(kn)、空間復雜度：O(n+k)、穩定排序、非原地排序（k為桶的個數）
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/131509.html
標籤：Python
上一篇：資料預測,制做線性回歸方程
下一篇：對excel行的操作