快排的疑问

来源：3-5 快速排序法 - Quick Sort

无心铁憨憨

2018-12-21

图片描述

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

写回答

1回答

liuyubobobo

2018-12-21

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

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

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

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

加油！：）

无心铁憨憨

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

2018-12-21

共1条回复

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

相似问题

回答 1

回答 2

回答 1

回答 7

回答 1