Go 语言中的快速排序算法实现

快速排序（Quick Sort）是一种高效的排序算法，在 Go 语言中实现快速排序可以充分发挥其性能优势。

快速排序的基本思想是选择一个基准元素，将待排序的数组划分为两部分，一部分的元素都小于等于基准元素，另一部分的元素都大于基准元素。然后对这两部分分别进行快速排序，从而实现整个数组的排序。

以下是一个用 Go 语言实现快速排序的示例代码：

package main

import "fmt"

// 交换函数
func swap(arr []int, i int, j int) {
    arr[i], arr[j] = arr[j], arr[i]
}

// 划分函数
func partition(arr []int, low int, high int) int {
    pivot := arr[high]
    i := (low - 1)

    for j := low; j <= high-1; j++ {
        if arr[j] <= pivot {
            i++
            swap(arr, i, j)
        }
    }
    swap(arr, i+1, high)
    return (i + 1)
}

// 快速排序函数
func quickSort(arr []int, low int, high int) {
    if low < high {
        pi := partition(arr, low, high)

        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
    }
}

// 打印数组函数
func printArray(arr []int, size int) {
    for i := 0; i < size; i++ {
        fmt.Printf("%d ", arr[i])
    }
    fmt.Println()
}

func main() {
    arr := []int{12, 11, 13, 5, 6}
    n := len(arr)

    fmt.Print("排序前的数组为: ")
    printArray(arr, n)

    quickSort(arr, 0, n-1)

    fmt.Print("排序后的数组为: ")
    printArray(arr, n)
}

在上述代码中，我们首先定义了swap函数用于交换数组中的元素，partition函数用于选择基准元素并进行划分，quickSort函数则是递归地对数组进行排序。

快速排序的平均时间复杂度为 O(nlogn)，空间复杂度为 O(logn)。它在大多数情况下都能表现出出色的性能，但在最坏情况下，时间复杂度可能会退化为 O(n^2)。不过，通过随机选择基准元素等优化手段，可以有效地减少最坏情况的出现概率。

快速排序是一种非常实用的排序算法，在 Go 语言中的实现也相对简单，能够高效地处理各种规模的数据排序问题。