Go |
您所在的位置：网站首页 › sort(reverse) › Go |
Go
sort 包主要用来实现排序相关的操作，它实现了四种基本的排序算法：插入排序（insertionSort）、归并排序（symMerge）、堆排序（heapSort）和快速排序（quickSort）；sort 包会依据实际数据自动选择最优的排序算法。 1. sort.Interface 接口如果某个 struct 需要排序，则必须实现 sort.Interface 接口，提供 Len、Less、Swap 三个方法的实现，然后调用 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) }假设我们需要对 []int 切片中的元素进行排序，其实现代码如下： 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] } func main(){ nums := []int{2, 31, 5, 6, 3} sort.Sort(IntSlice(nums)) fmt.Println("intSort:", nums) // [2,3,5,6,31] }其实，上述示例代码中定义的 IntSlice 就是 sort 包中已经提供好的内容，该包中还提供了 Float64Slice、StringSlice。如下图：  所以，我们在对 int、string、float64 的切片进行排序时就不需要再包装和实现 Interface 接口了，直接调用即可，示例如下： // []int排序 nums := []int{2, 31, 5, 6, 3} sort.Sort(sort.IntSlice(nums)) // []string字符串排序 names := []string{"abc", "12", "kk", "Jordan", "Ko", "DD"} sort.Sort(sort.StringSlice(nums))此外，sort 包中还提供了 Ints、Float64s、Strings 函数，其定义如下：  所以，我们的排序代码还可以简化，如下： // []int排序 nums := []int{2, 31, 5, 6, 3} sort.Ints(nums) // []string字符串排序 names := []string{"abc", "12", "kk", "Jordan", "Ko", "DD"} sort.Strings(nums) 2. sort.Reverse 逆向排序如果需要逆向排序，则需要先使用 sort.Reverse 进行包装，获取 sort.Reverse 指针，然后再调用 sort.Sort() ，示例如下： // []int排序 nums := []int{2, 31, 5, 6, 3} sort.Sort(sort.Reverse(sort.IntSlice(nums))) fmt.Println(nums) //[31 6 5 3 2]sort.Reverse(a) 接收的参数是实现了 sort.Interface 的数据。它只是标识需要逆序，并不执行排序操作，排序操作还是需要 sort.Sort() 来实现。 3. sort.Stable 稳定排序3.1. 稳定排序的概念数组 arr 中有若干元素，其中 A 元素和 B 元素相等，并且 A 元素在 B 元素前面，如果使用某种排序算法之后，能够保证 A 元素依旧在 B 元素的前面，则认为该算法是稳定的。  3.2. 稳定排序意义如果一组数据只需要一次排序，则稳定性一般是没有意义的，如果一组数据需要多次排序，则稳定性是有意义的。 例如，要排序的内容是一组商品对象，第一次排序按照价格由低到高排序，第二次排序按照销量由高到低排序。如果第二次排序使用稳定性算法，就可以使得相同销量的对象依旧保持着价格高低的顺序展现，只有销量不同的对象才需要重新排序。这样既可以保持第一次排序的原有意义，而且可以减少系统开销。  上图中，第一次根据价格排序时，华为 Mate30 在华为 P30 的前面，第二次根据销量排序后，华为 Mate30 依旧在华为 P30 前面，所以，这两次排序使用了稳定排序 3.3. 常见排序算法的稳定性稳定排序：冒泡排序、插入排序、归并排序不稳定排序：选择排序、希尔排序、快速排序3.4. sort.Stable 的使用package sortTest import ( "fmt" "sort" ) type person struct { Name string Age int Score int } type personSort struct { persons []person // 接收函数类型的参数，这样会比较灵活， less func(x, y person) bool } var pSlice = []person{ { Name: "A", Age: 55, Score: 90, }, { Name: "B", Age: 22, Score: 80, }, { Name: "C", Age: 40, Score: 50, }, { Name: "D", Age: 22, Score: 80, }, { Name: "E", Age: 11, Score: 60, }, } // 让 personSlice 实现 sort.Interface 接口 func (p personSort) Len() int { return len(p.persons) } func (p personSort) Less(a, b int) bool { return p.less(p.persons[a], p.persons[b]) } func (p personSort) Swap(i, j int) { p.persons[i], p.persons[j] = p.persons[j], p.persons[i] } func StableSortTest() { // 根据年龄排序 personAgeSort := personSort{ persons: pSlice, less: func(x, y person) bool { return x.Age < y.Age }, } sort.Stable(personAgeSort) // [{E 11 60} {B 22 80} {D 22 80} {C 40 50} {A 55 90}] fmt.Printf("StableSort1: %v \n", personAgeSort.persons) // 根据得分排序 personScoreSort := personSort{ persons: pSlice, less: func(x, y person) bool { return x.Score < y.Score }, } sort.Stable(personScoreSort) //[{C 40 50} {E 11 60} {B 22 80} {D 22 80} {A 55 90}] fmt.Printf("StableSort2: %v \n", personScoreSort.persons) // 先根据年龄排序，再根据得分排序,最后根据姓名排序 mixtureSort := personSort{ persons: pSlice, less: func(x, y person) bool { if x.Age != y.Age { return x.Age < y.Age } if x.Score != y.Score { return x.Score < y.Score } return x.Name < y.Name }, } sort.Stable(mixtureSort) fmt.Printf("StableSort2: %v \n", personScoreSort.persons) }上述代码中，我们定义了一个 personSort 结构体，它有两个成员变量，一个是 person 切片，一个是函数类型的 less 。personSort 实现了 sort.Interface 接口，所以可以对 personSort 中的内容进行排序。 在排序时，Less 条件由 personSort 的成员 less 决定，这样我们就可以根据实际需要动态的定义排序条件。 4. sort.IsSort 是否有序sort.Sort(a) 函数只用来判断 a 是否有序，并不执行排序操作，其定义如下： // IsSorted reports whether data is sorted. func IsSorted(data Interface) bool { n := data.Len() for i := n - 1; i > 0; i-- { if data.Less(i, i-1) { return false } } return true } |
【本文地址】
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |