利用遞歸與分治技術(shù)將數(shù)據(jù)序列劃分成為越來越小的半子表，再對半子表排序，最后再用遞歸步驟將排好序的半子表合并成為越來越大的有序序列。其中“歸”代表的是遞歸的意思，即遞歸地將數(shù)組折半地分離為單個數(shù)組。
1.計數(shù)排序
package sort
func countingSort(arr []int, bias int) (retArr []int) {
countingArr := make([]int, bias+1, bias+1)
retArr = make([]int, len(arr), cap(arr))
for _, v := range arr {
countingArr[v]++
}
for i := 1; i < len(countingArr); i++ {
countingArr[i] += countingArr[i-1]
}
for i := len(arr) - 1; i >= 0; i-- {
retArr[countingArr[arr[i]]-1] = arr[i]
countingArr[arr[i]]--
}
return
}
2.插入排序
插入排序，英文名（insertion sort）是一種簡單且有效的比較排序算法。
思想：在每次迭代過程中算法隨機地從輸入序列中移除一個元素，并將改元素插入待排序序列的正確位置。重復(fù)該過程，直到所有輸入元素都被選擇一次，排序結(jié)束。
類比：抓牌
package sort
func insertionSort(unsorted []int) {
length = len(unsorted)
for i := 0; i < length; i++ {
var insertElement = unsorted[i]
var insertPosition = i
for j := insertPosition - 1; j >= 0; j-- {
if insertElement < unsorted[j] {
unsorted[j+1] = unsorted[j]
insertPosition--
}
}
unsorted[insertPosition] = insertElement
}
}
詳見文章：跟著動畫學 Go 數(shù)據(jù)結(jié)構(gòu)之插入排序
3.冒泡排序
冒泡排序是一種最簡單的交換排序算法。
什么是交換？交換就是兩兩進行比較，如果不滿足次序就可以交換位置。比如，我們想要從小到大排序，通過兩個位置上的值兩兩比較，如果逆序就交換，使關(guān)鍵字大的記錄像泡泡一樣冒出來放在末尾。重復(fù)執(zhí)行若干次冒泡排序，最終得到有序序列。
類比： 值較小的元素如同”氣泡“一樣逐漸漂浮到序列的頂端。
package sort
func bubbleSort(nums []int) {
length = len(nums)
lastSwap := length - 1
lastSwapTemp := length - 1
for j := 0; j < length; j++ {
lastSwap = lastSwapTemp
for i := 0; i < lastSwap; i++ {
if nums[i] > nums[i+1] {
nums[i], nums[i+1] = nums[i+1], nums[i]
lastSwapTemp = i
}
}
if lastSwap == lastSwapTemp {
break
}
}
}
4.選擇排序
選擇排序（selection sort）是一種原地（in-place)排序算法，適用于數(shù)據(jù)量較少的情況。由于選擇操作是基于鍵值的且交換操作只在需要時才執(zhí)行，所以選擇排序長用于數(shù)值較大和鍵值較小的文件。
package sort
func selectionSort(nums []int) {
length = len(nums)
var minIdx int // 被選擇的最小的值的位置
for i := 0; i < length-1; i++ {
minIdx = i
// 每次循環(huán)的第一個元素為最小值保存
var minValue = nums[minIdx]
for j := i; j < length-1; j++ {
if minValue > nums[j+1] {
minValue = nums[j+1]
minIdx = j + 1
}
}
// 如果最小值的位置改變，將當前的最小值位置保存
if i != minIdx {
var temp = nums[i]
nums[i] = nums[minIdx]
nums[minIdx] = temp
}
}
}
詳見文章：跟著動畫學Go數(shù)據(jù)結(jié)構(gòu)之選擇排序
5.堆排序
堆排序是一種樹形選擇排序算法。堆排序的過程：
構(gòu)建初始堆
在輸出堆的頂層元素后，從上到下進行調(diào)整，將頂層元素與其左右子樹的根節(jié)點進行比較，并將最小的元素交換到堆的頂部；然后不斷調(diào)整直到葉子節(jié)點得到新的堆。
package sort
import (
"github.com/shady831213/algorithms/heap"
)
func heapSort(arr []int) {
h := heap.NewHeapIntArray(arr)
for i := h.Len() - 1; i > 0; i-- {
h.Pop()
}
}
/*not generic heap*/
type intArrayForHeapSort []int
func (h *intArrayForHeapSort) parent(i int) int {
return i >> 1
}
func (h *intArrayForHeapSort) left(i int) int {
return (i << 1) + 1
}
func (h *intArrayForHeapSort) right(i int) int {
return (i << 1) + 2
}
func (h *intArrayForHeapSort) maxHeaplify(i int) {
largest, largestIdx := (*h)[i], i
if (*h).left(i) < len((*h)) && (*h)[(*h).left(i)] > largest {
largest, largestIdx = (*h)[(*h).left(i)], (*h).left(i)
}
if h.right(i) < len((*h)) && (*h)[h.right(i)] > largest {
_, largestIdx = (*h)[h.right(i)], h.right(i)
}
if i != largestIdx {
(*h)[largestIdx], (*h)[i] = (*h)[i], (*h)[largestIdx]
h.maxHeaplify(largestIdx)
}
}
func (h *intArrayForHeapSort) buildHeap() {
for i := (len((*h)) >> 1) - 1; i >= 0; i-- {
h.maxHeaplify(i)
}
}
func heapSort2(arr []int) {
h := intArrayForHeapSort(arr)
h.buildHeap()
for i := len(h) - 1; i > 0; i-- {
h[0], h[i] = h[i], h[0]
h = h[:i]
h.maxHeaplify(0)
}
}
詳見文章：跟著動畫學Go數(shù)據(jù)結(jié)構(gòu)之堆排序
6.希爾排序
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
}
}
}
}
詳見文章：跟著動畫學Go數(shù)據(jù)結(jié)構(gòu)之希爾排序
7.歸并排序
利用遞歸與分治技術(shù)將數(shù)據(jù)序列劃分成為越來越小的半子表，再對半子表排序，最后再用遞歸步驟將排好序的半子表合并成為越來越大的有序序列。其中“歸”代表的是遞歸的意思，即遞歸地將數(shù)組折半地分離為單個數(shù)組。
給定一組序列含n個元素，首先將每兩個相鄰的長度為1的子序列進行歸并，得到n/2（向上取整）個長度為2或1的有序子序列，再將其兩兩歸并，反復(fù)執(zhí)行此過程，直到得到一個有序序列為止。
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)
}
}
8.快速排序
高效的排序算法，它采用 分而治之 的思想，把大的拆分為小的，小的再拆分為更小的。
其原理是：對于一組給定的記錄，通過一趟排序后，將原序列分為兩部分，其中前部分的所有記錄均比后部分的所有記錄小，然后再依次對前后兩部分的記錄進行快速排序，遞歸該過程，直到序列中的所有記錄均有序為止。
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]
}
}
}
