GO语言学习笔记6-Sort的使用
2011 年 9 月 9 日
GoLang标准库的sort包提供了排序切片和用户自定义数据集以及相关功能的函数。
Sort操作的对象通常是一个slice,需要满足三个基本的接口,并且能够使用整数来索引。
Sort操作的对象通常是一个slice,需要满足三个基本的接口,并且能够使用整数来索引。
1.sort实现原理
Sort排序的函数原型如下所示:
(1)Sort
// It makes one call to data.Len to determine n, and O(n*log(n)) calls to // data.Less and data.Swap. The sort is not guaranteed to be stable. func Sort(data Interface) { n := data.Len() quickSort(data, 0, n, maxDepth(n)) }
(2) interface
// A type, typically a collection, that satisfies sort.Interface can be // sorted by the routines in this package. The methods require that the // elements of the collection be enumerated by an integer index. 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) }
(3) quickSort
func quickSort(data Interface, a, b, maxDepth int) { for b-a > 12 { // Use ShellSort for slices <= 12 elements if maxDepth == 0 { heapSort(data, a, b) return } maxDepth-- mlo, mhi := doPivot(data, a, b) // Avoiding recursion on the larger subproblem guarantees // a stack depth of at most lg(b-a). if mlo-a 1 { // Do ShellSort pass with gap 6 // It could be written in this simplified form cause b-a <= 12 for i := a + 6; i < b; i++ { if data.Less(i, i-6) { data.Swap(i, i-6) } } insertionSort(data, a, b) } }
2.Sort内部 []int排序
type IntSlice []int // 获取此 slice 的长度 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 is a convenience method. func (p IntSlice) Sort() { Sort(p) }
3.代码实现
Olymic Game
这道题采用Sort排序的实现方法如下:
package main import ( "fmt" "sort" "strings" ) type MedalNum struct { name string gold int silver int bronze int } type MedalNumList []MedalNum func (m MedalNumList) Len() int { return len(m) } // 奖牌数降序,国家名称字典序 func (m MedalNumList) Less(i, j int) bool { if m[i].gold > m[j].gold { return true } else if m[i].gold == m[j].gold { if m[i].silver > m[j].silver { return true } else if m[i].silver == m[j].silver { if m[i].bronze > m[j].bronze { return true } else if m[i].bronze == m[j].bronze { if strings.Compare(m[i].name, m[j].name) < 0 { return true } } } } return false } func (m MedalNumList) Swap(i, j int) { m[i], m[j] = m[j], m[i] } func main() { var n int _, _ = fmt.Scan(&n) var medal MedalNumList var nameI string var goldI, sliverI, bronzeI int i := 0 for { if i == n { break } _, err := fmt.Scanln(&nameI, &goldI, &sliverI, &bronzeI); if err != nil { break } else { medal = append(medal, MedalNum{name:nameI, gold:goldI, silver:sliverI, bronze:bronzeI}) } i++ } sort.Sort(medal) for _, m := range medal { fmt.Println(m.name) } }
Compare是字符串比较函数,函数原型如下所示:
// Compare returns an integer comparing two strings lexicographically. // The result will be 0 if a==b, -1 if a b. func Compare(a, b string) int { if a == b { return 0 } if a < b { return -1 } return +1 }