使用“双指针”实现的 partition 操作，把数组分成三个部分
三路快排的思路分析：
三路快排-1
分析清楚以后，我们就可以很轻松地写出代码：
Python 代码：
def __partition_3(nums, left, right):
p = nums[left]
# lt 是 less than 的意思，表示严格小于
lt = left
# gt 是 great than 的意思，表示严格大于
gt = right + 1
# i 这个变量用于遍历数组中的标定点以后的元素
i = left + 1
# 注意循环可以继续的条件，为什么不可以取“=”
while i < gt:
if nums[i] < p:
lt += 1
nums[i], nums[lt] = nums[lt], nums[i]
i += 1
elif nums[i] == p:
i += 1
else:
gt -= 1
nums[i], nums[gt] = nums[gt], nums[i]
# 想清楚，为什么交换 left 和 lt
nums[left], nums[lt] = nums[lt], nums[left]
return lt, gt
def __quick_sort(nums, left, right):
if left >= right:
return
lt, gt = __partition_3(nums, left, right)
# 在有很多重复元素的排序任务中，lt 和 gt 可能会相距很远
# 因此后序递归调用的区间变小
# 递归的深度也大大降低了
__quick_sort(nums, left, lt - 1) # 想清楚为什么这里右边界是 lt - 1
__quick_sort(nums, gt, right)
def quick_sort(nums):
__quick_sort(nums, 0, len(nums) - 1)
关于使用两个指针把数组分成 3 个部分，在 LeetCode 上有一个专门的问题，我们可以当成练习巩固一下。
例题
例题1：LeetCode 第 75 题：颜色分类
传送门：75. 颜色分类。
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。示例:
输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2]进阶：
- 一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。- 你能想出一个仅使用常数空间的一趟扫描算法吗？
分析：其实最容易想到的是计数：分别统计 0、1、2 出现的次数，然后再对数组重新赋值。于是，我们有
思路 1 ：最先应该想到的写法，用空间换时间。
Python 代码：
class Solution:
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
counter = [0] * 3
for num in nums:
counter[num] += 1
i = 0
for idx, count in enumerate(counter):
for _ in range(count):
nums[i] = idx
i += 1
思路 1 要使用 3 个辅助空间，并且要遍历数组两次。鉴于这道题本质上是一个排序问题，并且有大量重复键值，我们完全可以使用这一节介绍的“双指针”的办法。
思路2：“双指针”遍历一次，就把数组分成了三个部分。
Python 代码：
class Solution:
def sortColors(self, nums):
l = len(nums)
# 循环不变量的定义：
# [0,zero] 中的元素全部等于 0
# [zero+1,i) 中的元素全部等于 1
# [two,l-1] 中的元素全部等于 2
zero = -1
two = l
i = 0 # 马上要看的位置
while i < two:
if nums[i] == 0:
zero += 1
nums[zero], nums[i] = nums[i], nums[zero]
i += 1
elif nums[i] == 1:
i += 1
else:
two -= 1
nums[two], nums[i] = nums[i], nums[two]
例题2：LeetCode 第 451 题：根据字符出现频率排序
传送门：451. 根据字符出现频率排序。
给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
示例 1:
输入: "tree" 输出: "eert" 解释: 'e'出现两次，'r'和't'都只出现一次。 因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。示例 2:
输入: "cccaaa" 输出: "cccaaa" 解释: 'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。 注意"cacaca"是不正确的，因为相同的字母必须放在一起。示例 3:
输入: "Aabb" 输出: "bbAa" 解释: 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。 注意'A'和'a'被认为是两种不同的字符。
分析：题目的要求是很简单的。其实就是要我们“将字符串里的字符按照出现的频率降序排列”，为此，我们要做一个计数器，然后给 sort 函数一个排序规则就可以了。这是我们最容易想到的。
Python 代码：
class Solution:
def frequencySort(self, s):
"""
:type s: str
:rtype: str
"""
d = dict()
# 词频统计
for char in s:
d[char] = d.setdefault(char, 0) + 1
# 按照词频降序排序
sorted_item = sorted(d.items(), key=lambda x: x[1], reverse=True)
result = ''
for key, count in sorted_item:
result += key * count
return result
其实，这道问题做到这里感觉已经差不多了。但注意到这道题的特殊性，待排序的字符串的字符是有限的：26 个小写英文字母 + 26 个大写英文字母，再加上一些特殊字符，在字符串很长的时候，就会有大量的重复元素。而有大量重复元素的排序任务恰恰好是三路快速排序擅长处理的问题。我们注意到这一点，就可以手动编写三路快排，当然我觉得如果在面试中，先写上面的写法是肯定没有问题的，也是应该最先想到的。三路快排的写法并没有改变这个问题求解的本质。
Java 代码：
class Solution {
private Random random = new Random();
public String frequencySort(String s) {
char[] chars = s.toCharArray();
// 记录每个字符出现的频次, 数字下标为字符ASCII码, LeetCode这题的测试用例128已经够用了
int[] freq = new int[128];
// 遍历字符数组, 计算每个字符出现的频次, 这一步时间复杂度O(n)
for (int i = s.length() - 1; i >= 0; i--) {
freq[chars[i]]++;
}
// 对chars数组进行三路快排, 设定频次越高的字符值越大,频次相等时再按照字符ASCII码进行比较
// 排序这一步时间复杂度为O(nlogn), 所以整个算法的时间复杂度是O(nlogn)
quicksort3Ways(chars, 0, s.length() - 1, freq);
// 排序完成之后
return new String(chars);
}
/**
* 三路快排, 递归算法, 对chars数组的[l...r]前闭后闭区间进行排序
* @param chars : 要排序的字符数组
* @param l : 数组左边界
* @param r : 数组右边界
* @param freq : 字符出现频次, 设定字符大小与频次高低一致
*/
private void quicksort3Ways(char[] chars, int l, int r, int[] freq){
// 递归终止条件,只有一个元素时默认数组是有序的
if (r - l < 1) {
return;
}
// 选取标定点, 随机选取, 避免数组本身是有序的导致快排性能下降
int pivotIndex = random.nextInt(r - l + 1) + l;
swap(chars, l, pivotIndex);
char pivot = chars[l];
// 设定chars[l+1...left] < pivot, chars[left + 1, i) == pivot, chars[right, r] < pivot
int left = l, right = r + 1, i = l + 1;
while(i < right){
// 大于pivot的元素
if (compare(chars[i], pivot, freq) > 0) {
swap(chars, left + 1, i);
left++;
i++;
// 小于pivot的元素
} else if (compare(chars[i], pivot, freq) < 0) {
swap(chars, right - 1, i);
// right - 1的元素还没有遍历, 所以这里只需要right--, 并不用i++
right--;
} else {
i++;
}
}
// chars[l]==pivot, 所以最后需要将l与left交换位置
swap(chars, l , left);
// 递归对小于pivot的元素再进行排序
quicksort3Ways(chars, l, left, freq);
// 递归对大于pivot的元素再进行排序
quicksort3Ways(chars, right, r, freq);
}
public int compare(char c1, char c2, int[] freq) {
if (freq[c1] == freq[c2]){
return c1 - c2;
}
return freq[c1] - freq[c2];
}
/**
* 对数组chars数组中index1,index2位置的两个元素进行交换
* @param chars
* @param index1
* @param index2
*/
private void swap(char[] chars, int index1, int index2){
char temp = chars[index1];
chars[index1] = chars[index2];
chars[index2] = temp;
}
public static void main(String[] args) {
new Solution().frequencySort("cccaaa");
}
}
我们又注意到，其实我们每次只关心频次最大的那个数，不妨借助最大堆。堆的内容我们马上就要介绍了，如果还没有掌握堆的朋友们可以暂时跳过。
Python 代码：
class Solution:
def frequencySort(self, s):
"""
:type s: str
:rtype: str
"""
l = len(s)
if l <= 1:
return s
d = dict()
for alpha in s:
d[alpha] = d.setdefault(alpha, 0) + 1
# print(d.items())
import heapq
h = []
for alpha, counter in d.items():
heapq.heappush(h, (-counter, alpha))
res = ''
dl = len(d.items())
for _ in range(dl):
counter, alpha = heapq.heappop(h)
res += alpha * (-counter)
return res
本文源代码
（本节完）
