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


归并排序

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


给定一组序列含 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]
    }
  }
}
相关文章
|
3天前
|
存储 Go
Go 语言入门指南:切片
Golang中的切片(Slice)是基于数组的动态序列,支持变长操作。它由指针、长度和容量三部分组成,底层引用一个连续的数组片段。切片提供灵活的增减元素功能,语法形式为`[]T`,其中T为元素类型。相比固定长度的数组,切片更常用,允许动态调整大小,并且多个切片可以共享同一底层数组。通过内置的`make`函数可创建指定长度和容量的切片。需要注意的是,切片不能直接比较,只能与`nil`比较,且空切片的长度为0。
Go 语言入门指南:切片
|
7天前
|
算法 安全 Go
公司局域网管理系统里的 Go 语言 Bloom Filter 算法,太值得深挖了
本文探讨了如何利用 Go 语言中的 Bloom Filter 算法提升公司局域网管理系统的性能。Bloom Filter 是一种高效的空间节省型数据结构,适用于快速判断元素是否存在于集合中。文中通过具体代码示例展示了如何在 Go 中实现 Bloom Filter,并应用于局域网的 IP 访问控制,显著提高系统响应速度和安全性。随着网络规模扩大和技术进步,持续优化算法和结合其他安全技术将是企业维持网络竞争力的关键。
24 2
公司局域网管理系统里的 Go 语言 Bloom Filter 算法,太值得深挖了
|
2天前
|
开发框架 前端开发 Go
eino — 基于go语言的大模型应用开发框架(二)
本文介绍了如何使用Eino框架实现一个基本的LLM(大语言模型)应用。Eino中的`ChatModel`接口提供了与不同大模型服务(如OpenAI、Ollama等)交互的统一方式,支持生成完整响应、流式响应和绑定工具等功能。`Generate`方法用于生成完整的模型响应,`Stream`方法以流式方式返回结果,`BindTools`方法为模型绑定工具。此外,还介绍了通过`Option`模式配置模型参数及模板功能,支持基于前端和用户自定义的角色及Prompt。目前主要聚焦于`ChatModel`的`Generate`方法,后续将继续深入学习。
65 6
|
3天前
|
存储 开发框架 Devops
eino — 基于go语言的大模型应用开发框架(一)
Eino 是一个受开源社区优秀LLM应用开发框架(如LangChain和LlamaIndex)启发的Go语言框架,强调简洁性、可扩展性和可靠性。它提供了易于复用的组件、强大的编排框架、简洁明了的API、最佳实践集合及实用的DevOps工具,支持快速构建和部署LLM应用。Eino不仅兼容多种模型库(如OpenAI、Ollama、Ark),还提供详细的官方文档和活跃的社区支持,便于开发者上手使用。
44 6
|
3天前
|
存储 算法 Go
Go语言实战:错误处理和panic_recover之自定义错误类型
本文深入探讨了Go语言中的错误处理和panic/recover机制,涵盖错误处理的基本概念、自定义错误类型的定义、panic和recover的工作原理及应用场景。通过具体代码示例介绍了如何定义自定义错误类型、检查和处理错误值,并使用panic和recover处理运行时错误。文章还讨论了错误处理在实际开发中的应用,如网络编程、文件操作和并发编程,并推荐了一些学习资源。最后展望了未来Go语言在错误处理方面的优化方向。
|
3天前
|
网络协议 算法 安全
Go语言的网络编程与TCP_UDP
Go语言由Google开发,旨在简单、高效和可扩展。本文深入探讨Go语言的网络编程,涵盖TCP/UDP的基本概念、核心算法(如滑动窗口、流量控制等)、最佳实践及应用场景。通过代码示例展示了TCP和UDP的实现,并讨论了其在HTTP、DNS等协议中的应用。最后,总结了Go语言网络编程的未来发展趋势与挑战,推荐了相关工具和资源。
|
6天前
|
缓存 监控 算法
内网监控管理软件:PHP 语言队列算法揭秘
在数字化办公环境中,内网监控管理软件对企业的稳定运行和信息安全至关重要。本文深入介绍PHP中的队列算法及其在内网监控软件中的应用,包括监控数据收集、任务调度和日志记录等场景,通过代码示例展示其实现方法。队列算法可提高性能、保证数据顺序并实现异步处理,为企业提供高效的安全保障。
18 1
|
11天前
|
存储 监控 算法
探秘员工泄密行为防线:基于Go语言的布隆过滤器算法解析
在信息爆炸时代,员工泄密行为对企业构成重大威胁。本文聚焦布隆过滤器(Bloom Filter)这一高效数据结构,结合Go语言实现算法,帮助企业识别和预防泄密风险。通过构建正常操作“指纹库”,实时监测员工操作,快速筛查可疑行为。示例代码展示了如何利用布隆过滤器检测异常操作,并提出优化建议,如调整参数、结合日志分析系统等,全方位筑牢企业信息安全防线,守护核心竞争力。
|
人工智能 算法 Go
使用golang学习算法(1)-排序
前言 终于感觉到算法的重要了。于是打算继续学习下。 其实算法跟语言没有啥关系,用啥语言都可以实现关键是思路,最近正好在学习golang。打算把算法的编写使用golang完成。 没有使用IDE,使用的是sublime2+ golang的插件,然后使用命令行进行编译。 开发效率也不低,也支持语言的自动补齐。 搭建环境【http://blog.csdn.net/freewebsys/a
1081 0
|
2月前
|
存储 监控 算法
员工上网行为监控中的Go语言算法:布隆过滤器的应用
在信息化高速发展的时代,企业上网行为监管至关重要。布隆过滤器作为一种高效、节省空间的概率性数据结构,适用于大规模URL查询与匹配,是实现精准上网行为管理的理想选择。本文探讨了布隆过滤器的原理及其优缺点,并展示了如何使用Go语言实现该算法,以提升企业网络管理效率和安全性。尽管存在误报等局限性,但合理配置下,布隆过滤器为企业提供了经济有效的解决方案。
100 8
员工上网行为监控中的Go语言算法:布隆过滤器的应用

热门文章

最新文章