經典排序演算法總結與Go實現

學習Go語言第二周，本周任務嘗試實現七大經典排序演算法以及分析演算法複雜度、優劣及應用場景等，七大經典演算法分別為冒泡排序，插入排序，選擇排序，希爾排序，歸併排序，快速排序，堆排序。

冒泡排序

思路

正如「冒泡」二字，我的理解是重複一次比較相鄰的兩個數，大的數放在後面，小的數放在前面，一直重複到沒有任何一對數字需要交換位置為止。就像冒泡一樣，大的數不斷浮上來。

偽代碼

do swapped = false for i = 1 to indexOfLastUnsortedElement-1 if leftElement > rightElement swap(leftElement, rightElement) swapped = true; swapCounter++ while swapped

Go實現

func Bubble_Sort(arr []int) {

swapped := true

len := len(arr)

for swapped {

swapped = false

for i := 0; i

arr[i+1] {

arr[i], arr[i+1] = arr[i+1], arr[i]

swapped = true

}

} }選擇排序

先假設第一個元素為最小值，然後與剩餘的 len-1 個元素依次進行比較，標記最小數的位置，如果有更小的數，則在進行下一輪遍歷比較之前交換位置。

repeat (numOfElements - 1) times set the first unsorted element as the minimum for each of the unsorted elements if element

func Selection_Sort(arr []int) {

思路 這個排序感覺和選擇排序的思路有點相似的。首先1個長度的數組肯定是有序的，假設數組的長度為n，第一位是有序的，然後從第二位開始在已排序序列中從後向前掃描，找到相應位置並插入。

mark first element as sorted for each unsorted element X extract the element X for j = lastSortedIndex down to 0 if current element j > X move sorted element to the right by 1 break loop and insert X here

func Insertion_Sort(arr []int) {

= 0; j-- {

if arr[j] > selected {

arr[j], arr[j+1] = arr[j+1], arr[j]

} else {

arr[j+1] = selected

break

} }歸併排序

歸併排序是採用分治法的一個非常典型的應用。歸併排序的思想就是先遞歸分解數組，再合并數組。先考慮合并兩個有序數組，基本思路是比較兩個數組的最前面的數，誰小就先取誰，取了後相應的指針就往後移一位。然後再比較，直至一個數組為空，最後把另一個數組的剩餘部分複製過來即可。再考慮遞歸分解，基本思路是將數組分解成left和right，如果這兩個數組內部數據是有序的，那麼就可以用上面合并數組的方法將這兩個數組合并排序。如何讓這兩個數組內部是有序的？可以再二分，直至分解出的小組只含有一個元素時為止，此時認為該小組內部已有序。然後合并排序相鄰二個小組即可。（摘抄）

split each element into partitions of size 1 recursively merge adjancent partitions for i = leftPartStartIndex to rightPartLastIndex inclusive if leftPartHeadValue =gap && arr[j-gap]>temp { //插入排序 arr[j] = arr[j-gap] j = j-gap } arr[j] = temp } gap = gap/2 //重新設置步長 } }堆排序

堆排序是一種選擇排序，其時間複雜度為O(nlogn)

堆的定義

n個元素的序列當且僅當滿足下列關係之一時，稱之為堆。 情形1：ki = k2i+1 （最大化堆或大頂堆） 其中i=1,2,…,n/2向下取整; 若將和此序列對應的一維數組（即以一維數組作此序列的存儲結構）看成是一個完全二叉樹，則堆的含義表明，完全二叉樹中所有非終端結點的值均不大於（或不小於）其左、右孩子結點的值。 例如，下列兩個序列為堆，對應的完全二叉樹如圖：

若在輸出堆頂的最小值之後，使得剩餘n-1個元素的序列重又建成一個堆，則得到n個元素的次小值。如此反覆執行，便能得到一個有序序列，這個過程稱之為堆排序。堆排序（Heap Sort）只需要一個記錄元素大小的輔助空間（供交換用），每個待排序的記錄僅佔有一個存儲空間。

堆的存儲

一般用數組來表示堆，若根結點存在序號0處， i結點的父結點下標就為(i-1)/2。i結點的左右子結點下標分別為2i+1和2i+2。（註：如果根結點是從1開始，則左右孩子結點分別是2i和2i+1。）如第0個結點左右子結點下標分別為1和2。如最大化堆如下：左圖為其存儲結構，右圖為其邏輯結構。

堆的排序實現

構造最大堆（Build_Max_Heap）：若數組下標範圍為0~n，考慮到單獨一個元素是大根堆，則從下標n/2開始的元素均為大根堆。於是只要從n/2-1開始，向前依次構造大根堆，這樣就能保證，構造到某個節點時，它的左右子樹都已經是大根堆。

堆排序（HeapSort）：由於堆是用數組模擬的。得到一個大根堆後，數組內部並不是有序的。因此需要將堆化數組有序化。思想是移除根節點，並做最大堆調整的遞歸運算。第一次將heap[0]與heap[n-1]交換，再對heap[0…n-2]做最大堆調整。第二次將heap[0]與heap[n-2]交換，再對heap[0…n-3]做最大堆調整。重複該操作直至heap[0]和heap[1]交換。由於每次都是將最大的數併入到後面的有序區間，故操作完後整個數組就是有序的了。

最大堆調整（Max_Heapify）：該方法是提供給上述兩個過程調用的。目的是將堆的末端子節點作調整，使得子節點永遠小於父節點 。

func Heap_Sort(arr []int) { N := len(arr) var first int = N/2 //最後一個非葉子節點 for start := first; start > -1; start-- { //構造大根堆 max_heapify(arr, start, N-1) } for end := N-1; end > 0; end-- { //堆排，將大根堆轉換成有序數組 arr[end],arr[0] = arr[0],arr[end] max_heapify(arr, 0, end-1) } } func max_heapify(arr []int, start int, end int) { root := start for true { child := root*2 + 1 //調整節點的子節點 if child > end { break } if child + 1

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！