Go 语言实现常见排序算法(上)

简介: 在每次迭代过程中算法随机地从输入序列中移除一个元素,并将改元素插入待排序序列的正确位置

计数排序

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


堆排序

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


  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)
  }
}
相关文章
|
3月前
|
算法 安全 Go
如何通过 go 语言实现雪花算法?
在Go语言中,可通过实现雪花算法(Snowflake)生成分布式唯一ID。该算法由Twitter提出,将64位ID分为时间戳、机器ID和序列号三部分。文章介绍了算法结构、Go语言实现代码、代码说明、示例输出、优点及注意事项。此算法具备高性能、分布式支持和有序性特点,适用于数据库主键等场景。使用时需确保机器ID唯一与时钟同步。
|
2月前
|
搜索推荐 算法 Go
Go语言数组排序(冒泡排序法)—— 用最直观的方式掌握排序算法
本案例介绍使用冒泡排序对整数数组进行升序排序的实现方法,涵盖输入处理、错误检查与排序逻辑。通过代码演示和算法解析,帮助理解排序原理及Go语言切片操作,为学习更复杂排序算法打下基础。
|
28天前
|
数据采集 Go API
Go语言实战案例:多协程并发下载网页内容
本文是《Go语言100个实战案例 · 网络与并发篇》第6篇,讲解如何使用 Goroutine 和 Channel 实现多协程并发抓取网页内容,提升网络请求效率。通过实战掌握高并发编程技巧,构建爬虫、内容聚合器等工具,涵盖 WaitGroup、超时控制、错误处理等核心知识点。
|
1月前
|
数据采集 JSON Go
Go语言实战案例:实现HTTP客户端请求并解析响应
本文是 Go 网络与并发实战系列的第 2 篇,详细介绍如何使用 Go 构建 HTTP 客户端,涵盖请求发送、响应解析、错误处理、Header 与 Body 提取等流程,并通过实战代码演示如何并发请求多个 URL,适合希望掌握 Go 网络编程基础的开发者。
|
2月前
|
JSON 前端开发 Go
Go语言实战:创建一个简单的 HTTP 服务器
本篇是《Go语言101实战》系列之一,讲解如何使用Go构建基础HTTP服务器。涵盖Go语言并发优势、HTTP服务搭建、路由处理、日志记录及测试方法,助你掌握高性能Web服务开发核心技能。
|
2月前
|
Go
如何在Go语言的HTTP请求中设置使用代理服务器
当使用特定的代理时,在某些情况下可能需要认证信息,认证信息可以在代理URL中提供,格式通常是:
162 0
|
3月前
|
JSON 编解码 API
Go语言网络编程:使用 net/http 构建 RESTful API
本章介绍如何使用 Go 语言的 `net/http` 标准库构建 RESTful API。内容涵盖 RESTful API 的基本概念及规范,包括 GET、POST、PUT 和 DELETE 方法的实现。通过定义用户数据结构和模拟数据库,逐步实现获取用户列表、创建用户、更新用户、删除用户的 HTTP 路由处理函数。同时提供辅助函数用于路径参数解析,并展示如何设置路由器启动服务。最后通过 curl 或 Postman 测试接口功能。章节总结了路由分发、JSON 编解码、方法区分、并发安全管理和路径参数解析等关键点,为更复杂需求推荐第三方框架如 Gin、Echo 和 Chi。
|
4月前
|
机器学习/深度学习 存储 监控
上网管理监控软件的 Go 语言流量特征识别算法实现与优化
本文探讨基于Go语言的流量特征识别算法,用于上网管理监控软件。核心内容涵盖AC自动机算法原理、实现及优化,通过路径压缩、哈希表存储和节点合并策略提升性能。实验表明,优化后算法内存占用降低30%,匹配速度提升20%。在1000Mbps流量下,CPU利用率低于10%,内存占用约50MB,检测准确率达99.8%。未来可进一步优化高速网络处理能力和融合机器学习技术。
129 10
|
4月前
|
分布式计算 Go C++
初探Go语言RPC编程手法
总的来说,Go语言的RPC编程是一种强大的工具,让分布式计算变得简单如同本地计算。如果你还没有试过,不妨挑战一下这个新的编程领域,你可能会发现新的世界。
99 10
|
4月前
|
人工智能 算法 Go
Go实现常见的限流算法
本文介绍了五种常见的限流算法:固定窗口、滑动窗口、漏桶算法、令牌桶和滑动日志。固定窗口简单高效,但可能产生两倍突发流量;滑动窗口可避免突发问题,但可能掐断流量;漏桶算法搭配生产者消费者模式实现平滑流量;令牌桶允许一定突发流量;滑动日志适用于多级限流场景。每种算法通过Go语言实现并附有代码解读,帮助理解其工作原理与适用场景。