Go 语言实现常见排序算法

举报
宇宙之一粟 发表于 2022/08/31 14:20:14 2022/08/31
【摘要】 计数排序package sortfunc 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...


计数排序

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

堆排序

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


  1. 构建初始堆

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


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) = 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]
    }
  }
}
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。