快排的疑问

Question

假设我们是第一次进入这个方法，在进行交换的时候，arr[j + 1] 和 arr[ i ]所指的数组下标不是一样的么？为什么还要去交换，应该是arr[ j ] 和arr[ i ]进行交换吧？

Answer 1

liuyubobobo 2018-12-21 10:17:08

首先，不一定一样。因为arr[i] < v才会进入交换。

其次，即使一样，确实进行了多余的交换，但if里还在维护j，进行了j ++。关键在于，我们整个循环再保持注释里的条件：arr[l + 1...j] < v；arr[j + 1...i] > v

写成arr[j]和arr[i]交换不对。实际这么写测试一下看看？如果发现不对，仔细debug一下，看看到底为什么不对？

一定结合课程中这一小节从2:00开始的动画，仔细理解我们的每一个变量都在做什么，他们的具体定义是什么，我们是如何维持他们的具体定义的。维持变量的具体定义，试写出正确算法的关键。（更专业的术语，叫：循环不变量。）

加油！：）

• 提问者 无心铁憨憨 #1

  明白了，l这个下标所指的元素暂时保持不动，即使进行了多余的交换，也是为了保持小于V的元素最后是在V的左边，直到最后把V这个元素跟J所指的元素进行位置交换，J所在的位置所指的元素一定是小于V的