当前位置:首页 > Golang杂记 > 正文内容

Go常用排序算法

2年前 (2020-10-24)Golang杂记972

常用的排序算法各种语言相同,这里大致介绍下go的常用排序,废话不多说,直入正题:

冒泡排序

package main

import (
   "fmt"
)

func bubbleSort(slice []int) []int {
   for n := 0; n <= len(slice); n++ {
      for i := 1; i < len(slice)-n; i++ {
         if slice[i] < slice[i-1] {
            slice[i], slice[i-1] = slice[i-1], slice[i]
         }
      }
   }
   return slice
}

func main() {
   var arr = [...]int{99, 51, 41, 2, 31}
   var rarr = bubbleSort(arr[:])
   fmt.Println(rarr) // 从小到大[2 31 41 51 99]
}

比较排序

package main

import (
   "fmt"
)

func selectionSort(slice []int) []int {
   for n := 0; n <= len(slice); n++ {
      for i := n + 1; i < len(slice); i++ {
         if slice[n] > slice[i] {
            slice[n], slice[i] = slice[i], slice[n]
         }
      }
   }
   return slice
}

func main() {
   var arr = [...]int{99, 51, 41, 2, 31}
   var rarr = selectionSort(arr[:])
   fmt.Println(rarr)
}

插入排序

    思路:将数组拆分为一个有序的,一个无序的。初始时下标0永远为有序数组。

    建立循环,从下标1开始到数组的长度,每个都与前一个进行对比,如果比前一个值小,就互相换位,当当前值比上一个值大时,说明当前值之前都是已经排序好的数组。就退出。

    例子:如该数组[...]int{10, 56, 4, 654, 8, 997},

    第一次循环时,n=1 i=1 56 > 10跳出。

    第二次循环时,{10, 56, 4, 654, 8, 997} n=2 i=n=2, 4<56互换,值为{10, 4, 56, 654, 8, 997},内部循环继续进行,i=1 4<10互换为[4 10 56 654 8 997]。内部循环结束,条件为i<0 

package main

import (
   "fmt"
)

func insertSort(arr []int) {
   for n := 1; n < len(arr); n++ {
      for i := n; i > 0; i-- {
         if arr[i] > arr[i-1] {
            break
         }
         arr[i], arr[i-1] = arr[i-1], arr[i]
      }
   }
}

func main() {
   var array = [...]int{10, 56, 4, 654, 8, 997}
   insertSort(array[:])

   fmt.Println(array)
}

快速排序

思路:以一个基准数将数组拆分为两个,一边大于这个数,一边小于这个数。从数组第0个开始,首先先记录此基准数的下标和值  {312, 84, 543, 5, 100, 23} ,k=0 v=312。需要传入一个从哪里开始到哪里的位置。这里基准数为第一个,顾循环位置就从0+1开始 循环完之后为 84 84 543 5 100 23 。

package main

import (
   "fmt"
)

func qsort(arr []int, start int, end int) {
   if start >= end {
      return
   }

   key := start
   value := arr[start] //记录当前基准值位置
   for n := start + 1; n <= end; n++ {
      // a[n] < arr[start]
      if arr[n] < value {
         arr[key] = arr[n]   //就将a[n]挪至arr[key]所在位置
         arr[n] = arr[key+1] //a[n]空缺了,将arr[key]向后移动一位
         // 理论上现在值为这个 {84, 84, 543, 5, 100, 23}
         key++ //key的位置改变了1位,key++
         //最后在将进位后的arr[key] = 之前保存的value即为
         // value=321 {84, 312, 543, 5, 100, 23}
         //这样完成了替换
      }
   }

   arr[key] = value
   //一轮循环后该数组为[84 5 100 23 312 543]
   //将基准数两边的数进行进行排序 此时 key=3 start=0 左边为 start-key-1
   qsort(arr, start, key-1)
   qsort(arr, key+1, end) //右边为key+1-end
}

func main() {
   var array = [...]int{312, 84, 543, 5, 100, 23}
   qsort(array[:], 0, len(array)-1)
   fmt.Println(array)
}
//输出[5 23 84 100 312 543]

排序思路算法几乎一样。十大经典排序算法暂时就介绍这几种了。

    扫描二维码推送至手机访问。

    版权声明:本文由周伯通的博客发布,如需转载请注明出处。

    本文链接:https://www.zhoubotong.site/post/6.html

    分享给朋友:

    相关文章

    go协程全局变量和局部变量

    大家可能经常会用到类似如下代码片段:package main import (    "fmt"   ...

    关于go协程同步的几种方法

    这里咋们简要介绍下关于go中协程的几种同步方法。先说下概念性的:协程概念简要理解协程有点类似线程,是一种更为轻量级的调度单位,但协程还是不同于线程的,线程是系统级实现的,常见的调度方法是时间片轮转法,...

    Go channel 协程为什么是安全的

        Channel跟java/php的 thread不一样,首先channel是协程不是线程。channel不会产生新的线程,自然不会涉及到新的进程或者线程...

    NewReplacer使用技巧

            上次写博客至今有段时间了,这些日子,认真过,努力过,职场中不管有哪些让人失意或不快的事,终归到底,是自己...

    Go easyjson使用技巧

    Go easyjson使用技巧

    如果使用go语言自带的json库,使用的是反射,而go语言中反射性能较低。easyjson就是一个比较好的替代方案。esayjson安装(https://gitcode.net/mirrors/mai...

    发表评论

    访客

    看不清,换一张

    ◎欢迎参与讨论,请在这里发表您的看法和观点。