17370845950

本文详解go语言实现原地快排的关键逻辑，重点纠正分区函数中left++位置错误导致数组元素不更新的问题，并提供完整、可运行、符合go惯用法的快排实现。

在Go中实现快速排序时，一个极易被忽视却影响核心逻辑的细节是：分区（partition）过程中索引递增的时机必须严格匹配元素交换顺序。你提供的代码在JavaScript中能正常运行，是因为JS引擎对变量作用域和执行顺序的容错性较高；而Go作为静态编译型语言，对语义顺序极为敏感——尤其是当left++被错误地放在swap()之前时，会导致后续循环中arr[i]始终读取到未被正确重排的旧值，从而破坏分区不变式。

根本问题出在partition函数内这段逻辑：

if arr[i] <= v {
    left++
    swap(i, left) // ❌ 错误：先自增再交换，left指向的是下一个空位，swap操作实际写入了错误位置
}

这会导致：

• left 在交换前已增加，swap(i, left) 将 arr[i] 与 arr[left+1] 交换（而非预期的 arr[left]）；
• 分区后主元左侧区域无法保证全部 ≤ 主元，算法失去正确性；
• fmt.Println 中观察到 arr[i] “不变”，实则是因交换逻辑错位，数组状态未按预期演进。

✅ 正确写法是先交换，再递增：

if arr[i] <= v {
    swap(i, left) // ✅ 先将小元素放到 left 位置
    left++        // ✅ 再移动边界
}

以下是修复后的完整、健壮、符合Go风格的快速排序实现（含边界处理、避免切片拷贝、支持任意整数切片）：

package main

import "fmt"

// QuickSort 对输入切片进行原地升序排序
func QuickSort(arr []int) {
    if len(arr) <= 1 {
        return
    }
    quickSortHelper(arr, 0, len(arr)-1)
}

func quickSortHelper(arr []int, low, high int) {
    if low < high {
        pivotIndex := partition(arr, low, high)
        quickSortHelper(arr, low, pivotIndex-1)
        quickSortHelper(arr, pivotIndex+1, high)
    }
}

func partition(arr []int, low, high int) int {
    // 选择最后一个元素作为主元（更稳定，避免最坏O(n²)退化）
    pivot := arr[high]
    i := low - 1 // i 指向小于等于pivot区域的右边界

    for j := low; j < high; j++ {
        if arr[j] <= pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i] // Go惯用交换，无需临时变量
        }
    }
    arr[i+1], arr[high] = arr[high], arr[i+1] // 将pivot归位
    return i + 1
}

func main() {
    arr := []int{20, 43, 52, -1, 43, 29, 34}
    fmt.Println("Unsorted:", arr)

    QuickSort(arr) // 原地排序，不返回新切片
    fmt.Println("Sorted:  ", arr)
    // 输出：Sorted:   [-1 20 29 34 43 43 52]
}

? 关键改进与注意事项：

• 避免全局变量：原代码依赖包级变量 arr，破坏可复用性；新版使用参数传递，支持任意切片；
• 主元选择优化：采用末尾元素作主元（arr[high]），比取中点更易理解且减少越界风险；
• 边界安全：quickSortHelper 递归调用时使用 pivotIndex-1 和 pivotIndex+1，确保子区间不重叠、不越界；
• Go惯用交换：直接使用 a, b = b, a，简洁高效；
• 空/单元素保护：QuickSort 函数开头检查长度，提升鲁棒性。

? 延伸建议：生产环境推荐使用标准库 sort.Ints()（基于pdqsort优化），但手写快排对理解分治思想、指针操作与切片底层机制极具教学价值。调试时善用 fmt.Printf("i=%d, j=%d, arr=%v\n", i, j, arr) 观察每轮分区状态，是定位此类逻辑错误的高效方式。