Home > Backend Development > Golang > About the use of sorting in golang

About the use of sorting in golang

藏色散人
Release: 2020-10-10 14:59:30
forward
2693 people have browsed it

The following column golang tutorial will introduce you to the sorting and use of golang. I hope it will be helpful to friends in need!

About the use of sorting in golang

The golang standard library implements many commonly used sorting methods, such as integers Sequence sorting: sort.Ints(),
So what do you do if you sort a custom data structure?
For example, for a list of users, sort them by their points:

First define the data structure. In order to clearly explain the problem, only two fields are given.

type User struct {
	Name  string
	Score int}type Users []User
Copy after login

If you want to customize sorting in golang, you need to implement three methods in your own structure:

// 摘自: $GOROOT/src/sort/sort.gotype 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)}
Copy after login

This design is wonderful, isn’t it? Think about the sorting we have learned, all of which require sequences. Length, ratio size, swap elements.
How to use golang to sort the above Users, that is, the user list?

First implement these three methods as it says:

func (us Users) Len() int {
	return len(us)}func (us Users) Less(i, j int) bool {
	return us[i].Score < us[j].Score}func (us Users) Swap(i, j int) {
	us[i], us[j] = us[j], us[i]}
Copy after login

Then you can sort:

func main() {
	var us Users	const N = 6

	for i := 0; i < N; i++ {
		us = append(us, User{
			Name:  "user" + strconv.Itoa(i),
			Score: rand.Intn(N * N),
		})
	}

	fmt.Printf("%v\n", us)
	sort.Sort(us)
	fmt.Printf("%v\n", us)}
Copy after login

The possible output is:

[{user0 5} {user1 15} {user2 11} {user3 11} {user4 13} {user5 6}]
[{user0 5} {user5 6} {user2 11} {user3 11} {user4 13} {user1 15}]

As you can see, the scores are arranged from small to large.

But generally our points are sorted from large to small, just change
sort.Sort(us) to sort.Sort(sort .Reverse(us)) will do.

It’s really convenient.

Of course, if the sorting provided by the system cannot meet our needs due to special needs,
we can still implement the sorting by ourselves. For example, for the above, we can sort by ourselves (from small to large):

func myqsort(us []User, lo, hi int) {
	if lo < hi {
		pivot := partition(us, lo, hi)
		myqsort(us, lo, pivot-1)
		myqsort(us, pivot+1, hi)
	}}func partition(us []User, lo, hi int) int {
	tmp := us[lo]
	for lo < hi {
		for lo < hi && us[hi].Score >= tmp.Score {
			hi--
		}
		us[lo] = us[hi]

		for lo < hi && us[lo].Score <= tmp.Score {
			lo++
		}
		us[hi] = us[lo]
	}
	us[lo] = tmp	return hi}
Copy after login

A simple quick sort, just myqsort(us) is needed when calling.

Summary:

  • Custom sequences must implement the three methods of Less, Swap, and Len.

Welcome to add and correct!

The above is the detailed content of About the use of sorting in golang. For more information, please follow other related articles on the PHP Chinese website!

Related labels:
source:csdn.net
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template