逐一將要排序的資料插入已排序好的序列中
notion: [ sorted array | unsorted array] [ "a" ] : target example given array: [5, 3, 4, 6, 1] 1. 3 < 5 : swap(array, 0, 1) => ["3", 5 | 4, 6, 1] 2. 4 < 5 : swap(array, 2, 1) => [3, "4", 5 | 6, 1] 3. 6 > 5 : => [3, 4, 5, 6 | 1] 4. 1 < 6 : swap(array, 4, 3) => [3, 4, 5, "1", 6] 1 < 5 : swap(array, 3, 2) => [3, 4, "1", 5, 6] 1 < 4 : swap(array, 2, 1) => [3, "1", 4, 5, 6] 1 < 3 : swap(array, 1, 0) => ["1", 3, 4, 5, 6] finish
func insertionSort(array []int) []int { for i := 1; i < len(array); i++ { j := i - 1 target := array[i] for j >= 0 && target < array[j] { array[j+1] = array[j] j-- } array[j+1] = target } return array }
將array分成排序好的和未排序好的array，逐一將未排序好的array的最大（最小）值換到未排序好的array的最後面
notion: [ sorted array | unsorted array] [ "a" ] : max example given array: [5, 3, 4, 6, 1] 1. max value: 6 => [5, 3, 4, 1 | 6] 2. max value: 5 => [3, 4, 1 | 5, 6] 3. max value: 4 => [3, 1 | 4, 5, 6] 4. max value: 3 => [1, 3, 4, 5, 6] finish
func prefixMax(array []int, i int) int { if i > 0 { j := prefixMax(array, i-1) if array[j] > array[i] { return j } } return i } func sort(array []int, i int) { if i > 0 { j := prefixMax(array, i) array[i], array[j] = array[j], array[i] sort(array[:], i-1) } } func selectionSort(array []int) []int { sort(array[:], len(array)-1) return array }
每一輪從 unsorted array index 0 開始往後兩兩相比較，將較大（小）的往後交換，每一輪都將最大的值換到 unsorted array 後面，當一輪內沒交換過則代表排序完畢
notion: [ sorted array | unsorted array] [ "a, b" ] : comparision example given array: [5, 3, 4, 6, 1] 1. ["5, 3", 4, 6, 1] => 5 > 3 swap(array, 1, 0) => [3, 5, 4, 6, 1] 2. [3, "5, 4", 6, 1] => 5 > 4 swap(array, 2, 1) => [3, 4, 5, 6, 1] 3. [3, 4, "5, 6", 1] => 6 > 5 do nothing => [3, 4, 5, 6, 1] 4. [3, 4, 5, "6, 1"] => 6 > 1 swap(array, 4, 3) => [3, 4, 5, 1, 6] -------- finish first round ----- 1. ["3, 4", 5, 1 | 6] => 4 > 3 do nothing => [3, 4, 5, 1 | 6] 2. [3, "4, 5", 1 | 6] => 5 > 4 do nothing => [3, 4, 5, 1 | 6] 3. [3, 4, "5, 1" | 6] => 1 < 5 swap(array, 3, 2) => [3, 4, 1, 5 | 6] -------- finish second round ----- 1. ["3, 4", 1 | 5, 6] => 4 > 3 do nothing => [3, 4, 1 | 5, 6] 2. [3, "4, 1" | 5, 6] => 1 < 4 swap(array, 2, 1) => [3, 1, 4 | 5, 6] -------- finish third round ----- 1. ["3, 1" | 4, 5, 6] => 1 < 3 swap(array, 1, 0) => [1, 3 | 4, 5, 6] finish
func bubbleSort(array []int) []int { n := len(array) for i := 0; i < n; i++ { isSorted := true for j := 0; j < n-i-1; j++ { if array[j] > array[j+1] { array[j], array[j+1] = array[j+1], array[j] isSorted = false } } if isSorted { break } } return array }
Merge sort 屬於divide and conquer 的方式，將array切割成subarray在合併成sorted array
example given array: [5, 3, 4, 6, 1] 5, 3, 4, 6, 1 / \ 5, 3 4, 6, 1 / \ / \ 5 3 4 6, 1 \ / | / \ 3, 5 | 6 1 | | \ / | | 1, 6 | \ / | 1, 4, 6 \ / 1, 3, 4, 5, 6
func merge(left []int, right []int) []int { l := len(left) + len(right) arr := make([]int, l) arr1 := make([]int, len(left)) arr2 := make([]int, len(right)) arr1 = append(arr1, math.MaxInt) arr2 = append(arr2, math.MaxInt) i1, i2 := 0, 0 for i := 0; i < l; i++ { if arr1[i1] < arr2[i2] { arr[i] = arr1[i1] i1++ } else { arr[i] = arr2[i2] i2++ } } return arr } func divideAndConquer(array []int) []int { if len(array) < 2 { return array } middle := len(array) / 2 leftArray := array[:middle] rightArray := array[middle:] return merge(divideAndConquer(leftArray), divideAndConquer(rightArray)) } func mergeSort(array []int) []int { return divideAndConquer(array) }
在array找一個基準點，將此array變成基準點前的subarray都小於基準點，基準點後的subarray都大於基準點，此過程稱作partition。接著再對基準點左右的subarray都做partition。
notion: "a": baseline example given array: [5, 3, 4, 6, 1] base: array[0] 1. [3, 4, 1, "5", 6] => left: [3, 4, 1, 5], right: [6] 2. [1, "3", 4, 5 | 6]
func partition(array []int) int { base := array[0] pivot := -1 for i := 0; i < len(array); i++ { if array[i] <= base { pivot += 1 array[pivot], array[i] = array[i], array[pivot] } } array[pivot], array[0] = array[0], array[pivot] return pivot + 1 } func sorting(array []int) { if len(array) < 2 { return } pivot := partition(array) sorting(array[:pivot]) sorting(array[pivot:]) } func quickSort(array []int) []int { sorting(array[:]) return array }
為selection sort 的變形，將找unsorted array的最大值的過程使用heap。過程分成兩部分， 1. buildHeap: 使array符合heap的規則。 2. 不停的砍斷heap的head, 與heapify
example given array: [5, 3, 4, 6, 1] 5 "5" <- heapify / \ / \ heapify-> "3" 4 => 6 4 / \ / \ 6 1 3 1 6 => / \ => [6, 5, 4, 3, 1] 5 4 / \ 3 1 => cut off head "1" <-heapify => / \ => [1, 5, 4, 3 | 6] 5 4 / 3 5 5 => / \ => / \ heapify-> "1" 4 3. 4 / / 3 1 => cut off head 1 => / \ => [1, 3, 4 | 5, 6] heapify-> 3 4 ...
func heapify(array []int, n int, i int) { left := 2*i + 1 right := 2*i + 2 max := i if left < n && array[left] > array[max] { max = left } if right < n && array[right] > array[max] { max = right } if max != i { array[max], array[i] = array[i], array[max] heapify(array[:], n, max) } } // parent: ( i - 1 ) / 2 // left: i * 2 + 1 // right: i * 2 + 2 func buildHeap(array []int, n int) { lastNode := n - 1 parent := (lastNode - 1) / 2 for i := parent; i >= 0; i-- { heapify(array[:], n, i) } } func heapSort(array []int) []int { n := len(array) buildHeap(array[:], n) for i := n - 1; i > 0; i-- { array[0], array[i] = array[i], array[0] heapify(array[:], i, 0) } return array }
| algorithm | Best Case | Average Case | Worst Case |
|---|---|---|---|
| Insertion sort | o(n) | o(n^2) | o(n^2) |
| Selection sort | o(n^2) | o(n^2) | o(n^2) |
| Bubble sort | o(n) | o(n^2) | o(n^2) |
| Merge sort | o(nlogn) | o(nlogn) | o(nlogn) |
| Quick Sort | o(nlogn) | o(nlogn) | o(n^2) |
| Heap sort | o(nlogn) | o(nlogn) | o(nlogn) |