Go言語でソートを実装する方法-Golang-php.cn

Go言語でソートを実装する方法

PHPz

リリース： 2023-04-03 13:40:07

オリジナル

1737 人が閲覧しました

近年、Go 言語は、特に Web 開発やクラウドネイティブアプリケーションで非常に人気のあるプログラミング言語となっており、Go 言語を選択する開発者がますます増えています。中でもGo言語のソート機能は非常に強力で、さまざまなソート機能を簡単に実装できます。この記事では、Go 言語でソートを実装する方法を検討します。

1. Golang での並べ替え

Go 言語には、さまざまな並べ替えアルゴリズムを実装するための並べ替えパッケージが用意されており、並べ替えパッケージに含まれる 2 つの主要な関数を紹介します。

sort.Slice

sort.Slice 関数は、スライス (スライス) タイプのデータを並べ替えるために使用できます。その関数プロトタイプは次のとおりです。

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

ログイン後にコピー

このうち、

slice パラメータはソートが必要なスライスを表し、less パラメータは判定関数であり、戻り値は bool 型でなければなりません。判定関数 less は、スライス内の各要素の大小関係を判定するために使用され、true が返された場合は、前の要素が後の要素よりも小さいため、入れ替える必要があることを意味します。

int 型のスライスをソートする例を示します。サンプルコードは次のとおりです:

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)
}

ログイン後にコピー

上記のプログラムは int 型のスライスをソートでき、結果は次の順序で並べられます。小さいものから大きいものまで。

sort.Sort 関数は、sort.Interface インターフェイスを実装する型を並べ替えるために使用できます。その関数プロトタイプは次のとおりです:

func Sort(data Interface)

ログイン後にコピー

このうち、

data パラメータは並べ替える必要があるデータを表し、このパラメータは sort.Interface インターフェイスを実装する型である必要があります。 sort.Interface インターフェイスの定義は次のとおりです。

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

ログイン後にコピー

sort.Interface は、並べ替えに必要な 3 つの関数を定義します。 Len() はデータ長を返し、Less(i, j int) はデータ長を返すかどうかを判断するために使用されます。位置 i のデータは次のとおりです。データが位置 j より小さい場合、Swap(i, j int) は位置 i のデータを位置 j のデータと交換します。

文字列配列をソートする例を取り上げます。サンプルコードは次のとおりです:

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)
}

ログイン後にコピー

上記のプログラムは文字列配列をソートでき、結果は小さいものから大きいものへの順序で並べられます。。

2. 一般的な並べ替えアルゴリズムの実装

sort パッケージでは、クイックソート、ヒルソートなどの一般的な並べ替えアルゴリズムが実装されています。ソートパッケージによって提供される関数を使用することに加えて、開発者はソートアルゴリズムを自分で実装することもできます。

クイックソートでは、分割統治戦略を使用してシーケンスを 2 つのサブシーケンスに分割します。具体的なプロセスは次のとおりです:

以下は、クイックソートのサンプルコードです:

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)
}

ログイン後にコピー

ヒルソート。降順インクリメンタルソートアルゴリズムとも呼ばれます。 , は、挿入ソートのより効率的な実装です。ソート対象の要素をいくつかのグループに分割し、それぞれ挿入ソートを実行します。グループの数を徐々に減らし、グループ内の要素の間隔を広げることで、最終的なソートが完了します。

次は、Hill ソートのサンプルコードです:

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. 概要

この記事では、Go 言語でソートを実装する方法と、一般的に使用されるソートアルゴリズムを紹介します。高速ソートとヒルソートは最も一般的に使用されるソートアルゴリズムの 1 つであり、どちらも比較的効率的な実装方法です。 sort パッケージを使用する場合、開発者は sort.Interface の 3 つのメソッドをオーバーライドする必要があります。より複雑なデータ構造の場合は、独自の並べ替えアルゴリズムを実装して並べ替え操作を完了することもできます。

以上がGo言語でソートを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。