// 1. 选择一个基准数量(可选第一个, 也可随机选数组的一个)
// 2. 双指针遍历, 右指针先动
// 3. 右指针找到比基准小的数, 停下
// 4. 左指针开始动, 当找到比基准打的数,停下
// 5. (3,4)步骤找到的数交换
// 6. 重复(3,4,5), 直到满足条件 7
// 7. 左右指针碰撞, 再交换一次值(防止之前是一个倒序数组)
func quickSort(data []int, left, right int)  {

	if left >= right {
		return
	}


	pivotIndex := partition(data, left, right)


	quickSort(data, left, pivotIndex - 1)
	quickSort(data, pivotIndex + 1, right)
}

func partition(data []int, left, right int) int {

	pivotIndex := left
	pivot := data[pivotIndex]
	for left != right {


		if data[right] > pivot {
			right --
			continue
		}

		// 增加等于符号, 防止基准位置右边有和基准数一样的数字
		// 导致进入死循环不停的交换两个值
		if data[left] <= pivot {
			left ++
			continue
		}


		data[left], data[right] = data[right], data[left]
	}

	data[left], data[pivotIndex] = data[pivotIndex], data[left]

	return left
}