排序算法 | sort

• import "sort"

• 概况

• 索引

• 例子

概况

程序包排序为排序切片和用户定义的集合提供原语。

例

package main

import (
	"fmt"
	"sort"
)

type Person struct {
	Name string
	Age  int
}

func (p Person) String() string {
	return fmt.Sprintf("%s: %d", p.Name, p.Age)
}

// ByAge implements sort.Interface for []Person based on
// the Age field.
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 main() {
	people := []Person{
		{"Bob", 31},
		{"John", 42},
		{"Michael", 17},
		{"Jenny", 26},
	}

	fmt.Println(people)
	sort.Sort(ByAge(people))
	fmt.Println(people)

}

示例（SortKeys）

ExampleSortKeys 演示了一种使用可编程排序标准对结构类型进行排序的技术。

package main

import (
	"fmt"
	"sort"
)

// A couple of type definitions to make the units clear.
type earthMass float64
type au float64

// A Planet defines the properties of a solar system object.
type Planet struct {
	name     string
	mass     earthMass
	distance au
}

// By is the type of a "less" function that defines the ordering of its Planet arguments.
type By func(p1, p2 *Planet) bool

// Sort is a method on the function type, By, that sorts the argument slice according to the function.
func (by By) Sort(planets []Planet) {
	ps := &planetSorter{
		planets: planets,
		by:      by, // The Sort method's receiver is the function (closure) that defines the sort order.
	}
	sort.Sort(ps)
}

// planetSorter joins a By function and a slice of Planets to be sorted.
type planetSorter struct {
	planets []Planet
	by      func(p1, p2 *Planet) bool // Closure used in the Less method.
}

// Len is part of sort.Interface.
func (s *planetSorter) Len() int {
	return len(s.planets)
}

// Swap is part of sort.Interface.
func (s *planetSorter) Swap(i, j int) {
	s.planets[i], s.planets[j] = s.planets[j], s.planets[i]
}

// Less is part of sort.Interface. It is implemented by calling the "by" closure in the sorter.
func (s *planetSorter) Less(i, j int) bool {
	return s.by(&s.planets[i], &s.planets[j])
}

var planets = []Planet{
	{"Mercury", 0.055, 0.4},
	{"Venus", 0.815, 0.7},
	{"Earth", 1.0, 1.0},
	{"Mars", 0.107, 1.5},
}

// ExampleSortKeys demonstrates a technique for sorting a struct type using programmable sort criteria.
func main() {
	// Closures that order the Planet structure.
	name := func(p1, p2 *Planet) bool {
		return p1.name < p2.name
	}
	mass := func(p1, p2 *Planet) bool {
		return p1.mass < p2.mass
	}
	distance := func(p1, p2 *Planet) bool {
		return p1.distance < p2.distance
	}
	decreasingDistance := func(p1, p2 *Planet) bool {
		return !distance(p1, p2)
	}

	// Sort the planets by the various criteria.
	By(name).Sort(planets)
	fmt.Println("By name:", planets)

	By(mass).Sort(planets)
	fmt.Println("By mass:", planets)

	By(distance).Sort(planets)
	fmt.Println("By distance:", planets)

	By(decreasingDistance).Sort(planets)
	fmt.Println("By decreasing distance:", planets)

}

示例（SortMultiKeys）

ExampleMultiKeys 演示了一种技术，用于在比较中使用不同组的多个字段对结构类型进行排序。我们将“较少”功能链接在一起，每个功能都比较一个字段。

package main

import (
	"fmt"
	"sort"
)

// A Change is a record of source code changes, recording user, language, and delta size.
type Change struct {
	user     string
	language string
	lines    int
}

type lessFunc func(p1, p2 *Change) bool

// multiSorter implements the Sort interface, sorting the changes within.
type multiSorter struct {
	changes []Change
	less    []lessFunc
}

// Sort sorts the argument slice according to the less functions passed to OrderedBy.
func (ms *multiSorter) Sort(changes []Change) {
	ms.changes = changes
	sort.Sort(ms)
}

