模仿 Go Sort 排序接口实现的自定义排序

Go 语言对于类型的要求非常严格,导致我们无法声明一个 interface 类型的切片对其排序。所以这里模仿 Go 的 sort 排序扩展包,实现对某个特定类型排序的方法。

查看完整代码,点击这里

Interface 接口

若要实现一个自定义的排序,就要实现 sort 包的排序接口。要排序的集合必须包含一个数字类型的索引,所以待排序的数据类型只能是数组或者切片。

// 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)
}

自定义排序的结构体

我们将对所有的学生进行排序,学生包含他的姓名以及成绩,排序的规则是按照学习的成绩排序。

type Student struct {
 Name string
 Score int
}
type Students []Student

实现排序的接口

func (s Students) Len() int {
 return len(s)
}
// 在比较的方法中,定义排序的规则
func (s Students) Less(i, j int) bool {
 if s[i].Score < s[j].Score {
 return true
 } else if s[i].Score > s[j].Score {
 return false
 } else {
 return s[i].Name < s[i].Name
 }
}
func (s Students) Swap(i, j int) {
 temp := s[i]
 s[i] = s[j]
 s[j] = temp
}

实现排序逻辑

Go 提供了基于快排实现的排序方法,这里为了体验为什么 Go 这么定义 Interface 接口,我使用了选择排序的方法代替 Go 的快排。

func Sort(s sort.Interface) {
 length := s.Len()
 for i := 0; i < length; i++ {
 minIndex := i
 for j := i + 1; j < length; j++ {
 if s.Less(j, i) {
 minIndex = j
 }
 }
 s.Swap(minIndex, i)
 }
}

在这个排序中,我使用了接口中定义的三个方法: Len(),Less(),Swap()。最重要的还是 Less(),没有它程序就不知道如何去比较两个未知元素的大小。

重写输出

为了更好的输出学生的信息,重写学生的字符串输出格式

func (s Student) String() string {
 return fmt.Sprintf("Student: %s %v", s.Name, s.Score)
}

测试输出

通过以下程序测试我们的排序算法

func main() {
 arr := []int{10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
 SelectionSort(arr, len(arr))
 fmt.Println(arr)
 students := student.Students{}
 students = append(students, student.Student{"D", 90})
 students = append(students, student.Student{"C", 100})
 students = append(students, student.Student{"B", 95})
 students = append(students, student.Student{"A", 95})
 Sort(students)
 for _, student := range students {
 fmt.Println(student)
 }
}

以下是输出结果:

[1 2 3 4 5 6 7 8 9 10]
Student: D 90
Student: A 95
Student: B 95
Student: C 100

本文来自:Segmentfault

感谢作者:Donne

查看原文:模仿 Go Sort 排序接口实现的自定义排序

• 编辑
• 预览