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

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

1. Golang での並べ替え

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

1. 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.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 つのサブシーケンスに分割します。具体的なプロセスは次のとおりです:

シーケンスから基本番号として要素を選択します。
基数より小さい要素はすべて基数の前に配置し、基数より大きい要素は基数の後に配置します。
参照番号の前後の 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 サイトの他の関連記事を参照してください。