|
|
排序算法不论是在面试还是刷题都经常遇到，掌握它能增加自己面试通过的几率提升自己的算法基础。 本文主要介绍一下三路快排，并以微软的一道面试题 leetcode 75. 颜色分类作为例题来讲解，供大家参考，希望对大家有所帮助。
三路快排
使用快速排序的思想给带有大量的重复键值的数组进行排序，一种经典的实现方式就是三路快排（Quick Sort 3 Ways）。
主要思想：将整个数组分成三部分，即小于 v、等于 v 和大于 v。分割后在递归的过程中，只需要递归地对小于 v 和大于 v 的部分进行快速排序，不关心等于 v 的部分。如下图示。
2、当前需要处理的元素为 i 位置的元素 k，保证 nums[lt+1...i-1] == v。如果 k == v，将 k 纳入等于 v 的部分，i 右移继续遍历。
3、如果 k < v，只需要将该元素与等于 v 的第一个元素交换位置，此时元素 k 处于小于 v 的最后一个元素，相应地 lt 向右移动一位，i 继续右移，查看下一个元素。
4、如果此时 k > v，只需要将该元素与 gt - 1 对应的元素交换位置，此时元素 k 处于数组大于 v 的第一个元素，相应地 gt 向左移动一位，指向大于 v 的第一个位置。
5、排序完成之后，数组如下图示意，lt 和 gt 分别指向小于 v 的最后一个位置和大于 v 的第一个位置，最后交换 l 位置的元素跟 lt 位置的元素，之后只需要对小于 v 和大于 v 的部分进行递归快速排序，等于 v 的部分已经放在数组中合适的位置。
优点：不需要对大量等于 v 的元素进行重复操作，可以少考虑很多元素，特别是对于等于 v 的元素特别多的话，这一步优化变得非常明显。
75. 颜色分类
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]
解题思路
由于排序后的数组主要依次分成三部分，即等于 0 的部分、等于 1 的部分和等于 2 的部分，这不是很像上面讲的三路快速排序吗？
每次选取一个标定点，由于数组中有很多个与标定点相等的元素，所以将数组分成三部分，即小于 v、等于 v 和大于 v，然后递归地对小于 v 和大于 v 的地方进行三路快排。
由于当前数组只有三个元素，所以只需要对整个数组执行一次三路快排即可。如下图示。
保证在遍历整个数组的过程中，0 处在整个数组的开始位置、1 处在紧接着 0 后面的位置，2 处在整个数组的末尾位置。
1、设置索引 zero 和 two，使得数组 nums[0...zero] == 0 和 nums[two...n-1] == 2，设置遍历索引 i 用于遍历数组元素，保证了 nums[zero+1...i-1] == 1。
2、当遍历到元素 m 时，如果 m == 1，此时只需将 m 纳入到属于 1 的部分，同时 i 右移。
3、如果 m == 2，只要取出索引 two 指向的元素的前一个元素 k（当前不等于 2 的第一个元素），与 m 进行交换位置，并将索引 two 左移一位，相当于将此时的 m 纳入到属于 2 的部分。
4、如果 m == 0，只需要找到索引 zero + 1 对应的元素（当前值为 1的第一个元素），将其与当前的 m 交换位置，并将 zero 右移，相当于将此时的 m 纳入到属于 0 的部分，将索引 i 右移查看下一元素的值。
Show me the Code
// c++
void sortColors(vector<int>& nums) {
int zero = -1; // 保证下标0到zero对应的元素都为0
int two = nums.size(); // 保证下标two到numsSize-1对应的元素都为 2
for (int i = 0; i < two;) {
// 直接将遍历到的元素1纳入到属于1的部分，i右移继续遍历
if (nums == 1) {
i++;
}
// 交换下标为two前一下标对应的元素与遍历到的元素
// 并将遍历到的元素2纳入到属于2的部分，two左移
else if (nums == 2) {
swap(nums, nums[--two]);
}
// 交换下标为zero后一下标对应的元素与遍历到的元素
// 并将遍历到的元素0纳入到属于0的部分，zero和i右移
else {
swap(nums[++zero], nums[i++]);
}
}
}
// go
func sortColors(nums []int) {
zero, two := -1, len(nums)
for i := 0; i < two; {
if nums == 1 {
i++
} else if nums == 2 {
two -= 1
nums, nums[two] = nums[two], nums
} else {
zero += 1
nums, nums[zero] = nums[zero], nums
i++
}
}
}往期同类精彩
更多精彩
关注公众号： 『程序员小熊』 |
|
发表于 2022-11-27 19:23:25