计数排序
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 }
插入排序
插入排序，英文名（insertion sort）是一种简单且有效的比较排序算法。
思想： 在每次迭代过程中算法随机地从输入序列中移除一个元素，并将改元素插入待排序序列的正确位置。重复该过程，直到所有输入元素都被选择一次，排序结束。
类比：抓牌
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 } }
冒泡排序
冒泡排序是一种最简单的交换排序算法。
什么是交换？交换就是两两进行比较，如果不满足次序就可以交换位置。比如，我们想要从小到大排序，通过两个位置上的值两两比较，如果逆序就交换，使关键字大的记录像泡泡一样冒出来放在末尾。重复执行若干次冒泡排序，最终得到有序序列。
类比： 值较小的元素如同”气泡“一样逐渐漂浮到序列的顶端。
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 } } }
选择排序
选择排序（selection sort）是一种原地（in-place)排序算法，适用于数据量较少的情况。由于选择操作是基于键值的且交换操作只在需要时才执行，所以选择排序长用于数值较大和键值较小的文件。
package sort func selectionSort(nums []int) { length = len(nums) var minIdx int // 被选择的最小的值的位置 for i := 0; i < length-1; i++ { minIdx = i // 每次循环的第一个元素为最小值保存 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 } } }
堆排序
堆排序是一种树形选择排序算法。堆排序的过程：
- 构建初始堆
- 在输出堆的顶层元素后，从上到下进行调整，将顶层元素与其左右子树的根节点进行比较，并将最小的元素交换到堆的顶部；然后不断调整直到叶子节点得到新的堆。
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) } }
