How to implement sorting in Go language

In recent years, Go language has become a very popular programming language, especially in web development and cloud native applications. More and more developers have chosen Go language. Among them, the sorting function in Go language is extremely powerful and can easily implement various sorting functions. In this article, we will explore how to implement sorting in Go language.

1. Sorting in Golang

The Go language provides the sort package to implement various sorting algorithms. Let’s introduce the two main functions in the sort package.

1. sort.Slice

The sort.Slice function can be used to sort a Slice (slice) type of data. Its function prototype is as follows:

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

Among them, the slice parameter represents the slice that needs to be sorted, the less parameter is a judgment function, and the return value must be of bool type. The judgment function less is used to determine the size relationship of each element in the slice. If true is returned, it means that the previous element is smaller than the later element and needs to be swapped.

Take sorting slices of type int as an example. The sample code is as follows:

package main

import (
    "fmt"
    "sort"
)

func main() {
    ints := []int{3, 1, 4, 1, 5, 9, 2, 6, 5, 4}
    sort.Slice(ints, func(i, j int) bool {
        return ints[i] < ints[j]
    })
    fmt.Println(ints)
}

The above program can sort a slice of type int, and the results will be arranged in order from small to large.

2. sort.Sort

The sort.Sort function can be used to sort types that implement the sort.Interface interface. Its function prototype is as follows:

func Sort(data Interface)

Among them, the data parameter represents the data that needs to be sorted, and the parameter must be a type that implements the sort.Interface interface. The definition of the sort.Interface interface is as follows:

type Interface interface {
    Len() int
    Less(i, j int) bool
    Swap(i, j int)
}

sort.Interface defines three functions necessary for sorting: Len() returns the data length, and Less(i, j int) is used to determine whether the data at position i is If the data is less than the j position, Swap(i, j int) swaps the data at the i position with the data at the j position.

Take sorting a string array as an example. The sample code is as follows:

package main

import (
    "fmt"
    "sort"
)

type stringSlice []string

func (s stringSlice) Len() int {
    return len(s)
}

func (s stringSlice) Less(i, j int) bool {
    return s[i] < s[j]
}

func (s stringSlice) Swap(i, j int) {
    s[i], s[j] = s[j], s[i]
}

func main() {
    words := stringSlice{"foo", "bar", "baz", "qux"}
    sort.Sort(words)
    fmt.Println(words)
}

The above program can sort a string array, and the results will be arranged in order from small to large.

2. Implementation of common sorting algorithms

In the sort package, common sorting algorithms are implemented, such as quick sort, Hill sort, etc. These algorithms are based on the sort.Interface interface. In addition to using the functions provided by the sort package, developers can also implement the sorting algorithm themselves.

1. Quick sort

Quick sort uses the divide-and-conquer strategy to divide a sequence into two sub-sequences. The specific process is as follows:

• From the sequence Pick an element as the base number.
• Place all elements smaller than the base number in front of the base number, and place elements larger than the base number after the base number.
• Repeat the above steps for the two subsequences before and after the reference number.

The following is a sample code for quick sorting:

package main

import "fmt"

func quickSort(arr []int, left, right int) {
    if left < right {
        partIndex := partition(arr, left, right)
        quickSort(arr, left, partIndex-1)
        quickSort(arr, partIndex+1, right)
    }
}

func partition(arr []int, left, right int) int {
    pivot := left
    for i:= left + 1; i <= right; i++ {
        if arr[i] < arr[left] {
            pivot++
            arr[pivot], arr[i] = arr[i], arr[pivot]
        }
    }
    arr[left], arr[pivot] = arr[pivot], arr[left]
    return pivot
}

func main() {
    arr := []int{5, 0, 3, 2, 1, 6, 8, 9, 7, 4}
    quickSort(arr, 0, len(arr)-1)
    fmt.Println(arr)
}

2. Hill sorting

Hill sorting, also known as descending incremental sorting algorithm , is a more efficient implementation of insertion sort. The elements to be sorted are divided into several groups, and insertion sorting is performed respectively. The final sorting is completed by gradually reducing the number of groups and increasing the interval of elements within the groups.

The following is a sample code for Hill sorting:

package main

import "fmt"

func shellSort(arr []int) []int {
    n := len(arr)
    for gap := n / 2; gap > 0; gap /= 2 {
        for i := gap; i < n; i++ {
            for j := i - gap; j >= 0 && arr[j] > arr[j+gap]; j -= gap {
                arr[j], arr[j+gap] = arr[j+gap], arr[j]
            }
        }
    }
    return arr
}

func main() {
    arr := []int{5, 0, 3, 2, 1, 6, 8, 9, 7, 4}
    fmt.Println(shellSort(arr))
}

3. Summary

This article introduces the method of implementing sorting in Go language and commonly used sorting algorithms, among which fast Sorting and Hill sorting are one of the most commonly used sorting algorithms, and they are both relatively efficient implementation methods. When using the sort package, developers need to override the three methods of sort.Interface. For some more complex data structures, they can also implement their own sorting algorithm to complete the sorting operation.

The above is the detailed content of How to implement sorting in Go language. For more information, please follow other related articles on the PHP Chinese website!