快速排序是一种基于分治法的高效排序算法,广泛应用于各种编程语言中。以下是一个简单的Golang实现快速排序的示例代码:
package main
import "fmt"
// 快速排序函数
func quickSort(arr []int, low, high int) {
if low < high {
// 找到基准值的位置
pivotIndex := partition(arr, low, high)
// 对基准值左边的子序列进行排序
quickSort(arr, low, pivotIndex-1)
// 对基准值右边的子序列进行排序
quickSort(arr, pivotIndex+1, high)
}
}
// 分区函数,将数组分为两部分,一部分小于基准值,另一部分大于基准值
func partition(arr []int, low, high int) int {
pivot := arr[high] // 选择最后一个元素作为基准值
i := low - 1 // 小于基准值的元素的索引
for j := low; j < high; j++ {
if arr[j] <= pivot {
i++ // 移动小于基准值的元素的索引
arr[i], arr[j] = arr[j], arr[i] // 交换元素
}
}
arr[i+1], arr[high] = arr[high], arr[i+1] // 将基准值放到正确的位置
return i + 1 // 返回基准值的最终位置
}
func main() {
arr := []int{10, 6, 7, 8, 1, 5}
fmt.Println("原数组:", arr)
quickSort(arr, 0, len(arr)-1)
fmt.Println("排序后:", arr)
}
代码解释:
- 快速排序函数:quickSort 函数接受一个整型切片 arr 和两个整数 low 和 high 作为参数,分别表示排序范围的起始和结束索引。
- 分区函数:partition 函数通过将数组分为两部分,一部分小于基准值,另一部分大于基准值,从而找到基准值的最终位置。
- 递归调用:在 quickSort 函数中,首先检查 low 是否小于 high,如果是,则递归调用 partition 函数来找到基准值的位置,然后对基准值左边和右边的子序列进行递归排序。