Goでクイックソートアルゴリズムを実装する方法

クイック ソートは古典的なソート アルゴリズムであり、ソート効率は非常に高く、時間計算量は O(n*logn) です。さまざまなプログラミング言語の中でも、Goに代表される新世代言語でもクイックソートの実装が多様に提供されていますが、本記事ではGoでのクイックソートアルゴリズムの実装方法を紹介します。

クイック ソート アルゴリズムの基本的な考え方は、クイック ソートの核となる操作は、配列内のすべての要素の中から特定の要素 (x) を選択することです (乱数またはfirst または last )、ピボット要素と呼ばれます。ソート対象のデータは、1 回のソート処理で 2 つの独立した部分に分割され、一方の部分のすべての要素は境界要素より小さく、もう一方の部分のすべての要素は境界要素より大きくなります。

具体的には、次の手順でクイック ソートを実装できます。

• 配列内の要素を比較要素 (ピボット) として選択します。
• ピボット以下の要素を左に配置し、ピボット以上の要素を右に配置します。
• 左側と右側でそれぞれ再帰的にすばやく並べ替えます。

Golang コードは次のとおりです:

package main

import "fmt"

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

func partition(arr []int, left, right int) int {
    pivot := arr[left]
    for left < right {
        for left < right && arr[right] >= pivot {
            right--
        }
        arr[left] = arr[right]
        for left < right && arr[left] <= pivot {
            left++
        }
        arr[right] = arr[left]
    }
    arr[left] = pivot
    return left
}

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

上記のコードは、クイック ソート プロセスを実装します。コード内のパーティション関数は要素を分割するために使用され、QuickSort 関数はクイック ソート再帰を実装するために使用されます。その中で、左右のポインタがそれぞれ中央に移動して、交換する必要がある番号を見つけ、交換を通じて新しい位置を決定し、ピボット位置に戻ります。

main関数では配列arrを定義し、クイックソート後の結果を出力しています。

要約すると、この記事は、クイック ソートの基本的なアルゴリズム原理を紹介し、Golang のコードを介してクイック ソートを実装することにより、クイック ソート アルゴリズムを理解して習得するのに役立ちます。

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