千奇百怪的排序算法

常用排序算法

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

快速选择

215. Kth Largest Element in an Array
快速选择一般用于求解 Kth Element 问题,可以在 O(n) 时间复杂度,O(1) 空间复杂度完成求解工作。

桶排序

347. Top K Frequent Elements
顾名思义,桶排序的意思是为每个值设立一个桶,桶内记录这个值出现的次数(或其它属性),然后对桶进行排序。

练习

451. Sort Characters By Frequency
桶排序的变形题。

75. Sort Colors
很经典的荷兰国旗问题,考察如何对三个重复且打乱的值进行排序。