三路快排的partition
来源：3-8 三路快速排序法
Corrots521
2020-07-16
波波老师，关于三路快排的partition这里，我按照你的动画讲解，自己补充了一下思路：
- 定义索引lt记录<v元素最后一个元素的位置；
- 定义索引gt记录>v元素第一个元素的位置；
- 遍历nums[l+1:r]中的元素，比较当前位置(i)的元素e与v的大小；
- e==v，i++即可；
- e<v，i和lt+1的元素互换位置，lt++；
- e>v，i和gt-1的元素互换位置，gt–；
- 当i>=gt时，结束循环；
- 最后l和lt的元素互换位置；
然后自己按照思路用go写了如下代码：
func partition(nums []int, l, r int) (int, int) {
random := rand.Int()%(r-l+1) + l
nums[l], nums[random] = nums[random], nums[l]
v := nums[l]
lt, gt := l+1, r
for i := l + 1; i <= r; i++ {
if i >= gt {
break
} else if nums[i] < v {
nums[i], nums[lt+1] = nums[lt+1], nums[i]
lt++
} else if nums[i] > v {
nums[i], nums[gt-1] = nums[gt-1], nums[i]
gt--
}
}
nums[l], nums[lt] = nums[lt], nums[l]
return lt, gt
}
通过测试发现我的代码也是可以正常排序的。
比较了老师的代码实现后，这里我就产生了一些小小的疑惑：
- 关于lt和gt的初始值问题，我初始化设置
lt = l+1，gt = r，跟老师的有些差异。老师这里讲解是为了确保三个区域初始化时都为空。那么我这样设置是否合理呢？ - 老师的代码中，当前元素
nums[i]>v时，不需要操作i++，因为换位后i依然是一个未被处理的元素。但是我的代码中，即使nums[i]>v时i也是从前往后一直循环遍历的。这里是不是跟老师的代码有出入呢？
刚刚开始学习算法和数据结构，发现有些地方不是很清楚，麻烦老师帮解惑一下，谢谢老师！
写回答
2回答
-
我按照你的逻辑在 C++ 上改变了一下，对于随机生成的测试用例是通不过测试的。
按照课程中的方式，随机生成 100 万的数据，用你的逻辑转一遍，然后编程验证一下，整个数组是不是有序的？如果有无序的部分，抛一个异常。看看最终是否会抛异常？
012020-07-16 -
Corrots521
提问者
2020-07-16
重新修改后的partition部分代码：
func partition(nums []int, l, r int) (int, int) { random := rand.Int()%(r-l+1) + l nums[l], nums[random] = nums[random], nums[l] v := nums[l] // 初始化lt, gt // 确保初始时nums[l+1,lt],nums[gt:r], nums[lt+1:i)都为空 lt, gt := l, r+1 i := l + 1 for i < gt { if nums[i] < v { nums[i], nums[lt+1] = nums[lt+1], nums[i] lt++ i++ } else if nums[i] > v { nums[i], nums[gt-1] = nums[gt-1], nums[i] gt-- } else { i++ } } nums[l], nums[lt] = nums[lt], nums[l] return lt, gt }00
相似问题