Skip to main content

moregeek program

go 语言实现常见排序算法_宇宙之一粟的漂泊之旅的博客-多极客编程

Go  语言实现常见排序算法_i++

计数排序

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

©著作权归作者所有:来自51CTO博客作者宇宙之一粟的原创作品,请联系作者获取转载授权,否则将追究法律责任

prometheus 启动时被禁止的功能特性_耳东-erdong的博客-多极客编程

Prometheus 有一些功能特性在服务启动的时候是默认禁止的,因为这些功能特性是对 Prometheus 有破坏性或是实验性质的,在未来的版本升级中这些特性会发生变化。如果发生了变化,这些变化会在每个版本的发行注记中进行标注和描述。我们在 Prometheus 启动的时候在命令行中使用 ​​--enable-feature​​ 参数来开启这些功能特性,如果实验性的功能特性在验证稳定之后,会在未

【云原生】docker介绍_柒号华仔的博客-多极客编程

作者:柒号华仔 个人主页:欢迎访问我的主页 个人信条:星光不问赶路人,岁月不负有心人。 个人方向:专注于5G领域,同时兼顾其他网络协议,编解码协议,C/C++,linux等,感兴趣的小伙伴可以关注我,一起交流。1. Docker简介1.1 Docker定义Docker 是一个用于开发、发布和运行应用程序的开放平台。Docker 能够将应用程序与基础架构分离,以便快速交付软件。使用 Docker,您

【云原生】devops(八):jenkins集成kubernetes_是dream呀的博客-多极客编程

@TOC 前言: 📢📢📢当下云原生火爆全网,云原生充分利用了云计算弹性、敏捷、资源池和服务化特性,改变云端应用的设计、开发、部署和运行模式,为我们大大提供了便利,本篇文章将带大家走进云原生的世界,揭开它的神秘面纱。💕 入门须知:这片乐园从不缺乏天才,努力才是你的最终入场券!🚀🚀🚀💓最后,愿我们都能在看不到的地方闪闪发光,一起加油进步🍺🍺🍺 一、 Jenkins集成Kubernetes 1.准

9步操作让你的k8s 更安全_mb62f1cd5a97d30的博客-多极客编程

Kubernetes 是一个复杂的平台,需要大量的配置和管理。为了保证 Kubernetes 工作负载的安全,尤其是在生产环境中,您需要通过实施安全最佳实践来解决关键的架构漏洞和平台依赖性。本文将向您介绍K8s 安全实践的9个关键步骤1.启用 K8s 的 RBACRBAC 可以帮助您定义谁有权访问 Kubernetes API 以及他们拥有哪些权限。RBAC 通常在 Kubernetes 1.6

【云原生】kubeadm部署单master集群(contained运行时)_键客李大白的博客-多极客编程

一、部署说明 主机清单 版本说明 contained version:1.6.5 kubeadm version: 1.23.9 kubectl version: 1.23.9 kubelet version: 1.23.9 二、主机初始化 配置/etc/hosts $ cat <<EOF >> /etc/hosts 192.168.2.60 kubeadm-m

kubeedge:下一代云原生边缘设备管理标准dmi的设计与实现_华为云开发者社区的博客-多极客编程

摘要:KubeEdge设备管理架构的设计实现,有效帮助用户处理设备数字孪生进程中遇到的场景。本文分享自华为云社区《​​KubeEdge:下一代云原生边缘设备管理标准DMI的设计与实现​​》。随着5G、AI、分布式云等技术的成熟发展,万物互联、数字孪生、算力泛在等理念不断推进,带来了很多行业业务的创新,越来越多的设备、应用运行在端侧,并产生大量的数据。如何更好地解耦业务应用开发和设备数据访问,为设备

wireguard-跨云or vpc网络通讯方案_对你无可奈何的博客-多极客编程

背景: 早期服务器集中于腾讯云,开始是传统网络。后面是自定义的私有网络vpc.当然了vpc中还有容器网络,容器的网络方案使用了默认的Global Router,并没有使用VPC-CNI的容器网络与云主机网络在同一个 VPC 内的方案(腾讯云官方文档还有了Cilium-Overlay 的方案,恩还有个测试环境的k8s集群是kubeadm自建的集群网络插件用的cilum).今年45月份有些新业务又跑在

工业智能化转型升级难?华为云这三招,加速商业变现_华为云开发者社区的博客-多极客编程

摘要:围绕工业场景,深入了解华为云提供的技术解决方案和场景应用案例,以及华为云云商店提供的商机权益。本文分享自华为云社区《​​工业智能化转型升级难?华为云这三招,加速商业变现​​》,作者:华为云社区精选 。在智能化转型的风口期,以及全球贸易、新冠疫情等外部的冲击影响下,工业企业通过新技术来保持增长态势、实现降本增效显得尤为关键,工业领域的数字化转型进入全面爆发期。比如在电力行业,用高精度的AI算法

分布式系统的磁盘均衡策略_mb60939e30d6d2e的博客-多极客编程

分布式系统设计中的一大挑战,是对磁盘的均衡使用,这在一个全新的集群中,是比较容易实现的。关键问题在于,随着时间的推移,我们需要在集群中不断地新增或者移除设备,在分布式文件存储系统 YRCLoudFile 产品中,我们可能会使用冷热分层策略将文件下刷至对象存储,这些行为都可能会导致集群内的磁盘使用不均,从而产生访问热点、资源利用率低等问题。数据分布算法决定了磁盘均衡的最终效果,一个良好的分布策略,往

免费搭建亚马逊云环境(1)——注册、创建和连接实例_书山有路的博客-多极客编程

一、注册亚马逊云账号1、登录网站:​​https://www.amazonaws.cn/free/?hd_gl_2109​​2、点击页面的创建账号按钮;3、填写相关用户信息;4、等待审核,正常在一天左右;二、创建EC21、审核完成后就可以开始创建实例,选择免费的Red Hat;2、根据默认的选择免费套餐即可;3、默认即可选择下一步;4、这边可以调整默认的存储空间大小,调整到免费最高的30G;5、这

免费搭建亚马逊云环境(2)—— root用户、数据库配置_书山有路的博客-多极客编程

一、切换管理员root账号1、输入命令sudo passwd root  2、提示你输入new password,然后再输入一遍确认3、切换root身份su root4、已经是root用户了可以顺便把vim安装上,输入命令:yum install vim5、使用root身份找到 PasswordAuthentication no,把no改成yes(前面#号也要删掉);​vim /etc/ssh/s

如何在 kubernetes 中使用 yrcloudfile 的 dataload 功能?_mb60939e30d6d2e的博客-多极客编程

Kubernetes 是用于自动部署、扩展和管理容器化应用程序的一个开源的容器编排解决方案。尽管 Kubernetes 最初是为无状态应用程序设计的,但随着有状态工作负载的日益流行,Kubernetes 也可用于管理有状态应用程序。今天我们想要分享的是如何在 Kubernetes 中使用 YRCloudFile 的 DataLoad 功能。当前业内擅长非结构化数据的存储方式主要是文件存储和对象存储