// OrderedBy returns a Sorter that sorts using the less functions, in order.
// Call its Sort method to sort the data.
func OrderedBy(less ...lessFunc) *multiSorter {
	return &multiSorter{
		less: less,
	}
}

// Len is part of sort.Interface.
func (ms *multiSorter) Len() int {
	return len(ms.changes)
}

// Swap is part of sort.Interface.
func (ms *multiSorter) Swap(i, j int) {
	ms.changes[i], ms.changes[j] = ms.changes[j], ms.changes[i]
}

// Less is part of sort.Interface. It is implemented by looping along the
// less functions until it finds a comparison that is either Less or
// !Less. Note that it can call the less functions twice per call. We
// could change the functions to return -1, 0, 1 and reduce the
// number of calls for greater efficiency: an exercise for the reader.
func (ms *multiSorter) Less(i, j int) bool {
	p, q := &ms.changes[i], &ms.changes[j]
	// Try all but the last comparison.
	var k int
	for k = 0; k < len(ms.less)-1; k++ {
		less := ms.less[k]
		switch {
		case less(p, q):
			// p < q, so we have a decision.
			return true
		case less(q, p):
			// p > q, so we have a decision.
			return false
		}
		// p == q; try the next comparison.
	}
	// All comparisons to here said "equal", so just return whatever
	// the final comparison reports.
	return ms.less[k](p, q)
}

var changes = []Change{
	{"gri", "Go", 100},
	{"ken", "C", 150},
	{"glenda", "Go", 200},
	{"rsc", "Go", 200},
	{"r", "Go", 100},
	{"ken", "Go", 200},
	{"dmr", "C", 100},
	{"r", "C", 150},
	{"gri", "Smalltalk", 80},
}

// ExampleMultiKeys demonstrates a technique for sorting a struct type using different
// sets of multiple fields in the comparison. We chain together "Less" functions, each of
// which compares a single field.
func main() {
	// Closures that order the Change structure.
	user := func(c1, c2 *Change) bool {
		return c1.user < c2.user
	}
	language := func(c1, c2 *Change) bool {
		return c1.language < c2.language
	}
	increasingLines := func(c1, c2 *Change) bool {
		return c1.lines < c2.lines
	}
	decreasingLines := func(c1, c2 *Change) bool {
		return c1.lines > c2.lines // Note: > orders downwards.
	}

	// Simple use: Sort by user.
	OrderedBy(user).Sort(changes)
	fmt.Println("By user:", changes)

	// More examples.
	OrderedBy(user, increasingLines).Sort(changes)
	fmt.Println("By user,<lines:", changes)

	OrderedBy(user, decreasingLines).Sort(changes)
	fmt.Println("By user,>lines:", changes)

	OrderedBy(language, increasingLines).Sort(changes)
	fmt.Println("By language,<lines:", changes)

	OrderedBy(language, increasingLines, user).Sort(changes)
	fmt.Println("By language,<lines,user:", changes)

}

示例（SortWrapper）

package main

import (
	"fmt"
	"sort"
)

type Grams int

func (g Grams) String() string { return fmt.Sprintf("%dg", int(g)) }

type Organ struct {
	Name   string
	Weight Grams
}

type Organs []*Organ

func (s Organs) Len() int      { return len(s) }
func (s Organs) Swap(i, j int) { s[i], s[j] = s[j], s[i] }

// ByName implements sort.Interface by providing Less and using the Len and
// Swap methods of the embedded Organs value.
type ByName struct{ Organs }

func (s ByName) Less(i, j int) bool { return s.Organs[i].Name < s.Organs[j].Name }

// ByWeight implements sort.Interface by providing Less and using the Len and
// Swap methods of the embedded Organs value.
type ByWeight struct{ Organs }

func (s ByWeight) Less(i, j int) bool { return s.Organs[i].Weight < s.Organs[j].Weight }

