算法基础之快速排序的图解及 Go 代码实现

在算法的世界中，快速排序是一种高效且常用的排序算法。它采用了分治的策略，能够在平均情况下以 O(n log n) 的时间复杂度对数组进行排序。

让我们通过图解来理解快速排序的工作原理。假设我们有一个待排序的数组：[5, 1, 9, 3, 7, 2]。

选择一个基准元素，通常选择数组的第一个元素。然后，将数组分为小于基准和大于基准的两部分。

以 5 为基准，从数组的第二个元素开始比较。小于 5 的元素放在左边，大于 5 的元素放在右边。第一轮排序后，数组可能变为：[2, 1, 3, 5, 7, 9]。

接下来，对左右两部分分别重复上述步骤，直到整个数组有序。

下面是用 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{10, 7, 8, 9, 1, 5}
    n := len(arr)
    fmt.Println("排序前的数组为: ")
    printArray(arr, n)
    quickSort(arr, 0, n-1)
    fmt.Println("排序后的数组为: ")
    printArray(arr, n)
}

快速排序在实际应用中表现出色，尤其对于大型数据集。它的平均性能优秀，但在最坏情况下，时间复杂度可能退化为 O(n^2)。不过，通过合理选择基准元素，可以有效地避免最坏情况的发生。

通过对快速排序的图解和代码实现的学习，相信您对这种排序算法有了更深入的理解和掌握。