「Go语言面试题」算法：手写快速排序（QuickSort）

package main

import (
    "fmt"
    "math/rand"
)

// QuickSort 快速排序函数
func QuickSort(arr []int) {
    // 如果数组长度小于等于1，无需排序
    if len(arr) <= 1 {
        return
    }
    
    // 调用递归排序函数
    quickSort(arr, 0, len(arr)-1)
}

// quickSort 递归排序函数
func quickSort(arr []int, low, high int) {
    if low < high {
        // 获取分区点
        pi := partition(arr, low, high)
        
        // 递归排序分区点左边的子数组
        quickSort(arr, low, pi-1)
        // 递归排序分区点右边的子数组
        quickSort(arr, pi+1, high)
    }
}

// partition 分区函数，选择最后一个元素作为基准
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 partitionRandom(arr []int, low, high int) int {
    // 随机选择基准值
    randomIndex := rand.Intn(high-low+1) + low
    arr[randomIndex], arr[high] = arr[high], arr[randomIndex]
    
    // 使用标准分区逻辑
    return partition(arr, low, high)
}

func main() {
    // 测试用例
    arr := []int{10, 7, 8, 9, 1, 5}
    fmt.Println("原始数组:", arr)
    
    QuickSort(arr)
    fmt.Println("排序后数组:", arr)
    
    // 测试随机数组
    randomArr := make([]int, 10)
    for i := range randomArr {
        randomArr[i] = rand.Intn(100)
    }
    fmt.Println("随机数组:", randomArr)
    
    QuickSort(randomArr)
    fmt.Println("排序后随机数组:", randomArr)
}