首页 计算机科学 算法训练 2023

# 快速排序

// 快速排序 填坑法
func quickSortV1(nums []int) []int {
	if len(nums) <= 1 {
		return nums
	}
	p := partionV1(nums)
	quickSortV1(nums[:p])
	quickSortV1(nums[p+1:])
	return nums
}
func partionV1(nums []int) int {
	low, high := 0, len(nums)-1
	pVal := nums[low]
	for low < high {
		for low < high && nums[high] >= pVal {
			high--
		}
		nums[low] = nums[high]
		for low < high && nums[low] <= pVal {
			low++
		}
		nums[high] = nums[low]
	}
	nums[low] = pVal
	return low
}
// 快速排序 顺序遍历法
func quickSortV2(nums []int) []int {
	if len(nums) <= 1 {
		return nums
	}
	p := partionV2(nums)
	quickSortV2(nums[:p])
	quickSortV2(nums[p+1:])
	return nums
}
func partionV2(nums []int) int {
	low, high := 0, len(nums)-1
	pVal := nums[low]
	i := low
	for j := low + 1; j <= high; j++ {
		if nums[j] < pVal {
			nums[i], nums[j] = nums[j], nums[i]
			i++
		}
	}
	nums[i] = pVal
	return i
}
关于快排之前还有文档：
go 多协程实现快排 V1 ：https://blog.twelveeee.top/2023/Go/go goroutine quicksort/
go 多协程实现快排 V2 : https://blog.twelveeee.top/2023/Go/go_goroutine_quicksort_v2/
# 算法题
# 1. 数组中的第 K 个最大元素
https://leetcode.cn/problems/kth-largest-element-in-an-array/description/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/10_QuickSort/level_2/topic_1.go
给定整数数组 nums 和整数 k ，请返回数组中第 **k** 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
ps: 感觉这题比较垃，主要是面向测试用例编程
func findKthLargest(nums []int, k int) int {
	return subFindKthLargest(nums, len(nums)-k-1, 0, len(nums)-1)
}
func subFindKthLargest(nums []int, k, low, high int) int {
	if low == high {
		return nums[low]
	}
	pVal := nums[low]
	i, j := low-1, high+1
	for i < j {
		for i++; nums[i] < pVal; i++ {
		}
		for j--; nums[j] > pVal; j-- {
		}
		if i < j {
			nums[i], nums[j] = nums[j], nums[i]
		}
	}
	p := j
	if p <= k {
		return subFindKthLargest(nums, k, p+1, high)
	}
	return subFindKthLargest(nums, k, low, p)
}
 
-->