温馨提示×

go快速排序算法怎么实现

go
小亿
95
2023-10-26 18:40:56
栏目: 编程语言

快速排序(Quick Sort)是一种高效的排序算法,它的基本思想是选择一个基准元素,通过一趟排序将数组分成两部分,其中一部分的所有元素都比基准元素小,另一部分的所有元素都比基准元素大。然后递归地对这两部分进行排序,以达到整个数组有序的目的。

以下是使用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函数将数组划分成两部分,再递归地对两部分进行快速排序,直到整个数组有序。最后,通过调用QuickSort函数对给定数组进行排序。运行上述代码,输出结果为:[1 2 3 4 5 6 7 8 9],表示数组已经按照升序排序。

0