Go-快速排序

快速排序

• 算法实现

func partition(nums []int, left int, right int) int {
    value := nums[left] // 基准值
    for left < right {
        for nums[right] >= value && left < right { // 依次查找大于等于基准值的位置
            right--
        }
        nums[left] = nums[right]
        for nums[left] < value && left < right { // 依次查找小于基准值的位置
            left++
        }
        nums[right] = nums[left]
    }
    nums[left] = value
    // 最终 left == right 就是基准值的位置
    return left
}

func QuickSort(list []int, left int, right int) {
    if left < right {
        middle := partition(list, left, right)
        QuickSort(list, left, middle-1)
        QuickSort(list, middle+1, right)
    }
}

• 测试代码

func main() {
    list := []int{8, 4, 2, 9, 10, -3, 3, 20, 15, -1}
    QuickSort(list, 0, len(list)-1)
    fmt.Println(list)
}

• 排序结果

[-3 -1 2 3 4 8 9 10 15 20]

• 时间复杂度

O (nlogn)