常用的排序算法

以下是一些最基本的排序算法。虽然在 C++ 里可以通过 std::sort() 快速排序，而且刷题 时很少需要自己手写排序算法，但是熟习各种排序算法可以加深自己对算法的基本理解，以及解 出由这些排序算法引申出来的题目。

关于常用的排序算法可以移步到 排序算法 | 面试问题浓缩总结 (xiaoyou66.com) (opens new window)

快速选择

数组中的第K个最大元素

215. 数组中的第K个最大元素 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这个题目其实很简单，就是自己先对数组进行排序，然后找到k的最大的元素就可以了（第一次手写快排哈哈~，，居然让我蒙对了好多）

func findKthLargest(nums []int, k int) int {
	// 先对数组进行排序
	quickSort(nums,0,len(nums)-1)
	return nums[len(nums)-k]
}

// 快速排序找到中点
func finMid(arr []int,low int,high int) int  {
	// 我们就使用第一个作为临时点
	tmp:=arr[low]
	for low < high {
		// 错误一：这里必须要low<high
		for low < high && arr[high] >= tmp {
			high --
		}
		arr[low] = arr[high]
		for low < high && arr[low] <= tmp {
			low ++
		}
		arr[high] = arr[low]
	}
	arr[low] = tmp
	return low
}

// 快速排序
func quickSort(arr []int,low int,high int)  {
	//错误2 这里是要确保low<high
	if low < high {
		mid:=finMid(arr,low,high)
		quickSort(arr,low,mid-1)
		quickSort(arr,mid+1,high)
	}
}

桶排序

前k个高频元素

这个题目在简单看了一下别人的思路的情况下做出来了，不容易啊，一直错误。。这个题目难点在于我们如何找出频率前k高的元素，还要保证时间复杂度优于nlogn,而且最变态的就是不同数字的出现次数居然还能重复。。。

所以我们使用桶排序来解决，首先我们使用map统计每个数字出现的次数，同时我们获取出现次数最多是多少。然后我们就建立一个大小为出现次数最多的一个桶，然后我们遍历map把数据放到桶里面去，最后我们只需要遍历这个桶就行了

func topKFrequent(nums []int, k int) []int {
	// 首先我们使用count来统计出现的频次
	count:=make(map[int]int)
	// 先遍历一次获取出现频率最大的
	max:=0
	for _,v:=range nums{
		count[v] ++
		// 这里获取出现次数最大的值
		if count[v] > max {
			max = count[v]
		}
	}
	// 然后我们就可以按照出现的频率来创建一个桶
	bucket:=make([][]int,max+1)
	// 创建一个map来存储数据
	for i,v:=range count{
		bucket[v]=append(bucket[v], i)
	}
	// 下面我们就可以找出前n高的元素了
	var ans []int
	for i:=len(bucket)-1;i>=0;i-- {
		// 因为我们桶里面是可能出现不同数的情况所以我们需要遍历
		for _,v:=range bucket[i] {
			// 当我们找出这前n个时，我们就立即返回
			if len(ans) < k {
				ans = append(ans,v)
			} else {
				return ans
			}
		}
	}
	return ans
}

基础难度 451. Sort Characters By Frequency (Medium) 桶排序的变形题。 进阶难度 75. Sort Colors (Medium) 很经典的荷兰国旗问题，考察如何对三个重复且打乱的值进行排序。