基数排序-Goalng语言

golanguage · · 313 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。
> 由于之前在golang中文社区没有查到radix-sort让我尴尬,就自己给出如下代码,如果不足也请大家指明 ```go import "strconv" func RadixSort(arr []int) []int{ if len(arr)<2{ fmt.Println("NO NEED TO SORT") return arr } maxl:=MaxLen(arr) return RadixCore(arr,0,maxl) } func RadixCore(arr []int,digit,maxl int) []int{ //核心排序机制时间复杂度 O( d( r+n ) ) if digit>=maxl{ return arr //排序稳定 } radix:=10 count:=make([]int,radix) bucket:=make([]int,len(arr)) for i:=0;i<len(arr);i++{ count[GetDigit(arr[i],digit)]++ } for i:=1;i<radix;i++{ count[i]+=count[i-1] } for i:=len(arr)-1;i>=0;i--{ d:=GetDigit(arr[i],digit) bucket[count[d]-1]=arr[i] count[d]-- } return RadixCore(bucket,digit+1,maxl) } func GetDigit(x,d int) int{ //获取某位上的数字 a:=[]int{1,10,100,1000,10000,100000,1000000} return (x/a[d])%10 } func MaxLen(arr []int) int{ //获取最大位数 var maxl,curl int for i:=0;i<len(arr);i++{ curl=len(strconv.Itoa(arr[i])) if curl>maxl{ maxl=curl } } return maxl } ``` 这是LSD法(排序稳定),即从最低位开始比较哦,还有一种从最高位开始比较法MSD(排序不稳定).
313 次点击  
加入收藏 微博
2 回复  |  直到 2018-05-17 17:02:11
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传