快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。快速排序是使用分治法（Divide and conquer）的一个非常典型的应用。在平均状况下，排序n个项目要 less than cubic time (i.e., O(n3) comparisons)。在最坏状况下（即 nearly sorted or reverse ordered input），排序 cost up to quadratic time (i.e., O(n2) comparisons)。但是，快速排序是对数时间（O(log n)）的算法。

func TestQuickSort(t *testing.T) {
    a := []int{9, 5, 6, 8, 3, 2, 1}
    QuickSort(a, 0, len(a)-1)
    fmt.Println(a)
}

func QuickSort(a []int, left, right int) {
    if left >= right {
        return
    }
    base := left
    hi := right
    for left < right {
        for left < right && a[right] >= a[base] { // 使用 >= 以保持基准值的稳定性
            right--
        }
        for left < right && a[left] <= a[base] {
            left++
        }
        if left < right {
            a[left], a[right] = a[right], a[left]
        }
    }
    // 将基准值交换到正确的位置
    a[base], a[left] = a[left], a[base]

    // 递归排序基准值左侧和右侧的元素
    QuickSort(a, base, left-1) // 注意这里的 left-1 和 base-1
    QuickSort(a, left+1, hi)   // 注意这里的 left+1
}