快速排序

• 算法实现

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)