请问老师关于快速排序的疑问

Question

我带了一个小数据量{10,9,8,7}，然后在纸上画程序执行的流程，虽然最后能走完程序并正确排序，但其中还是绕的比较晕，尤其是对于这个p的变化看的一头雾水，老师可以说下这个p是怎么变化的吗？

Answer 1

liuyubobobo 2019-09-06 01:39:22

整体，p 的意思就是，对于当前处理的arr[l, r] 这个区间，找到了(严格说不是找，因为元素的位置有调整)一个位置 p， 对于 arr[l...p-1] 区域的元素，都小于 arr[p]，对于 arr[p + 1,r] 区域的元素，都大于 arr[p]。

注意，

1）每一个 p 的计算，都是针对当前处理的 arr[l...r] 区间来说的，不是 arr[0...n]

2）p不是在变化，是对于每一个arr[l...r]区间，都求出一个p

具体，我建议使用一个有7个元素的数据，再模拟一遍，体会一下这个过程。如果对于某个p的值感觉有疑问，你可以再来更加明确的提问：对于某一部，你认为p的取值应该是多少？但实际上却是多少？你觉得有疑问？

加油！：）

• 提问者 精慕门6573819 #1

  非常感谢！