__partition中while循环实现及算法学习方法的请教

Question

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后端。此次已经第三次（跨专业自学、准备面试、准备考研）训练快排的白板写作，发现并不能完全吃透快排，学习算法的路上颇有点吃力不讨好的感觉。我尝试调整我的学习方法，在方法论上有疑问！

1. 当我能看懂视频中的动画演示的时候，我是不是要立刻尝试实现？
   目前我的做法是，看完视频后，脑子里会过一遍动画，但是不做机械系记忆。第二天同一时间再进行白板写作。

2. 总是在寻求边界问题的明确语义而花费大量时间，是否值得？如何优化方法？
   看视频的时候，实现”保持区间从遍历开始到结束的性质不变“，让我疑惑，也让我写代码的时候异常痛苦。

   具体表现在，我实现帖子上的代码的过程：
   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才能让我有自信重新完成快排的白板写作。

Answer 1

liuyubobobo 2021-06-24 19:55:03

问题稍微有些大，我随便聊聊我的看法。

1）“我的做法是，看完视频后，脑子里会过一遍动画，但是不做机械系记忆。第二天同一时间再进行白板写作。”我觉得这个方法没毛病。实际上，学习算法，我认为基本上是完全不需要机械记忆的。

2）“总是在寻求边界问题的明确语义而花费大量时间，是否值得”值得。很多时候，边界是写出一个正确算法的关键，而定义正确边界的核心就是：明确边界的语义。

3）“怀疑自己的理解能力”不要怀疑。你的理解能力没有问题，而是本身“彻底理解一个算法”，本身就是难的，否则就没有那么多人对算法头疼了。同理，也不需要“焦虑”，如果听一段课程，大家就都能轻而易举地写出正确的算法，算法就没有那么难了。

4）“卡在第一个for循环不知道 i 和j 分别取什么值合理”实际上，i 和 j 的初值，就是由我们定义的循环的语义决定的。因为你最后说“明白老师注释背后的逻辑”，我相信你已经理解了这一点。

而实际上，边界的取值方式是并不唯一的。边界的取值，可以跟着你定义的语义的变化而变化。我印象里，在我的课程中，针对二分搜索发介绍了这个问题。但不管怎么样，写出正确的程序的核心就是：定义清楚每一个变量的语义。所有的变量的维护，都是跟着开发者最初指定的变量的语义而变化的。这里有一个很重要的概念，叫循环不变量，即在循环中，要保持自己最初定义的语义的性质（也就是我注释的内容。）这一点可能在这个课程中，我的强调还不太够，我在我的其他课程中，越来越多地强调了这个问题。语义，语义，语义。

对于这一点，可能确实需要大量的练习，才能理解的越来越深刻。

值得一提的是，在写复杂的函数的时候（比如递归函数），也是这一点最为重要。很多同学对于复杂函数的书写，越来越乱，都是因为没有一个特别清晰的函数语义的定义。

5）“我发现整个算法，最难理解的是开始和结束的边界问题。”同上，我觉得你理解的非常透彻了。

最后，我不是很确定你说的方法论上的疑问是指什么，你可以继续补充。但是通过你的描述，我其实觉得你学习的方法没有问题。快排确实是这样一个说起来简单但实现起来细节颇多，不容易实现对的算法。10h 不算多，深入到算法中，debug 一个程序一晚上甚至一周都是正常的。

我相信你不是学习每一个算法都会如此（同样是高级排序，我个人认为归并排序涉及的这样的边界上的细节就少很多。）

继续加油！：）

• 提问者 ych_1997 #1

  谢谢老师的耐心回答！！在向您提问的过程中，我尽可能描述我在学习本课程时遇到的困难。这个帖子与其说是方法论上的疑问，更准确来说是借提问来暴露自己的缺点。因为本人没有在计算机学习及工作上有过满意的学习经验，我认为掌握学习方法比掌握某个知识更有价值。获得老师的两个答复：“学习算法不需要机械记忆”“寻求边界问题的明确语义而花费大量时间，是值得的”让我坚信目前的学习状态与“不要犯完美主义”并不矛盾，我会加油的。