__partition中while循环实现及算法学习方法的请教
来源：3-5 快速排序法 - Quick Sort
ych_1997
2021-06-21
int __partition(int *arr, int l, int r) {
int v = arr[l];
// 保持区间从遍历开始到结束的性质不变 arr[l+1...j] < v ; arr[j+1...i) > v
// 初始时（未开始考察） j [l+1...j] 等价于 [j+1 ... j] 此时区间为空
int j = l;
// 初始时（未开始考察） i [j+1 ... i) 等价于 [j+1 ... j+1) 此时区间为空
int i = l + 1;
while (i <= r) {
if (arr[i] < v) {
j++;
swap(arr[i], arr[j]);
}
i++;
}
// arr[i-1] 为最后一个 >= v 的元素。i此时在数组中已经越界，但程序不会访问。
// arr[j] 为最后一个 < v 的元素。交换后v找到了在目标数组的绝对位置。
swap(arr[j], arr[l]);
return j;
}
老师好！本人写业务代码一年有余，做的web后端。此次已经第三次（跨专业自学、准备面试、准备考研）训练快排的白板写作，发现并不能完全吃透快排，学习算法的路上颇有点吃力不讨好的感觉。我尝试调整我的学习方法，在方法论上有疑问！
-
当我能看懂视频中的动画演示的时候，我是不是要立刻尝试实现？
目前我的做法是，看完视频后，脑子里会过一遍动画，但是不做机械系记忆。第二天同一时间再进行白板写作。 -
总是在寻求边界问题的明确语义而花费大量时间，是否值得？如何优化方法？
看视频的时候，实现”保持区间从遍历开始到结束的性质不变“，让我疑惑，也让我写代码的时候异常痛苦。具体表现在，我实现帖子上的代码的过程：
2.1 如果有1000个数字进行快排，大概能清楚第4~5轮的动画演示。开始写代码，卡在第一个for循环不知道i和j分别取什么值合理，怕一步错步步错。
2.2 再看一遍动画演示，依旧不能自信的写出来，表现为写写删删改改，不运行程序。
2.3 直接看老师的代码，给我的感觉是注释也看不懂，开始怀疑自己的理解能力。
2.4 尝试自言自语去描述快排的过程，很困难，但是无法提出”正确的问题“。
2.5 尝试自己写代码，卡住了也忍住不看老师的代码，这段时间会容易焦虑。
2.6 用了两个晚上约6h，代码写完。已经能理解初始情况i和j的下标取值，并用while循环改写了老师第一个快排实现。我发现整个算法，最难理解的是开始和结束的边界问题。
2.7 完善自己的注释，再看一遍老师的代码，才明白老师注释背后的逻辑。
2.8 综上，约10h才能让我有自信重新完成快排的白板写作。
1回答
-
问题稍微有些大，我随便聊聊我的看法。
1）“我的做法是，看完视频后，脑子里会过一遍动画，但是不做机械系记忆。第二天同一时间再进行白板写作。”我觉得这个方法没毛病。实际上，学习算法，我认为基本上是完全不需要机械记忆的。
2）“总是在寻求边界问题的明确语义而花费大量时间，是否值得”值得。很多时候，边界是写出一个正确算法的关键，而定义正确边界的核心就是：明确边界的语义。
3）“怀疑自己的理解能力”不要怀疑。你的理解能力没有问题，而是本身“彻底理解一个算法”，本身就是难的，否则就没有那么多人对算法头疼了。同理，也不需要“焦虑”，如果听一段课程，大家就都能轻而易举地写出正确的算法，算法就没有那么难了。
4）“卡在第一个for循环不知道
i和j分别取什么值合理”实际上，i 和 j 的初值，就是由我们定义的循环的语义决定的。因为你最后说“明白老师注释背后的逻辑”，我相信你已经理解了这一点。而实际上，边界的取值方式是并不唯一的。边界的取值，可以跟着你定义的语义的变化而变化。我印象里，在我的课程中，针对二分搜索发介绍了这个问题。但不管怎么样，写出正确的程序的核心就是：定义清楚每一个变量的语义。所有的变量的维护，都是跟着开发者最初指定的变量的语义而变化的。这里有一个很重要的概念，叫循环不变量，即在循环中，要保持自己最初定义的语义的性质（也就是我注释的内容。）这一点可能在这个课程中，我的强调还不太够，我在我的其他课程中，越来越多地强调了这个问题。语义，语义，语义。
对于这一点，可能确实需要大量的练习，才能理解的越来越深刻。
值得一提的是，在写复杂的函数的时候（比如递归函数），也是这一点最为重要。很多同学对于复杂函数的书写，越来越乱，都是因为没有一个特别清晰的函数语义的定义。
5）“我发现整个算法，最难理解的是开始和结束的边界问题。”同上，我觉得你理解的非常透彻了。
最后，我不是很确定你说的方法论上的疑问是指什么，你可以继续补充。但是通过你的描述，我其实觉得你学习的方法没有问题。快排确实是这样一个说起来简单但实现起来细节颇多，不容易实现对的算法。10h 不算多，深入到算法中，debug 一个程序一晚上甚至一周都是正常的。
我相信你不是学习每一个算法都会如此（同样是高级排序，我个人认为归并排序涉及的这样的边界上的细节就少很多。）
继续加油！：）
212021-06-25
相似问题