希尔排序
package sort func swap(array []int, a int, b int) { array[a] = array[a] + array[b] array[b] = array[a] - array[b] array[a] = array[a] - array[b] } func shellSort(array []int) { length = len(array) for gap := length / 2; gap > 0; gap = gap / 2 { for i := gap; i < length; i++ { var j = i for { if j-gap < 0 || array[j] >= array[j-gap] { break } swap(array, j, j-gap) j = j - gap } } } }
归并排序
利用递归与分治技术将数据序列划分成为越来越小的半子表，再对半子表排序，最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列。其中“归”代表的是递归的意思，即递归地将数组折半地分离为单个数组。
给定一组序列含 n 个元素，首先将每两个相邻的长度为 1 的子序列进行归并，得到 n/2（向上取整）个长度为 2 或 1 的有序子序列，再将其两两归并，反复执行此过程，直到得到一个有序序列为止。
package sort /* merge sort O(nlgn): T(n) = 2T(n/2) + O(n) master theorem: a = 2, b = 2, f(n) = n logb(a) = lg2 = 1 f(n) = f(n^logb(a)) = f(n^1) so, O(n) = O(n^logb(a)lgn) = O(nlgn) */ import ( "sync" ) func merge(arr []int) { i := len(arr) / 2 //copy left and right array leftArr, rightArr := make([]int, i, i), make([]int, len(arr)-i, len(arr)-i) copy(leftArr, arr[:i]) copy(rightArr, arr[i:]) leftIter, rightIter := ints(leftArr).Iter(), ints(rightArr).Iter() leftValue, leftHasNext := leftIter() rightValue, rightHasNext := rightIter() //merge for k := range arr { if !leftHasNext { //left empty, use right value, in CLRS, use infinity arr[k] = rightValue rightValue, rightHasNext = rightIter() } else if !rightHasNext { //right empty, use left value, in CLRS, use infinity arr[k] = leftValue leftValue, leftHasNext = leftIter() } else { if leftValue > rightValue { arr[k] = rightValue rightValue, rightHasNext = rightIter() } else { arr[k] = leftValue leftValue, leftHasNext = leftIter() } } } } func mergeSort(arr []int) { i := len(arr) / 2 if i > 0 { mergeSort(arr[:i]) mergeSort(arr[i:]) merge(arr) } } func mergeSortParallel(arr []int) { i := len(arr) / 2 if i > 0 { var wd sync.WaitGroup wd.Add(2) go func() { mergeSortParallel(arr[:i]) wd.Done() }() go func() { mergeSortParallel(arr[i:]) wd.Done() }() wd.Wait() merge(arr) } }
快速排序
高效的排序算法，它采用 分而治之 的思想，把大的拆分为小的，小的再拆分为更小的。
其原理是：对于一组给定的记录，通过一趟排序后，将原序列分为两部分，其中前部分的所有记录均比后部分的所有记录小，然后再依次对前后两部分的记录进行快速排序，递归该过程，直到序列中的所有记录均有序为止。
package sort import "math/rand" func partition(arr []int) (primeIdx int) { primeIdx = 0 for i := 0; i < len(arr)-1; i++ { if arr[i] < arr[len(arr)-1] { arr[i], arr[primeIdx] = arr[primeIdx], arr[i] primeIdx++ } } arr[primeIdx], arr[len(arr)-1] = arr[len(arr)-1], arr[primeIdx] return } func quickSort(arr []int) { if len(arr) > 1 { primeIdx := partition(arr) quickSort(arr[:primeIdx]) quickSort(arr[primeIdx+1:]) } } func randomQuickSort(arr []int) { if len(arr) > 1 { primeIdx := rand.Intn(len(arr)) arr[primeIdx], arr[len(arr)-1] = arr[len(arr)-1], arr[primeIdx] primeIdx = partition(arr) randomQuickSort(arr[:primeIdx]) randomQuickSort(arr[primeIdx+1:]) } } func quickSortTail(arr []int) { for len(arr) > 1 { primeIdx := partition(arr) if primeIdx < len(arr)/2 { quickSortTail(arr[:primeIdx]) arr = arr[primeIdx+1:] } else { quickSortTail(arr[primeIdx+1:]) arr = arr[:primeIdx] } } }
