开源一夏 | Go 语言实现常见排序算法

2022 年 8 月 29 日
广东
本文字数：3958 字
阅读完需：约 13 分钟

计数排序

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    }}

复制代码

详见文章：跟着动画学 Go 数据结构之插入排序

冒泡排序

冒泡排序是一种最简单的交换排序算法。

什么是交换？交换就是两两进行比较，如果不满足次序就可以交换位置。比如，我们想要从小到大排序，通过两个位置上的值两两比较，如果逆序就交换，使关键字大的记录像泡泡一样冒出来放在末尾。重复执行若干次冒泡排序，最终得到有序序列。

类比： 值较小的元素如同”气泡“一样逐渐漂浮到序列的顶端。

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    }  }}

复制代码

详见文章：跟着动画学Go数据结构之选择排序

堆排序

堆排序是一种树形选择排序算法。堆排序的过程：

构建初始堆
在输出堆的顶层元素后，从上到下进行调整，将顶层元素与其左右子树的根节点进行比较，并将最小的元素交换到堆的顶部；然后不断调整直到叶子节点得到新的堆。

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数据结构之堆排序

希尔排序

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数据结构之希尔排序

归并排序

利用递归与分治技术将数据序列划分成为越来越小的半子表，再对半子表排序，最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列。其中“归”代表的是递归的意思，即递归地将数组折半地分离为单个数组。

给定一组序列含 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) = nlogb(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]    }  }}

复制代码

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/09cf8603d432c359e5616c1e9】。文章转载请联系作者。

宇宙之一粟

关注

宇宙古今无有穷期，一生不过须臾，当思奋争 2020.05.07 加入

🏆InfoQ写作平台-第二季签约作者 🏆 混迹于江湖，江湖却没有我的影子热爱技术，专注于后端全栈，轻易不换岗拒绝内卷，工作于软件工程师，弹性不加班热衷分享，执着于阅读写作，佛系不水文

发布

暂无评论

创作场景

开源一夏 | Go 语言实现常见排序算法

计数排序

插入排序

冒泡排序

选择排序

堆排序

希尔排序

归并排序

快速排序

宇宙之一粟

评论