sort包中实现了3种基本的排序算法:插入排序.快排和堆排序.和其他语言中一样,这三种方式都是不公开的,他们只在sort包内部使用。
所以用户在使用sort包进行排序时无需考虑使用那种排序方式,sort.Interface定义的三个方法:获取数据集合长度的Len()方法、比较两个元素大小的Less()方法和交换两个元素位置的Swap()方法,就可以顺利对数据集合进行排序。sort包会根据实际数据自动选择高效的排序算法。
1 2 3 4 5 6 7 8 | type Interface interface {
Len() int
Less(i, j int) bool
Swap(i, j int)
}
|
登录后复制
任何实现了 sort.Interface 的类型(一般为集合),均可使用该包中的方法进行排序。这些方法要求集合内列出元素的索引为整数。
这里我直接用源码来讲解实现:
1、源码中的例子:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | type Person struct {
Name string
Age int
}
type ByAge []Person
func (a ByAge) Len() int { return len(a) }
func (a ByAge) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }
func Example() {
people := []Person{
{ "Bob" , 31},
{ "John" , 42},
{ "Michael" , 17},
{ "Jenny" , 26},
}
fmt.Println(people)
sort.Sort(ByAge(people))
fmt.Println(people)
}
|
登录后复制
2、Sort(data Interface)方法
1 2 3 4 5 6 7 8 9 10 11 12 | func Sort(data Interface) {
n := data.Len()
maxDepth := 0
for i := n; i > 0; i >>= 1 {
maxDepth++
}
maxDepth *= 2
quickSort(data, 0, n, maxDepth)
}
|
登录后复制
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | func quickSort(data Interface, a, b, maxDepth int) {
for b-a > 12 {
if maxDepth == 0 {
heapSort(data, a, b)
return
}
maxDepth--
mlo, mhi := doPivot(data, a, b)
if mlo-a < b-mhi {
quickSort(data, a, mlo, maxDepth)
a = mhi
} else {
quickSort(data, mhi, b, maxDepth)
b = mlo
}
}
if b-a > 1 {
for i := a + 6; i < b; i++ {
if data.Less(i, i-6) {
data.Swap(i, i-6)
}
}
insertionSort(data, a, b)
}
}
|
登录后复制
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | func heapSort(data Interface, a, b int) {
first := a
lo := 0
hi := b - a
for i := (hi - 1) / 2; i >= 0; i-- {
siftDown(data, i, hi, first)
}
for i := hi - 1; i >= 0; i-- {
data.Swap(first, first+i)
siftDown(data, lo, i, first)
}
}
|
登录后复制
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | func siftDown(data Interface, lo, hi, first int) {
root := lo
for {
child := 2*root + 1
if child >= hi {
break
}
if child+1 < hi && data.Less(first+child, first+child+1) {
child++
}
if !data.Less(first+root, first+child) {
return
}
data.Swap(first+root, first+child)
root = child
}
}
|
登录后复制
更多golang知识请关注golang教程栏目。
以上是golang中sort包如何实现的详细内容。更多信息请关注PHP中文网其他相关文章!