一. 歸并排序演算法簡介
歸并排序演算法是一種采用了分治策略的排序演算法，它通過遞回地先使每個子序列有序，再將兩個有序的序列進行合并成一個有序的序列（也可以采用非遞回的方式實作，效率更高一些），歸并演算法是穩定和高效的排序演算法（適用于復雜物件（結構體）數列的穩定排序）
二. 演算法復雜度
最理想情況：O(nlogn)
最壞情況： O(nlogn)
三. 演算法分治思路
- 將陣列切片為相同長度的兩部分，長度為LEN的陣列，分解為：兩個子陣列，一個是 nums[0...LEN/2] 另一個是 nums[LEN/2+1...LEN]
- 遞回的對兩個部分進行相同的切片操作，直到陣列長度為1
- 對已經排好序的兩個切片進行合并操作
五. 演算法實作
5.1 遞回實作
package main import ( "fmt" )func mergeSort1(array []int) []int { arrLen := len(array); if arrLen < 2 { return array; } i := arrLen >>1; leftSub := mergeSort1(array[0:i]); rightSub := mergeSort1(array[i:]); result := merge1(leftSub, rightSub); return result; }
func merge1(left []int, right []int) []int { m := len(left); n := len(right); result := make([]int, m+n, m+n); i, j, k := 0, 0, 0; for i < m && j < n { if left[i] <= right[j] { result[k] = left[i]; k++; i++; } else { result[k] = right[j]; k++; j++; } } if i == m { for j < n { result[k] = right[j]; k++; j++; } } if j == n { for i < m { result[k] = left[i]; k++; i++; } } return result; } 5.2 非遞回實作 //merge sort using no recursion /**** // i: the begin index of old sub-array, j: the begin index of even sub-array
|<- k ->| |<- k ->| //case: k = 4 array [0,1,2,3] [4,5,6,7][8,9] ^ ^ ^ i j arrLen ****/
//merge sort using no recursion func mergeSort2(array []int){ arrLen := len(array); if arrLen <= 0 { return; }
list := make([]int, arrLen, arrLen); source := &array; target := &list; flag := 0;
// k is the arrLength of sub-array,k=1,2,4,... for k:= 1; k < arrLen; k <<=1 { if flag == 1{ source = &list; target = &array; } else { source = &array; target = &list; } flag = 1 - flag; //i, j is the begin index of sub-array i, j := 0, k; for n:= 0 ; n < arrLen; { p, q:= i, j; pEnd := i + k; if pEnd > arrLen { pEnd = arrLen; } qEnd := j + k; if qEnd > arrLen { qEnd = arrLen; } for (p < pEnd) && (q < qEnd) { if (*source)[p] <= (*source)[q] { (*target)[n] = (*source)[p]; n++; p++; } else { (*target)[n] = (*source)[q]; n++; q++; } } //copy the left data of sub_array indexed by q if p >= pEnd { for q < qEnd { (*target)[n] = (*source)[q]; n++; q++; } } //copy the left data of sub_array indexed by p if q >= qEnd { for p < pEnd { (*target)[n] = (*source)[p]; n++; p++; } }
i += k << 1; j += k << 1; } } if flag == 1 { for r:=0; r < arrLen; r++ { array[r] = list[r]; } } }
func main() { arr := []int{9,4, 6, 8, 6, 30, 28, 2, 3, 50}; fmt.Println(arr);
sortArr := mergeSort1(arr); fmt.Println(sortArr);
mergeSort2(arr); fmt.Println(arr); } 說明，遞回演算法容易理解，因為涉及到嵌套遞回和臨時空間開銷，效率不高，在專案實踐中不建議使用；非遞回演算法，采用自下向上從最小長度為1的子陣列（子陣列長度分別為：1,2,4,8，...直到大于原陣列長度）開始歸并，直到歸并排序完成，效率很高，另外只申請了和原陣列等長的臨時空間用于存盤中間歸并結果，空間開銷小，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/455631.html
標籤：Go