高速ソートアルゴリズムの実装方法

クイックソートは効率の良いソートアルゴリズムで、基本的には基準値を選択し、一度ソートすることで配列を 2 つに分割します。そのうちの 1 つは基準値よりも小さく、もう 1 つは基準値よりも大きいものです。そして、この 2 つを帰納的にソートすることで、配列全体をソートします。

以下に、Go でクイックソートアルゴリズムを実装するコードを示します。

package main

import "fmt"

// 快速排序
func QuickSort(arr []int, left, right int) {
	if left < right {
		// 获取分区点
		pivot := partition(arr, left, right)

		// 对分区点左侧进行快速排序
		QuickSort(arr, left, pivot-1)
		// 对分区点右侧进行快速排序
		QuickSort(arr, pivot+1, right)
	}
}

// 分区函数
func partition(arr []int, left, right int) int {
	// 使用数组的最后一个元素作为基准元素
	pivot := arr[right]
	// i指向小于pivot的元素的位置
	i := left - 1

	// 遍历数组，将小于pivot的元素交换到左侧
	for j := left; j < right; j++ {
		if arr[j] < pivot {
			i++
			arr[i], arr[j] = arr[j], arr[i]
		}
	}

	// 将pivot元素交换到正确的位置
	arr[i+1], arr[right] = arr[right], arr[i+1]

	// 返回分区点的位置
	return i + 1
}

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

上記のコードでは、QuickSort 関数がクイックソートアルゴリズムを実装し、partition 関数は配列を分割して分割点の位置を返します。QuickSort 関数では、最初に基準要素（ここでは最後の要素を選択）を選択し、partition 関数を呼び出して配列を 2 つの部分に分割します。その後、2 つの部分に対して再帰的にクイックソートを実行して、配列全体が整列するまで続けます。最後に、QuickSort 関数を呼び出して渡された配列をソートします。上記のコードを実行すると、出力結果は [1 2 3 4 5 6 7 8 9] となり、配列が昇順でソートされていることを示します。