温馨提示×

golang快速排序算法怎么实现

小亿
92
2024-01-27 14:34:56
栏目: 编程语言

Golang中的快速排序算法可以通过以下步骤来实现:

  1. 选择一个基准元素,可以是数组中的任意一个元素。通常选择第一个元素作为基准元素。

  2. 将数组分为两部分,小于基准元素的放在左边,大于基准元素的放在右边。

  3. 递归地对左右两部分进行快速排序。

下面是一个示例代码实现:

package main

import "fmt"

func quickSort(arr []int, low, high int) {
	if low < high {
		pivot := partition(arr, low, high)
		quickSort(arr, low, pivot-1)
		quickSort(arr, pivot+1, high)
	}
}

func partition(arr []int, low, high int) int {
	pivot := arr[low]
	for low < high {
		for low < high && arr[high] >= pivot {
			high--
		}
		arr[low] = arr[high]

		for low < high && arr[low] <= pivot {
			low++
		}
		arr[high] = arr[low]
	}
	arr[low] = pivot
	return low
}

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

在上述示例代码中,quickSort函数实现了快速排序算法,partition函数用于划分数组并返回基准元素的最终位置。在main函数中,我们定义了一个待排序的整数数组,并调用quickSort函数对其进行排序。最后输出排序结果。

0