快排时，为什么不能是__quicksort(arr,l,p)?

Question

请问老师，在快速排序时，为什么不能是__quicksort(arr,l,p)?尽管应该是p-1.但是用p会运行中断？这是为什么？

Answer 1

liuyubobobo 2017-11-17 02:11:29

因为每次partition之后，标定点p就会放在它应该在的位置：p之前的元素都比p小，p之后的元素都比p大，说明p已经在了将整个数组排好序后p应该在的位置。所以我们继续排序就不需要考虑p这个元素了，对arr[l, p-1]和arr[p+1, r]继续排序即可。

• 提问者 慕慕9414451 #1

  老师，经过测试，发现问题主要出现在__quickSort(arr,p,r)；这个语句。具体如下:
  首先老师的代码是正确无误的。
  若改为__quickSort(arr,l,p);__quickSort(arr,p+1,r)没有问题。
  
  出现问题的情况是__quickSort(arr,l,p-1);__quickSort(arr,p,r)。出错的原因是陷入死循环了。
  还请老师指教。

• liuyubobobo 回复 提问者 慕慕9414451 #2

  找一个小数据量跟一下。八成和无法保证做到每次向下递归都缩小数组有关。比如l=2，r=3；如果最终p的位置也在2，__quickSort(arr,p,r)将重复调用对[2,3]执行，形成无限递归。

• 提问者 慕慕9414451 回复 liuyubobobo #3

  您的总结相当精辟到位！佩服万分。对您的思路瞬间也理解了很多！非常感谢！何时老师能开一门公开课，讲讲您的武功心法和学习方法呢？当真是无限期待。

点开查看后面2条评论