分享
  1. 首页
  2. 文章

基本排序算法Golang

borey · · 2257 次点击 · · 开始浏览
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

摘要

排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。

冒泡排序

 1 func BubbleSort(vector []int) {
 2 fmt.Println("BubbleSort")
 3  fmt.Println(vector)
 4 for i := 0; i < len(vector); i++ {
 5 tag := true // 为了剪枝
 6 // 每一趟将最大的数冒泡
 7 for j := 0; j < len(vector)-i-1; j++ {
 8 if vector[j] > vector[j+1] { /*vector[j] < vector[j+1]*/
 9 temp := vector[j]
10 vector[j] = vector[j+1]
11 vector[j+1] = temp
12 tag = false
13  }
14  }
15 if tag {
16 break //0~len(vector)-i没有发生交换说明已经有序
17  }
18  fmt.Println(vector)
19  }
20 }

插入排序

 1 func InsertSort(vector []int) {
 2 fmt.Println("InsertSort")
 3  fmt.Println(vector)
 4 for i := 1; i < len(vector); i++ {
 5 // 每一趟不满足条件就选择i为哨兵保存,将哨兵插入0~i-1有序序列(0~i-1始终是有序的)
 6 if vector[i] < vector[i-1] { /*vector[i] > vector[i-1]*/
 7 temp := vector[i]
 8 //后移直到找到哨兵合适的位置
 9 j := i - 1
10 for ; j >= 0 && vector[j] > temp; j-- { /*vector[j] < temp*/
11 vector[j+1] = vector[j]
12  }
13 //插入位置前后都是有序的,最后也是有序的
14 vector[j+1] = temp
15  }
16  fmt.Println(vector)
17  }
18 }

选择排序

 1 func SelectSort(vector []int) {
 2 fmt.Println("SelectSort")
 3  fmt.Println(vector)
 4 for i := 0; i < len(vector); i++ {
 5 // 选择最小的元素
 6 k := i
 7 for j := i + 1; j < len(vector); j++ {
 8 if vector[k] > vector[j] {
 9 k = j
10  }
11  }
12 // 交换
13 if k != i {
14 temp := vector[i]
15 vector[i] = vector[k]
16 vector[k] = temp
17  }
18  fmt.Println(vector)
19  }
20 }

二元选择排序

 1 func BinarySelectSort(vector []int) {
 2 fmt.Println("SelectSort")
 3  fmt.Println(vector)
 4 n := len(vector)
 5 for i := 0; i < n/2; i++ {
 6 // 选择最小的元素和最大元素
 7 k := i
 8 t := n - i - 1
 9 for j := i + 1; j <= n-i-1; j++ {
10 if vector[k] > vector[j] {
11 k = j
12  }
13 if vector[t] < vector[j] {
14 t = j
15  }
16  }
17 // 交换
18 if k != i {
19 temp := vector[i]
20 vector[i] = vector[k]
21 vector[k] = temp
22  }
23 if t != n-i-1 {
24 temp := vector[n-i-1]
25 vector[n-i-1] = vector[t]
26 vector[t] = temp
27  }
28  fmt.Println(vector)
29  }
30 }

快速排序

简单的说快速排序就是挖坑填数然后分治,公认效率最好,这个必须会

 1 func QuickSort(vector []int, low, hight int) {
 2  fmt.Println(vector)
 3 if low < hight {
 4 i := low
 5 j := hight
 6 temp := vector[low] // 开始挖坑填数
 7 for i < j {
 8 for i < j && vector[j] >= temp {
 9 j--
10  }
11 vector[i] = vector[j]
12 for i < j && vector[i] <= temp {
13 i++
14  }
15 vector[j] = vector[i]
16  }
17 vector[i] = temp
18 QuickSort(vector, low, i-1) // 分治
19 QuickSort(vector, i+1, hight)
20  }
21 }

常见问题,已知序列WAUSTHKO,将第一个数作W为基数,问:

1,第一趟后的序列是多少?假设递归同时进行

1),OAUSTHKW

2),KAHOTSUW

3),HAKOSTUW

4),AHKOSTUW

2,排序过程中那些数会被作为选基数?

以上标记的都是:W,O,K、T,H

3,基数的选择直接影响到效率,同时排序末尾显然有效率问题,可以用其他算法替换。

有疑问加站长微信联系(非本文作者)

本文来自:博客园

感谢作者:borey

查看原文:基本排序算法Golang

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

关注微信
2257 次点击
暂无回复
添加一条新回复 (您需要 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传

用户登录

没有账号?注册
或
(追記) (追記ここまで)

今日阅读排行

    加载中
(追記) (追記ここまで)

一周阅读排行

    加载中

关注我

  • 扫码关注领全套学习资料 关注微信公众号
  • 加入 QQ 群:
    • 192706294(已满)
    • 731990104(已满)
    • 798786647(已满)
    • 729884609(已满)
    • 977810755(已满)
    • 815126783(已满)
    • 812540095(已满)
    • 1006366459(已满)
    • 692541889

  • 关注微信公众号
  • 加入微信群:liuxiaoyan-s,备注入群
  • 也欢迎加入知识星球 Go粉丝们(免费)

给该专栏投稿 写篇新文章

每篇文章有总共有 5 次投稿机会

收入到我管理的专栏 新建专栏