golang实现快速排序

• 什么是快速排序
  • 从数组中选中一个基准值，递归遍历数组的值和基准值作对比，分为比基准值大的，比基准值小的数组后合并

原地排序版本

js
package main

import "fmt"

func quickSort(nums []int, left, right int) {
    if left >= right {
            return
    }

    pivot := nums[left] // 选最左作为基准
    i, j := left, right

    for i < j {
        // 从右往左找小于 pivot 的
        for i < j && nums[j] >= pivot {
                j--
        }
        // 从左往右找大于 pivot 的
        for i < j && nums[i] <= pivot {
                i++
        }
        nums[i], nums[j] = nums[j], nums[i]
    }

    // 把 pivot 放到正确位置
    nums[left], nums[i] = nums[i], nums[left]

    quickSort(nums, left, i-1)
    quickSort(nums, i+1, right)
}

func main() {
    arr := []int{5, 2, 3, 1, 4}
    quickSort(arr, 0, len(arr)-1)
    fmt.Println(arr)
}

版本2

js
package main

import "fmt"

func quickSort(arr []int, left, right int) {
    if left < right {
        // 获取分区后的基准索引
        pivotIndex := partition(arr, left, right)

        // 递归排序左半部分
        quickSort(arr, left, pivotIndex-1)
        // 递归排序右半部分
        quickSort(arr, pivotIndex+1, right)
    }
}

func partition(arr []int, left, right int) int {
    // 选择最右侧元素作为基准
    pivot := arr[right]
    i := left - 1 // i 指向小于基准的区域边界

    for j := left; j < right; j++ {
        // 如果当前元素小于或等于基准
        if arr[j] <= pivot {
            i++
            // 交换元素
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    // 将基准值交换到中间正确的位置
    arr[i+1], arr[right] = arr[right], arr[i+1]
    return i + 1
}

func main() {
    data := []int{34, 7, 23, 32, 5, 62}
    fmt.Println("排序前:", data)

    quickSort(data, 0, len(data)-1)

    fmt.Println("排序后:", data)
}

标准版实现

js
package main

import (
    "fmt"
    "math/rand"
    "time"
)

// 快速排序入口函数
func QuickSort(arr []int) {
    if len(arr) <= 1 {
        return // 递归终止条件：数组长度≤1时已有序
    }
    // 分区操作，返回基准元素的最终索引
    pivotIdx := partition(arr)
    // 递归排序左右子数组
    QuickSort(arr[:pivotIdx])
    QuickSort(arr[pivotIdx+1:])
}

// 分区函数：将数组分为左右两部分，返回基准元素的索引
func partition(arr []int) int {
    // 选择最后一个元素作为基准
    pivot := arr[len(arr)-1]
    i := 0 // i是小于基准的区域的最后一个元素的索引

    // 遍历数组（除基准元素外）
    for j := 0; j < len(arr)-1; j++ {
        if arr[j] <= pivot {
            // 将当前元素交换到小于基准的区域
            arr[i], arr[j] = arr[j], arr[i]
            i++
        }
    }
    // 将基准元素放到正确的位置（小于基准区域的下一个位置）
    arr[i], arr[len(arr)-1] = arr[len(arr)-1], arr[i]
    return i
}

func main() {
    // 初始化随机数生成器
    rand.Seed(time.Now().UnixNano())

    // 生成随机测试数组
    arr := make([]int, 10)
    for i := range arr {
            arr[i] = rand.Intn(100)
    }

    fmt.Println("排序前:", arr)
    QuickSort(arr)
    fmt.Println("排序后:", arr)
}

基于标准版的优化

js
// 优化的分区函数：随机选择基准
func partitionOptimized(arr []int) int {
    // 随机选择一个索引作为基准
    randIdx := rand.Intn(len(arr))
    // 将基准元素交换到数组末尾，复用原分区逻辑
    arr[randIdx], arr[len(arr)-1] = arr[len(arr)-1], arr[randIdx]
    return partition(arr) // 调用原分区函数
}

// 优化的快速排序入口
func QuickSortOptimized(arr []int) {
    if len(arr) <= 1 {
            return
    }
    pivotIdx := partitionOptimized(arr)
    QuickSortOptimized(arr[:pivotIdx])
    QuickSortOptimized(arr[pivotIdx+1:])
}