golang sort 包使用,及三个简单排序算法冒泡,插入,选择 练习

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

sort 包的核心类型是 sort.Interface:

type Interface interface {    
    // Len is the number of elements in the collection.
    Len() int
    // Less reports whether the element with
    // index i should sort before the element with index j.
    Less(i, j int) bool
    // Swap swaps the elements with indexes i and j.
    Swap(i, j int)
}

接口 是golang 的很cool 的特性,rob pike 说接口有点类似uinx pipe,把不同的代码片段连接在一起,这个契约就是接口规范,

提供了指定的功能集合,不管你的内部实现。var  s  sort.Interface,  s 是抽象的接口类型, 具体类型u只要提供了 Len(), Less(),  Swap(),       s = u,  就可以把 u 型变量赋值s, 还体现在 函数函数 是 s, 返回值是s 的地方。

sort.Ints,  sort.Float64s, sort.Strings, 都是库方便的包装,如 sort.Ints 是这样实现的:

func Ints(a []int) { Sort(IntSlice(a)) }
type IntSlice []int   	   
func (p IntSlice) Len() int           { return len(p) }   
func (p IntSlice) Less(i, j int) bool { return p[i] < p[j] }   
func (p IntSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] } 

内部调用 sort.Sort(), 函数的参数是抽象的sort.Interface 类型,[]int 类型没有实现Len(), Less(), Swap() , 而它的别名类型

IntSlice 实现了, 所以 IntSlice(a), 类型转换,以满足接口。对于反序排序有一个巧妙的接口运用:

type reverse struct {   Interface   }

func (r reverse) Less(i, j int) bool {

return r.Interface.Less(j, i)

}

func Reverse(data Interface) Interface {

return &reverse{data}

}

golang语言规范如下描述:

Given a struct type S and a type named T, promoted methods are included in the method set of the struct as follows:

  • If S contains an anonymous field T, the method sets of S and *S both include promoted methods with receiver T. The method set of *S also includes promoted methods with receiver *T.

The method set of an interface type is its interface。

reverse struct 类型 是S, Interface 是T,  reverse 包含匿名字段 Interface, Interface 是接口类型,它的方法集是自己, Len(), Swap(), Less() 被提升到 reverse上, 而reverse又定义的自己的Less()(内部引用被嵌入字段的实现,翻转比较),    reverse 类型拥有了老的len(),swap() 实现,新的less() 实现,所以满足 sort.Interface, reverse 的指针类型包含reverse的方法集,所以

导出函数Reverse() 返回 reverse 指针来满足 Interface接口。

package main
import (
    "fmt"
    "sort"
)
func  bubbleSort(data  sort.Interface){
    r := data.Len()-1
    for i := 0; i < r ; i++{
        for j := r; j > i; j--{
            if data.Less(j, j-1){
                data.Swap(j, j-1)
            }
        }
    }
}
func insertSort(data sort.Interface){
    r := data.Len()-1
    for i := 1; i <= r; i++{
        for j := i; j > 0 && data.Less(j, j-1); j--{
            data.Swap(j, j-1)
        }
    }
}
func  selectSort(data sort.Interface){
    r := data.Len()-1
    for i := 0; i < r; i++{
        min := i
        for j:= i+1; j <= r; j++ {
            if data.Less(j, min) {  min = j }
        }
        data.Swap(i, min)
    }
}
func main(){
    nums := []int{120,33,44,1,23,90,87,13,57,43,42}
    //标准库qsort 正序(实际上是qsort结合heapsort,insertsort)
    sort.Ints(nums)
    fmt.Println(nums)
    //反序qsort
    sort.Sort(sort.Reverse(sort.IntSlice(nums)))
    fmt.Println(nums)
    //正序bubble 
    bubbleSort(sort.IntSlice(nums))
    fmt.Println(nums)
    //反序bubble
    bubbleSort(sort.Reverse(sort.IntSlice(nums)))
    fmt.Println(nums)
    //正序insert
    insertSort(sort.IntSlice(nums))
    fmt.Println(nums)
    //反序inert
    insertSort(sort.Reverse(sort.IntSlice(nums)))
    fmt.Println(nums)
    //正序select
    selectSort(sort.IntSlice(nums))
    fmt.Println(nums) 
    //反序select 
    selectSort(sort.Reverse(sort.IntSlice(nums)))
    fmt.Println(nums)

}




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

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

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