三路快排的partition

Question

波波老师，关于三路快排的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
}

通过测试发现我的代码也是可以正常排序的。
比较了老师的代码实现后，这里我就产生了一些小小的疑惑：

1. 关于lt和gt的初始值问题，我初始化设置lt = l+1，gt = r，跟老师的有些差异。老师这里讲解是为了确保三个区域初始化时都为空。那么我这样设置是否合理呢？
2. 老师的代码中，当前元素nums[i]>v时，不需要操作i++，因为换位后i依然是一个未被处理的元素。但是我的代码中，即使nums[i]>v时i也是从前往后一直循环遍历的。这里是不是跟老师的代码有出入呢？

刚刚开始学习算法和数据结构，发现有些地方不是很清楚，麻烦老师帮解惑一下，谢谢老师！

Answer 1

liuyubobobo 2020-07-16 17:22:53

我按照你的逻辑在 C++ 上改变了一下，对于随机生成的测试用例是通不过测试的。

按照课程中的方式，随机生成 100 万的数据，用你的逻辑转一遍，然后编程验证一下，整个数组是不是有序的？如果有无序的部分，抛一个异常。看看最终是否会抛异常？

• 提问者 Corrots521 #1

  重新调试了一下，的确是我输出的测试用例问题，对于数组[]int{10, 9, 8, 7, 6, 5, 4, 3, 2, 1}能够排序。重新设置了随机的测试数据，就发现问题了。。。
  谢谢老师

Answer 2

提问者 Corrots521 2020-07-16 18:13:46

重新修改后的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
}