手撕程式碼之常用排序演算法
- 2019 年 10 月 6 日
- 筆記
手撕程式碼之常用排序演算法
0.導語
本節為手撕程式碼系列之第一彈，主要來手撕排序演算法，主要包括以下幾大排序演算法：
- 直接插入排序
- 冒泡排序
- 選擇排序
- 快速排序
- 希爾排序
- 堆排序
- 歸併排序
1.直接插入排序
【演算法思想】
每一步將一個待排序的記錄，插入到前面已經排好序的有序序列中去，直到插完所有元素為止。
【程式碼實現】
# 直接插入排序 def insert_sort(arr): length = len(arr) for i in range(length): k = i for j in range(k,0,-1): if arr[j]<arr[j-1]: t = arr[j] arr[j]=arr[j-1] arr[j-1]=t arr = [4,3,0,-1] insert_sort(arr) print(arr)
2.冒泡排序
【演算法思想】
對相鄰的元素進行兩兩比較，順序相反則進行交換，這樣，每一趟會將最小或最大的元素「浮」到頂端，最終達到完全有序。
【程式碼實現】
# 冒泡排序 def bubbleSort(arr): length = len(arr) for i in range(length-1): flag = True for j in range(length-i-1): if arr[j]>arr[j+1]: t = arr[j] arr[j]=arr[j+1] arr[j+1]=t flag = False if flag: break arr = [6,-2,0,9] bubbleSort(arr) print(arr)
3.選擇排序
【演算法思想】
每一趟從待排序的數據元素中選擇最小（或最大）的一個元素作為首元素，直到所有元素排完為止，簡單選擇排序是不穩定排序。
【程式碼實現】
def selectSort(arr): length = len(arr) for i in range(length-1): min = i for j in range(i+1,length): if arr[min]>arr[j]: min=j if min!=i: t = arr[i] arr[i]=arr[min] arr[min]=t arr = [6,-2,0,9] selectSort(arr) print(arr)
4.快速排序
【演算法思想】
快速排序思想—-分治法。
- 先從數列中取出一個數作為基準數。
- 分區過程，將比這個數大的數全放到它的右邊，小於或等於它的數全放到它的左邊。
- 再對左右區間重複第二步，直到各區間只有一個數。
每次劃分得到，樞椎的左邊比它小，右邊比它大。
【程式碼實現】
def quickSort(arr,left,right): # 遞歸終止條件 if left>right: return pivot = arr[left] i = left j = right while i<j: while i<j and arr[j]>=pivot: j-=1 while i<j and arr[i]<=pivot: i+=1 if i<j: t = arr[i] arr[i] = arr[j] arr[j] = t # 放入樞椎 arr[left] = arr[i] arr[i]=pivot # 遞歸調用左區域 quickSort(arr,left,i-1) # 遞歸調用右區域 quickSort(arr,i+1,right) arr = [6,-2,0,9] quickSort(arr,0,len(arr)-1) print(arr)
5.希爾排序
【演算法思想】
該演算法也被稱為：縮小增量排序。
希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，演算法便終止。
【程式碼實現】
# 希爾排序 def shellSort(arr): length = len(arr) # 設置初始增量 gap = length//2 while gap>0: # 從第gap個元素，逐個對其所在組進行直接插入排序 for i in range(gap,length): j = i while j-gap>=0 and arr[j]<arr[j-gap]: t = arr[j] arr[j] = arr[j-gap] arr[j-gap] = t j-=gap gap//=2 arr = [6,-2,0,9] shellSort(arr) print(arr)
6.堆排序
【演算法思想】
堆是具有以下性質的完全二叉樹：每個結點的值都大於或等於其左右孩子結點的值，稱為大頂堆；或者每個結點的值都小於或等於其左右孩子結點的值，稱為小頂堆。
基本思路：
a.將無需序列構建成一個堆，根據升序降序需求選擇大頂堆或小頂堆;
b.將堆頂元素與末尾元素交換，將最大元素"沉"到數組末端;(升序方法)
c.重新調整結構，使其滿足堆定義，然後繼續交換堆頂元素與當前末尾元素，反覆執行調整+交換步驟，直到整個序列有序。
【程式碼實現】
class HeapSort: def heapSort(self, nums): length = len(nums) # 從後往前遍歷，交換堆頂與最後葉子節點，並依次調整堆，重複操作 for j in range(length-1,0,-1): # 獲取堆頂元素(獲取同時，調整堆) firstNum = self.adjustHeap(nums,j+1) # 交換最後一個葉子節點與堆頂元素 temp = nums[j] nums[j] = firstNum nums[0] = temp return nums # 調整堆(最大堆)，每次返回最大堆頂元素 def adjustHeap(self,nums,length): # 最後一個非葉節點 i = length//2 -1 # 從最後一個非葉節點開始調整，構成最大堆 while i>=0: temp = nums[i] k = 2*i+1 while k<length: if k+1<length and nums[k]<nums[k+1]: k+=1 if nums[k]>temp: nums[i]=nums[k] i=k else: break k=2*k+1 nums[i] = temp i-=1 return nums[0] s = HeapSort() nums = [8,9,7,10] t = s.heapSort(nums) print(t)
7.歸併排序
【演算法思想】
歸併排序是利用歸併的思想實現的排序方法，該演算法採用經典的分治策略（分治法將問題分(divide)成一些小的問題然後遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)。
【程式碼實現】
def mergeSort(nums): if len(nums)<=1: return nums mid = len(nums)//2 left = mergeSort(nums[:mid]) right = mergeSort(nums[mid:]) return merge(left,right) def merge(left,right): result = [] i,j = 0,0 while i<len(left) and j<len(right): if left[i]<=right[j]: result.append(left[i]) i+=1 else: result.append(right[j]) j+=1 if i<len(left): result+=left[i:] if j<len(right): result+=right[j:] return result nums = [5,3,0,6,1,4] t = mergeSort(nums) print(t)
