Question

让目标对象实现特定接口，以支持排序。
内部实现了 QuickSort 、 HeapSort 、 InsertionSort 、 SymMerge 算法。

package main

import (
	"fmt"
	"sort"
)

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

// [1 2 3 4 5 6]

Slice

通过自定义函数，选择要比较的内容，或改变次序。

func Slice(x any, less func(i, j int) bool)
func SliceStable(x any, less func(i, j int) bool)

func SliceIsSorted(x any, less func(i, j int) bool) bool

func main() {
	s := []struct{
		id   int
		name string
	}{
		{5, "a"}, 
		{2, "b"}, 
		{6, "c"}, 
		{3, "d"}, 
		{1, "e"}, 
		{4, "f"},
	}
	
	sort.Slice(s, func(i, j int) bool {
		// return s[i].id < s[j].id
		return s[i].id > s[j].id      // 倒序
	})

	fmt.Println(s)
}

// [{6 c} {5 a} {4 f} {3 d} {2 b} {1 e}]

Interface

避开辅助函数，实现排序接口。

type Interface interface {
	// Len is the number of elements in the collection.
	Len() int

	// Less reports whether the element with index i
	// must 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 Sort(data Interface)    // 不稳定排序，不保证相等元素原始次序不变。
func Stable(data Interface)  // 稳定排序，相等元素原始次序不变。

package main

import (
	"fmt"
	"sort"
)

type Data struct {
	text  string
	index int
}

// --------------------------

type Queue []Data

func (q Queue) Len() int {
	return len(q)
}

func (q Queue) Less(i, j int) bool {
	return q[i].index < q[j].index
}

func (q Queue) Swap(i, j int) {
	q[i], q[j] = q[j], q[i]
}

// ---------------------------

func main() {
	q := Queue{
		{"d", 3},
		{"c", 2},
		{"e", 4},
		{"a", 0},
		{"b", 1},
	}

	fmt.Println(sort.IsSorted(q))

	sort.Sort(q)
	fmt.Println(q, sort.IsSorted(q))
}

// false
// [{a 0} {b 1} {c 2} {d 3} {e 4}] true

Search

排序过后的数据，可用 Search 执行二分搜索（binary search）。
返回 [0,n) 之间， f() == true 的最小索引序号。
可用来查找有序插入位置。如找不到，则返回 n 。

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

func main() {
	q := Queue{
		{"a5", 5},
		{"a2", 2},
		{"a4", 4},
		{"a0", 0},
	}

	sort.Sort(q)
	fmt.Println(q)
    
    // --------------------------------------------

	// 找不到，返回 n。
	i := sort.Search(len(q), func(index int) bool {
		return q[index].index > 6
	})
    
	fmt.Println("index > 6:", i)
    
    // --------------------------------------------

	// 查找合适插入位置。
	i = sort.Search(len(q), func(index int) bool {
		return q[index].index >= 3
	})
    
	fmt.Println("index >= 3:", i)

	s := make(Queue, len(q)+1)
	copy(s, q[:i])
	copy(s[i+1:], q[i:])
	s[i] = Data{"a3", 3}
    
	fmt.Println(s)
}

/*

[{a0 0} {a2 2} {a4 4} {a5 5}]

index > 6: 4
index >= 3: 2

[{a0 0} {a2 2} {a3 3} {a4 4} {a5 5}]

*/

Reverse

辅助函数 Reverse 返回一个将 Less 参数对调的包装对象。
如此，判断结果就正好相反，实现倒序。

// sort.go

type reverse struct {
	Interface
}

func (r reverse) Less(i, j int) bool {
	return r.Interface.Less(j, i)
}

func Reverse(data Interface) Interface {
	return &reverse{data}
}

func main() {
	q := Queue{
		{"d", 4},
		{"b", 2},
		{"a", 1},
		{"c", 3},
	}

	sort.Sort(sort.Reverse(q))
	fmt.Println(q)
}

// [{d 4} {c 3} {b 2} {a 1}]