func main() {
	s := []*Organ{
		{"brain", 1340},
		{"heart", 290},
		{"liver", 1494},
		{"pancreas", 131},
		{"prostate", 62},
		{"spleen", 162},
	}

	sort.Sort(ByWeight{s})
	fmt.Println("Organs by weight:")
	printOrgans(s)

	sort.Sort(ByName{s})
	fmt.Println("Organs by name:")
	printOrgans(s)

}

func printOrgans(s []*Organ) {
	for _, o := range s {
		fmt.Printf("%-8s (%v)\n", o.Name, o.Weight)
	}
}

索引

• func Float64s(a []float64)

• func Float64sAreSorted(a []float64) bool

• func Ints(a []int)

• func IntsAreSorted(a []int) bool

• func IsSorted(data Interface) bool

• func Search(n int, f func(int) bool) int

• func SearchFloat64s(a []float64, x float64) int

• func SearchInts(a []int, x int) int

• func SearchStrings(a []string, x string) int

• func Slice(slice interface{}, less func(i, j int) bool)

• func SliceIsSorted(slice interface{}, less func(i, j int) bool) bool

• func SliceStable(slice interface{}, less func(i, j int) bool)

• func Sort(data Interface)

• func Stable(data Interface)

• func Strings(a []string)

• func StringsAreSorted(a []string) bool

• type Float64Slice

• func (p Float64Slice) Len() int

• func (p Float64Slice) Less(i, j int) bool

• func (p Float64Slice) Search(x float64) int

• func (p Float64Slice) Sort()

• func (p Float64Slice) Swap(i, j int)

• type IntSlice

• func (p IntSlice) Len() int

• func (p IntSlice) Less(i, j int) bool

• func (p IntSlice) Search(x int) int

• func (p IntSlice) Sort()

• func (p IntSlice) Swap(i, j int)

• type Interface

• func Reverse(data Interface) Interface

• type StringSlice

• func (p StringSlice) Len() int

• func (p StringSlice) Less(i, j int) bool

• func (p StringSlice) Search(x string) int

• func (p StringSlice) Sort()

• func (p StringSlice) Swap(i, j int)

例子

Package

Ints

反向搜索搜索（DescendingOrder）

SliceStable

字符串包（SortKeys）

包（SortMultiKeys）

包（SortWrapper）

包文件

search.go sort.go zfuncversion.go

func Float64sSource

func Float64s(a []float64)

Float64 以递增顺序对一片 float64 进行排序（非数字值被视为小于其他值）。

func Float64sAreSortedSource

func Float64sAreSorted(a []float64) bool

Float64sAreSorted 测试是否按增量顺序对一段 float64 进行排序（非数字值被视为小于其他值）。

func IntsSource

func Ints(a []int)

Ints 按递增顺序排序一部分整数。

例

package main

import (
	"fmt"
	"sort"
)

func main() {
	s := []int{5, 2, 6, 3, 1, 4} // unsorted
	sort.Ints(s)
	fmt.Println(s)
}

func IntsAreSortedSource

func IntsAreSorted(a []int) bool

IntsAreSorted 测试是否按升序对整片进行排序。

func IsSortedSource

func IsSorted(data Interface) bool

IsSorted 报告数据是否被排序。

func SearchSource

func Search(n int, f func(int) bool) int

