// 快速排序
// 时间复杂度：平均 O(nlogn)
// 空间复杂度：O(1)
// 稳定：否
func quickSort(nums []int, start, end int) {
	if start >= end {
		return
	}

	left, right := start, end
	pivot := nums[(start+end)/2]

	// 条件是 <= 防止死循环
	/*
		如果是 left < right,
		假设输入数据: [3, 2, 1, 4, 5]
		那么, pivot = 1, 完成一个 partition 之后是 [1, 2, 3, 4, 5] (left, right 都指向 2 )
		那么, 左边递归开始前是: [1, 2], 右边递归开始前是: [2, 3, 4, 5]
		(左边) 那么, pivot = 1, 完成一个 partition 之后是 [1, 2] (left, right 都指向 1 )
		(左边) 那么, 左边递归开始前是: [1], 右边递归开始前是: [1, 2]
		// [1, 2] 永远无法结束, 超时
	*/

	// nums[left] < pivot 而不是 nums[left] <= pivot 是防止时间复杂度降至 O(n^2), 如 [1, 1, 1, 1, 1]
	// 保证了等于的情况是均分的，防止最坏情况
	// 最终 pivot 左侧都是 <= pivot, pivot 右侧都是 >= pivot
	for left <= right {
		for left <= right && nums[left] < pivot {
			left++
		}
		for left <= right && nums[right] > pivot {
			right--
		}
		if left <= right {
			nums[left], nums[right] = nums[right], nums[left]
			left++
			right--
		}
	}

	quickSort(nums, start, right)
	quickSort(nums, left, end)
}

// 归并排序
// 时间复杂度：O(nlogn)
// 空间复杂度：O(n)
// 稳定：是
func mergeSort(nums []int, start int, end int, tmp []int) {
	if start >= end {
		return
	}
	mid := (start + end) / 2
	mergeSort(nums, start, mid, tmp)
	mergeSort(nums, mid+1, end, tmp)
	merge(nums, start, mid, end, tmp)
}

func merge(nums []int, start int, mid int, end int, tmp []int) {
	left := start
	right := mid + 1
	idx := start

	for left <= mid && right <= end {
		if nums[left] <= nums[right] {
			tmp[idx] = nums[left]
			idx++
			left++
		} else {
			tmp[idx] = nums[right]
			idx++
			right++
		}
	}

	for left <= mid {
		tmp[idx] = nums[left]
		idx++
		left++
	}

	for right <= end {
		tmp[idx] = nums[right]
		idx++
		right++
	}

	copy(nums[start:end+1], tmp[start:end+1])
}

/**
 * @param k: An integer
 * @param nums: An array
 * @return: the Kth largest element
 */
func KthLargestElement(k int, nums []int) int {
	return quickSelect(nums, 0, len(nums)-1, len(nums)-k)
}

func quickSelect(nums []int, start int, end int, k int) int {
	if start >= end {
		return nums[k]
	}

	left := start
	right := end
	mid := (start + end) / 2
	pivot := nums[mid]

	for left <= right {
		for left <= right && nums[left] < pivot {
			left++
		}
		for left <= right && nums[right] > pivot {
			right--
		}
		if left <= right {
			nums[left], nums[right] = nums[right], nums[left]
			left++
			right--
		}
	}

	if k <= right {
		return quickSelect(nums, start, right, k)
	}
	if k >= left {
		return quickSelect(nums, left, end, k)
	}

	return nums[k]
}