Golang array or slice sort

The introduction

Before, when scrolling leetCode, some questions needed to be sorted, such as:

a := []int{2.1.3 ,4}
sort.Ints(a)
fmt.Println(a) / / 1, 2, 3, 4
Copy the code

Results:

[1, 2, 3, 4]Copy the code

To explore the source

Let’s take a look at sort.ints () source code:

// Ints sorts a slice of ints in increasing order.
func Ints(a []int) { Sort(IntSlice(a)) } // Sort integer arrays in ascending order.
Copy the code

The question is, why should it increase? So let’s look at IntSlice() source:

// IntSlice attaches the methods of Interface to []int, sorting in increasing order.
type IntSlice []int // IntSlice appends Interface methods to []int in ascending order.
Copy the code

Why should it increase? Continue to look at:

func (p IntSlice) Len(a) int           { return len(p) }
func (p IntSlice) Less(i, j int) bool { return p[i] < p[j] } / / here, [I] p < p [j] / / increment, if p [I] > p [j] / / decreasing bai, it seems to be on int [] rewrite
func (p IntSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
Copy the code

Here, [I] p < p [j] increments, if p [I] > p [j] decreasing bai, it seems to rewrite the int [] additional methods.

Note: sort.sort (data Interface), pass is the Interface, let’s look at the source code

// Sort sorts data.
// It makes one call to data.Len to determine n, and O(n*log(n)) calls to //
[fixed] [fixed] [fixed] [fixed] [fixed] [fixed] [fixed] [fixed] [fixed] [fixed] [fixed
func Sort(data Interface) {
	n := data.Len()
	quickSort(data, 0, n, maxDepth(n))
}
Copy the code

Example:

type sortable []int // Rewrite three methods for []int
func (p sortable) Len(a) int           { return len(p) }
func (p sortable) Less(i, j int) bool { return p[i] > p[j] }
func (p sortable) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
func main(a) {
  	a := []int{2.1.3.4}
  	sort.Sort(sortable(a))
		fmt.Println(a)
}
Copy the code

Results:

[4 3 2 1]
Copy the code

There is another method: sort.Slice, just write less fun, do not read the source code:

// Slice sorts the provided Slice given the provided less function. // Provide less func for sorting
//
// The sort is not guaranteed to be stable. For a stable sort, use SliceStable
// SliceStable.
//
// The function panics if The provided interface is not a slice
func Slice(slice interface{}, less func(i, j int) bool) {
	rv := reflectValueOf(slice) / / reflection
	swap := reflectSwapper(slice) / / reflection
	length := rv.Len() // Rv, swap, len are retrieved by reflection, so only less fun is required
	quickSort_func(lessSwap{less, swap}, 0, length, maxDepth(length))
}
Copy the code

So:

func main(a) {
	a := []int{2.1.3.4}
	less := func(i, j int) bool {
		return a[i] > a[j]
	}
	sort.Slice(a, less)
	fmt.Println(a)
}
Copy the code

Results:

[4 3 2 1]
Copy the code

A two-dimensional

In fact, it’s the same thing as one dimension, and it’s the same two methods

  • sort.Sort(data Interface)
  • sort.Slice(slice interface{}, less func(i, j int)

conclusion

For simple sorting, you can use two methods:

  • sort.Sort(data Interface)
  • sort.Slice(slice interface{}, less func(i, j int)

Update go-Notes regularly