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

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)

}