假设在 [0，n），f（i）== true 的范围内，Search 使用二进制搜索来查找并返回 f（i）为真的 [0，n）中的最小索引 i，意味着 f（i + 1）== true 。也就是说，搜索要求 f 对于输入范围 [0，n）的某些（可能为空）前缀为假，对于（可能为空）余数为真; 搜索返回第一个真正的索引。如果没有这样的索引，Search 返回 n 。（请注意，“未找到”返回值不是-1，例如 strings.Index 。）仅在 i [0，n] 范围内搜索调用 f（i）。

Search 的一个常见用途是在排序的，可索引的数据结构（如数组或片段）中为值 x 找到索引 i 。在这种情况下，参数 f（通常是闭包）捕获要搜索的值，以及数据结构如何编制索引和排序。

例如，给定按升序排序的片数据，调用 Search（len（data），func（i int）bool { return datai> = 23}）返回最小的索引 i，使得 datai> = 23。如果调用者要查找23是否在分片中，它必须分别测试 datai == 23。

搜索按降序排序的数据将使用<=运算符而不是> =运算符。

为了完成上面的例子，下面的代码试图在一个整数片数据中按升序排序找到值 x：

x := 23
i := sort.Search(len(data), func(i int) bool { return data[i] >= x })
if i < len(data) && data[i] == x {
	// x is present at data[i]
} else {
	// x is not present in data,
	// but i is the index where it would be inserted.
}

作为一个更奇特的例子，这个程序猜测你的号码：

func GuessingGame() {
	var s string
	fmt.Printf("Pick an integer from 0 to 100.\n")
	answer := sort.Search(100, func(i int) bool {
		fmt.Printf("Is your number <= %d? ", i)
		fmt.Scanf("%s", &s)
		return s != "" && s[0] == 'y'
	})
	fmt.Printf("Your number is %d.\n", answer)
}

例

此示例演示如何搜索按升序排序的列表。

package main

import (
	"fmt"
	"sort"
)

func main() {
	a := []int{1, 3, 6, 10, 15, 21, 28, 36, 45, 55}
	x := 6

	i := sort.Search(len(a), func(i int) bool { return a[i] >= x })
	if i < len(a) && a[i] == x {
		fmt.Printf("found %d at index %d in %v\n", x, i, a)
	} else {
		fmt.Printf("%d not found in %v\n", x, a)
	}
}

示例（降序）

此示例演示搜索按降序排列的列表。该方法与按升序搜索列表相同，但条件反转。

package main

import (
	"fmt"
	"sort"
)

func main() {
	a := []int{55, 45, 36, 28, 21, 15, 10, 6, 3, 1}
	x := 6

	i := sort.Search(len(a), func(i int) bool { return a[i] <= x })
	if i < len(a) && a[i] == x {
		fmt.Printf("found %d at index %d in %v\n", x, i, a)
	} else {
		fmt.Printf("%d not found in %v\n", x, a)
	}
}

func SearchFloat64sSource

func SearchFloat64s(a []float64, x float64) int

SearchFloat64s 在已排序的 float64s 片段中搜索 x，并返回 Search 所指定的索引。如果 x 不存在（它可能是len（a）），则返回值是插入x的索引。切片必须按升序排序。

func SearchIntsSource

func SearchInts(a []int, x int) int

SearchInts 在已排序的整数片段中搜索 x，并返回 Search 所指定的索引。如果 x 不存在（它可能是 len（a）），则返回值是插入 x 的索引。切片必须按升序排序。

func SearchStringsSource

func SearchStrings(a []string, x string) int

SearchStrings 在已排序的字符串片段中搜索 x，并返回 Search 所指定的索引。如果 x 不存在（它可能是 len（a）），则返回值是插入 x 的索引。切片必须按升序排序。

func SliceSource

func Slice(slice interface{}, less func(i, j int) bool)

由于提供了较少的功能，Slice 会对提供的切片进行排序。

排序不保证稳定。为了稳定排序，请使用 SliceStable。

如果提供的接口不是切片，则函数发生混乱。

例

package main

import (
	"fmt"
	"sort"
)

func main() {
	people := []struct {
		Name string
		Age  int
	}{
		{"Gopher", 7},
		{"Alice", 55},
		{"Vera", 24},
		{"Bob", 75},
	}
	sort.Slice(people, func(i, j int) bool { return people[i].Name < people[j].Name })
	fmt.Println("By name:", people)

	sort.Slice(people, func(i, j int) bool { return people[i].Age < people[j].Age })
	fmt.Println("By age:", people)
}

func SliceIsSortedSource

func SliceIsSorted(slice interface{}, less func(i, j int) bool) bool

SliceIsSorted 测试是否对切片进行排序。

如果提供的接口不是切片，则函数发生混乱。

func SliceStableSource

func SliceStable(slice interface{}, less func(i, j int) bool)

SliceStable 根据提供的 less 函数对提供的 slice 进行排序，同时保持相同元素的原始顺序。

如果提供的接口不是切片，则函数发生混乱。

例

package main

import (
	"fmt"
	"sort"
)

func main() {

	people := []struct {
		Name string
		Age  int
	}{
		{"Alice", 25},
		{"Elizabeth", 75},
		{"Alice", 75},
		{"Bob", 75},
		{"Alice", 75},
		{"Bob", 25},
		{"Colin", 25},
		{"Elizabeth", 25},
	}

	// Sort by name, preserving original order
	sort.SliceStable(people, func(i, j int) bool { return people[i].Name < people[j].Name })
	fmt.Println("By name:", people)

	// Sort by age preserving name order
	sort.SliceStable(people, func(i, j int) bool { return people[i].Age < people[j].Age })
	fmt.Println("By age,name:", people)

}

func SortSource

func Sort(data Interface)

对排序数据进行排序。它调用 data.Len 来确定 n 和 O（n * log（n））对 data.Less 和 data.Swap 的调用。排序不保证稳定。

func StableSource

func Stable(data Interface)

稳定排序数据，同时保持相同元素的原始顺序。

它调用 data.Len 来确定调用 data.Less 和 O（n * log（n）* log（n））调用 data.Swap 的 n，O（n * log（n））调用。

func StringsSource

func Strings(a []string)

Strings 按递增顺序排序一部分字符串。

例

package main

import (
	"fmt"
	"sort"
)

func main() {
	s := []string{"Go", "Bravo", "Gopher", "Alpha", "Grin", "Delta"}
	sort.Strings(s)
	fmt.Println(s)
}

func StringsAreSortedSource

func StringsAreSorted(a []string) bool

StringsAreSorted 测试一串字符串是否按递增顺序排序。

type Float64SliceSource

Float64Slice 将接口的方法附加到 [] float64，按递增顺序进行排序（非数字值被视为小于其他值）。

type Float64Slice []float64

func (Float64Slice) LenSource

func (p Float64Slice) Len() int

func (Float64Slice) LessSource

func (p Float64Slice) Less(i, j int) bool

func (Float64Slice) SearchSource

func (p Float64Slice) Search(x float64) int

搜索返回应用 SearchFloat64s 到接收器和 x 的结果。

func (Float64Slice) SortSource

func (p Float64Slice) Sort()

排序是一种方便的方法。

func (Float64Slice) SwapSource

func (p Float64Slice) Swap(i, j int)

type IntSliceSource

IntSlice 将接口的方法附加到 [] int，按升序排序。

type IntSlice []int

func (IntSlice) LenSource

func (p IntSlice) Len() int

func (IntSlice) LessSource

func (p IntSlice) Less(i, j int) bool

func (IntSlice) SearchSource

func (p IntSlice) Search(x int) int

Search 返回将 SearchInts 应用于接收者和 x 的结果。

func (IntSlice) SortSource

func (p IntSlice) Sort()

Sort 是一种方便的方法。

func (IntSlice) SwapSource

func (p IntSlice) Swap(i, j int)

type InterfaceSource

一个类型，通常是一个集合，满足 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)
}

func ReverseSource

func Reverse(data Interface) Interface

Reverse 返回数据的相反顺序。

例

package main

import (
	"fmt"
	"sort"
)

func main() {
	s := []int{5, 2, 6, 3, 1, 4} // unsorted
	sort.Sort(sort.Reverse(sort.IntSlice(s)))
	fmt.Println(s)
}

type StringSliceSource

StringSlice 将接口的方法附加到 []字符串，按升序排序。

type StringSlice []string

func (StringSlice) LenSource

func (p StringSlice) Len() int

func (StringSlice) LessSource

func (p StringSlice) Less(i, j int) bool

func (StringSlice) SearchSource

func (p StringSlice) Search(x string) int

Search 返回将 SearchStrings 应用于接收者和 x 的结果。

func (StringSlice) SortSource

func (p StringSlice) Sort()

Sort 是一种方便的方法。

func (StringSlice) SwapSource

func (p StringSlice) Swap(i, j int)

	排序算法 | sort
	排序算法 | sort	详细