更新时间：2017-02-15 22:36:42浏览次数：1+次
这个问题不会做的问题，出在算法实现的具体过程不熟悉，或者是代码看的糊里糊涂的了。这个空是一个算法关键地方，填不出来或者填错，并不表示你不懂快排算法，只是这部分的代码绕晕了。
看算法代码非常容易看晕看得喘不过气，主要原因在于循环递归的层次太多了，大脑一下子处理不过来。有一句话叫做，好记性不如烂笔头。如果大脑同时在运算的时候，还要记忆处理的结果，会造成很大的压力，结果最后层级越多，就越混乱了。
其实看代码是需要一定方法的，有了正确的方法，可以轻松自如的解决问题。下面我就来介绍如何来处理这类代码题目，这个方法适用今后的开发中的代码阅读，而不仅限于做题。
这是一道快排的题目，所以，快排的算法，你需要非常清楚。我说的清楚，不是你知道这个算法大概是怎么回事，而且还要知道，这个算法运算的过程，是个什么样子。你可以开始不用写代码实现，但是需要在书面上将一步步的结果演变出来。如果你没有演变过，那么请多演变几次，以加深对算法处理排序过程的每一步的感知。为什么要说感知每一步的变化呢？程序的实现也就是去演化每一步，最后得到一个结果。所以，如果我们要想看得懂代码，也就是要先把每一步演化的情况熟悉了。然后就很容易知道每一个算法的精髓，然后形成算法模型，理解就深刻了。
那么演化的过程，后面我在此题的讲解时分析，演示。
第一步是熟悉算法本身，第二步就是熟悉一个程序的整体的流程。
程序的整体流程是从main开始的，所以我们开始就从main函数开始阅读。而代码中显示的其他几个函数在main前面，是懒得写单独的函数声明，因为定义在前面，后面的函数就可以直接使用了。此时不能和阅读一般文章一样从头到尾阅读，这样容易找不到头尾，没有线索，思路就形不成。
在阅读代码的过程中，先抓住主线，理清一条思路，然后再一个个细节的去确认。
1.主函数main
所以，我们阅读main函数，得知a数组，就是要处理的数据。从这里我们也得知要得到的预期结果。毕竟我们可以手动演化一遍嘛，如果这都不会，就不要看代码了，就要回去手动来使用算法来排序得到结果。
我们做这样的算法题只能是拿来巩固你的算法的熟悉程度和理解程度，不是拿来虐自己的。当你能够手动演化出来结果，看代码做题是可以巩固理解的。
有了a数组后，我们可以看到quicksort(a,0,N-1)，这就是快排的一个函数调用。后面的就是打印结果，就可以忽略了。
2.进一步阅读quicksort函数
这个函数不需要你处理，但是你要明白这个函数的用处。从这个函数里看到，里面还调用了quicksort，这就是递归的实现。所以我们可以看到if(p<r)，这是递归的终止条件，如果没有这个条件，就会出现死递归，产生栈溢出。虽然这不是算法里的东西，但是这是递归正确的写法，也是需要学习的。
两个quicksort调用，从参数可以看到，q是中间一个分界，第一个quicksort是处理左边一部分的数据，第二个quicksort是处理右边一部分的数据的。而partition则是确定中间分界线的。
了解到这里，这个函数也就差不多了。但是问题来了，这个函数到底完成了算法的哪个部分呢？这个得问你自己了。请仔细将这个模型与算法的演化模型匹配，如果匹配到了，这个函数就看懂了。
实际上，这个部分就是完成递归的迭代演化。也就是将一个数组按照一个标尺切成两半，比标尺小的都在左边，比标尺大的都在右边。那么具体的标尺是什么呢？这里看不出来。只知道，从partition得到了一个分界点。所以我们需要看partition来进一步了解一次演化的过程。而quicksort则是整体上的N次的递归演化的过程。
3.了解一次的演化过程partition，确定分界点，供quicksort来使用。
大体看一下这个函数，里面有一个swap函数，这个函数有什么作用呢，我们需要先清楚。所以先找到这个函数的定义，然后再来看partition的具体代码。swap函数很简单，就是一个交换a数组的后两个参数指定的两个位置的元素。
要说难，除非你完全不懂的快排算法，否则quicksort也称不上难，一眼可以匹配上。而partition则真需要你去仔细看代码了。当然，如果你不熟悉快排演化过程，也是很难填出来答案的。
但是这里有3个while循环，还是要费点心思的，一共有5个量，分别是i,j,r,p,x。又是++，又是--，如果你想直接看代码，除非你对算法很熟很熟，一眼就可以匹配到过程，否则还是要费点劲的。话说回来，如果不能轻松匹配，要么就是算法不够熟练，手动演化的不够，要么就是C语言基础太弱了。都需要强化。
但是很多时候，两者都是。所以得想办法来读懂这段代码。前面说了，就是，烂笔头方法。另外就是一个代入法。烂笔头加上代入法，是阅读大量循环和复杂算法代码非常有效的方法。而前面提到的抓主线则是阅读整体工程项目代码需要用到的。
因为代码中没有任何注释，看起来颇为费劲，所以，你要将每一步看懂了，在后面加上注释。不是说你连最简单的赋值都看不懂，而是信息太多了，要减轻大脑的记忆压力，写出来可以让大脑将精力集中在读懂代码上，然后眼睛扫一遍，就可以将整个读懂的信息贯穿起来。
而对于一个过程的熟悉，最好的就是代入法。代入法就是将一个具体的数代入其中，而不是用抽象的i,j这些符号来表示。具体的数字是很容易感知的，抽象的代号很容易让人晕乎。
所以你先写好注释，如下所示：（这里为了讲解，注释写的很详细，在做题时可以简单写一下）
int partition(int a[], int p, int r)
{
int i = p;// int j = r + 1;//12
int x = a[p];//取区间第一个数作为标尺，这个是从后面的两个while循环比较得到的信息。
while(1){
while(i<r && a[++i]<x);//将从第二个开始和标尺比，如果小于标尺，就继续比较。
while(a[--j]>x);//从右往左比较，如果大于标尺，继续比较。
if(i>=j) break;//如果i,j相遇，说明两边推进，相遇了，比较完了。直接跳出就行了。
swap(a,i,j);//将大小两个数字交换位置如果是没有左右相遇而执行到这里，那说明左侧的有一个数字大于标尺，右侧有一个数字小于标尺，所以要交换到各自的区间，只要对调就行了。
}
swap(a,p,j);//那么回顾快排算法，我们知道，在对调完一次之后，以第一个数为标尺，从第二个到一个位置全部小于标尺，然后右边的全部大于标尺，所以，算法要求将标尺插到中间来，这样就得到了，标尺左侧全部小于标尺，标尺右侧全部大于标尺。
//这样一次执行，就确定一个标尺和标尺两侧的大小系列，在回到quicksort就可以递归将两边进一步的按照第一个数字来分成左右侧，直到已经是排好序为止。
return j;
}
看着代码，注释好每一步的动作，然后将数据代入，标好变量，指好指针，然后一步步的执行代码演化，就得到一步步的结果，最后就剩下最后一步，也就是填空的位置。我们很容易知道，最后的结果要是要让标尺在中间。所以就是对调一次。那么此时对调的变量也就很清楚了。p指向的是标尺，j是最有标尺要在的位置，所以就是swap(a,p,j);没有其他的答案。i在不断的变化，所以已经不等于p了。而j所处的位置，只有j一个人。
如果你觉得这个解答给力，记得分享给需要的人哦。
此类题目就不再重复解答，请按照这个方法一步步走就对了。别人这样走一遍也是这么走的，算法题不能一眼看的出来的，就是感觉的出来也得走一遍来验证。所以也是别人不愿意解答算法题的原因。不过有了这个方法，这种题也不是难题了，只要稍微花点时间，什么题都搞定了。当然前提是这个算法你要熟悉。
相关资讯
