Go言語でのsortパッケージの実装方法は何ですか?

Go は強く型付けされた言語であり、コードは簡潔で読みやすく、効率的なパフォーマンスを備えているため、開発者の間でますます人気が高まっています。その中でも、sort パッケージは Go 言語の標準ライブラリの重要な部分であり、スライスとユーザー定義のコレクション型のソート関数を提供します。この記事では、Go 言語でのsortパッケージの実装を紹介します。

sort パッケージの sort.Interface インターフェイスの定義は次のとおりです。

type Interface interface {
    // 嵌入内置的len函数，返回集合元素个数
    Len() int
    // 比较索引i和索引j上的元素
    Less(i, j int) bool
    // 交换索引i和索引j上的元素
    Swap(i, j int)
}

このインターフェイスを通じて、カスタム タイプの並べ替えアルゴリズムを実装できます。

sort パッケージには、Sort、Stable、Slice という 3 つの主要な並べ替えメソッドが実装されています。以下で 1 つずつ紹介します。

1. Sort

Sort メソッドは、受信スライスを並べ替え、最適化されたクイック ソート アルゴリズムを使用します。ソース コードからわかるように、スライスの型は []Type であるため、Type スライスを使用して Sort メソッドを直接呼び出すことができます (Type はスライスの内部要素の型です)。

func Sort(data Interface) {
    n := data.Len()
    quickSortFunc(n, swapFunc(data), maxDepth(n))
}

Sort メソッドは、並べ替え操作を実行するために、内部で QuickSortFunc 関数を呼び出します。この関数は、再帰が完了するか、分割されたサブスライスが小さすぎるまで、それ自体を再帰的に呼び出します。

// 快速排序
// n 为切片大小
// swap 为交换函数，可以通过sort.Interface中的swap方法来实现
func quickSortFunc(n int, swap swapFunc, maxDepth int) {
    // 插入排序，Num^1为偶数，&1可用来判断奇偶性
    if n < insertionSortThreshold {
        for i := 1; i < n; i++ {
            for j := i; j > 0 && swap(j-1, j); j-- {
            }
        }
        return
    }
    if maxDepth == 0 {
        heapSortFunc(n, swap)
        return
    }
    maxDepth--
    third := n / 2
    // 选择枢纽元
    if n > med3Threshold {
        m0 := 0
        m1 := n / 2
        m2 := n - 1
        if n > 40 {
            s := n / 8
            m0 = med3(swap, 0, s, 2*s)
            m1 = med3(swap, m1-s, m1, m1+s)
            m2 = med3(swap, n-1-2*s, n-1-s, n-1)
        }
        third = med3(swap, m0, m1, m2)
    }
    // 挖洞填数
    // z正反代表着大或小于枢纽元素
    z := n - 1
    // p代表在枢纽元素左边的指针，q代表在枢纽元素右边的指针
    p := 0
    q := z
    for {
        for ; p < n && !swap(p, third); p++ {
        }
        for ; q >= 0 && swap(q, third); q-- {
        }
        if p >= q {
            break
        }
        swap(p, q)
        if p == third {
            third = q
        } else if q == third {
            third = p
        }
        p++
        q--
    }
    // 对子切片递归调用quickSortFunc函数
    quickSortFunc(p, swap, maxDepth)
    quickSortFunc(n-p-1, swapFuncAt(swap, p+1), maxDepth)
}

2. Stable

Stable メソッドは、等しい要素の相対位置を変更しないで維持できる安定した並べ替えアルゴリズムです。この操作は主に、図内の要素の半並べ替えなど、Sort メソッドの並べ替えルールに準拠していない一部のスライスを比較的順序よく並べ替えることを目的としています。

func Stable(data Interface) {
    // length 为切片长度
    length := data.Len()
    // mergeSort函数就是归并排序
    mergeSort(data, 0, length)
}

このアルゴリズムは非常に効率的で、安定した並べ替えアルゴリズムであるだけでなく、複雑さも O(n log n) です。

3. Slice

Slice はサブスライスを並べ替えます (つまり、スライス [開始、終了)] を並べ替えます。このメソッドを使用すると、スライスでサポートされるすべての反復子を並べ替えることができます。

func Slice(slice interface{}, less func(i, j int) bool) {
    // 利用反射获取slice值信息
    rv := reflect.ValueOf(slice)
    // 获取长度信息
    vlen := rv.Len()
    // 初始化并调用SortInterface，参数为lessSlice
    reflect.Sort(newSortInterface(rv, makeLessSlice(less, vlen)))
}

less 関数メソッドの実装は、sort.Interface の Less メソッドに従って実装する必要があることに注意してください。less 関数は 2 つのインデックス i と j を渡し、ブール値を返します。要素 i が要素 j より小さいかどうか。そうであれば、swap(i, j)。

上記は、Go 言語での並べ替えパッケージの簡単な実装です。上記の紹介から、並べ替えパッケージは実装が比較的簡単であるにもかかわらず、効率的な並べ替えパフォーマンスがあり、開発者に大きな利便性を提供することがわかります。 。

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