快速排序是一种基于分治法的高效排序算法,广泛应用于各种编程语言中。以下是一个简单的Golang实现快速排序的示例代码:

    1. package main
    2. import "fmt"
    3. // 快速排序函数
    4. func quickSort(arr []int, low, high int) {
    5. if low < high {
    6. // 找到基准值的位置
    7. pivotIndex := partition(arr, low, high)
    8. // 对基准值左边的子序列进行排序
    9. quickSort(arr, low, pivotIndex-1)
    10. // 对基准值右边的子序列进行排序
    11. quickSort(arr, pivotIndex+1, high)
    12. }
    13. }
    14. // 分区函数,将数组分为两部分,一部分小于基准值,另一部分大于基准值
    15. func partition(arr []int, low, high int) int {
    16. pivot := arr[high] // 选择最后一个元素作为基准值
    17. i := low - 1 // 小于基准值的元素的索引
    18. for j := low; j < high; j++ {
    19. if arr[j] <= pivot {
    20. i++ // 移动小于基准值的元素的索引
    21. arr[i], arr[j] = arr[j], arr[i] // 交换元素
    22. }
    23. }
    24. arr[i+1], arr[high] = arr[high], arr[i+1] // 将基准值放到正确的位置
    25. return i + 1 // 返回基准值的最终位置
    26. }
    27. func main() {
    28. arr := []int{10, 6, 7, 8, 1, 5}
    29. fmt.Println("原数组:", arr)
    30. quickSort(arr, 0, len(arr)-1)
    31. fmt.Println("排序后:", arr)
    32. }

    代码解释:

    • 快速排序函数:quickSort 函数接受一个整型切片 arr 和两个整数 low 和 high 作为参数,分别表示排序范围的起始和结束索引。
    • 分区函数:partition 函数通过将数组分为两部分,一部分小于基准值,另一部分大于基准值,从而找到基准值的最终位置。
    • 递归调用:在 quickSort 函数中,首先检查 low 是否小于 high,如果是,则递归调用 partition 函数来找到基准值的位置,然后对基准值左边和右边的子序列进行递归排序。