第十八章 数组（三） ---- 数组的最值与排序 　 18.1 求数组中的最大值 ? 18.1.1 基本思路与实现 ? 18.1.2 实例 18.2 将数组元素排序 ? 18.2.1 现实算法与程序算法的不同 ? 18.2.2 冒泡排序 ? 18.2.3 选择排序 ? 18.2.4 快速排序 （选修） 18.3 小结 　 什么叫程序？随着我们学习的不断进展，这个问题的答案不断有新的表述。 今天，我们学过了“流程”，也学过了“数据类型”。 “流程”表达某种动作或操作的过程；“数据”表达现实生活的事物。因此，程序自然可以表达为“通过流程控制，来对数据进行正确的处理”。其实这一句话，也可以用两个字来代替“算法”。 事实上有一个著名的公式，说：程序 = 数据结构 + 算法。 　 要想真正理解什么叫算法，最好的办法还是从我们的现实生活入手。 　 最常见的例子，就是给整理扑克牌了。给你一付打乱的扑克牌，然后让你把它们整理，就是让你排序。结果是：前四张是：黑桃A，红心A，草花A、方块A，然后是2，3……老K，最后是大小王两张。? 这个过程使用的是“排序”算法。 　 更简单的，给你3张牌，让你找出其中最大的一张，这也需要一种算法。称为“求最值”。 你会说，这也算“算法”，3张牌往桌子上一摆，我“一眼”就能找出哪一张最大啊，我的大脑好像没有进行过任何计算。呵呵，这样说可就不对了。你把这三张牌往一头猪前面摆，摆上三年它也找不出哪一张是最大的。这可以证明，我们的大脑的确进行了一定的演算。 　 一套相同的算法，其实是连续的一段“流程控制”。可以用在不同的数据上。比如排序算法，我们可以用于整理扑克，也可以用于排出学员成绩的名次，而不这两样数据的数据结构是什么。但是一套算法在实现时，针对不同数据结构，有不同的实现。 　 这一章主要就是讲两种算法在数组上的实现，这两种算法是:“求最值”、“排序”。 　 18.1 求数组中的最大值 数组含有许多元素，这些元素如果是可以比较大小的，那就常常需要一种计算，求出这些元素中的最大值或最小值。求最值的算法应用在方方面面，比如：如何找出一条街上你喜欢的那某裙子最便宜卖的那家店。比如当早上第四节下课铃敲响后，如何找出从教室到食堂最近的一条路等等。 18.1.1 基本思路与实现 我想大家都知道了，一到要讲实例，我举的例子就是“成绩管理”。“烦不烦呢？”我看到有些同学使劲撇嘴。可不能烦啊，上一章的成绩管理中，“求成绩第一名”和“成绩排序”这样重要的功能还没实现呢。本章的作业就是它们了。 　 比如有这么一个数组，用于存储几个学生成绩。现在老师想找出其中的第一名。 　 int cj[] = {80,67,76,87,78}; 　 我们还是一眼“找”出了结果：87。但如果不是5个成绩，而是5万个成绩呢（比如首钢的工人进行考试的结果）？我们就不能一眼看出，而是不断地从一个个成绩里搜寻那个最大值。不管是5万还是5个，其实算法是一样的。 　 冰心老奶奶举了个例子：同样是从动物园回来，有的小学生写出让你如临其境的作文，而有的小学生则像是没有去过动物园一样，写得干巴巴的。 　 在把你的解决问题的思路转化为程序代码的过程中，显然第一步应该做是你能够用自然语言清楚地，准确地表达出你的思路。有些人能做好这一点，而有些人则表达得相当困难，仿佛他不会解决问题。 　 当然这是一个双向锻炼的过程，如果你原来在这方面不擅长，跟着我在这里学习编程，慢慢的你会发现自已不仅学会也写程序，而且学会了如何表达自已的想法、思路、情感……很多人说学习编程是一件快乐的事，很多人沉迷于编程，其中的一点奥妙，他们都不肯“泄密”，我泄密了。 　 言归正传。大家提起精神来！ 　 求最大值是一个“比较”的过程。我们就说5个数的情况，看看如何找出5个数中的最大值： 　 2、3、1、4、0 　 为了方便表达，我们用 N 来表示最大值。 　 1、首先假设第一个数就是最大值，则 N = 2; 2、把N和第二个数比较，发现 3 比 N 大，于是让 N = 3; 3、把N和第三个数比较，发现 1 不比 N 大，于是N不变。 4、把N和第四个数比较，发现 4 比 N 大，于是让 N = 4; 5、把N和第五个数比较，发现 0 不比 N 大，于是N不变; 　 求五个数的最大值，我们用了五行话表达，如果求100个数的最值呢？要比较99次，岂不是要写100行？按照它的表达，我们写成的代码是： 　 int n[5] = {2,3,1,4,0}; 　 int N = n[0]; 　 if(N > n[1]) ? N = n[1]; if(N > n[2]) ? N = n[2]; if(N > n[3]) ? N = n[3]; if(N > n[4]) ? N = n[4]; 　 这可不叫“算法”。所以前面的表达并没有说出真正的算法。我们要改进它。 　 1、首先假设第一个数就是最大值，则 N = 2; 2、把N和下一个数比较，如果下一个数比N大，则让N等于该数; 3、重复第二步，直到没有下一个数。 明白了吗？算法就是这样而来的。第一，这三行话可以适用于无论多少个数求最大值的情况，这是你的算法是否正确的一个必要条件，如果你的算法表达的长短依赖于具体数据的个数，那么你的算法不是通用的算法，不管是否能解决问题。第二，我们在表达中看到了“如果”，看到“重复”，很好，“如果”就是“分支流程”，就是if或switch；而“重复”就是“循环流程”，是for 或 while 或 do...while。 　 int n[5] = {2,3,1,4,0}; 　 int N = n[0]; 　 for( int i = 1; i < 5; i++) { ?? if(n[i] > N) ???? N = n[i]; } 　 循环从数组下标1开始，因为从算法的表述中，我们也看到了，N一开始就等于数组中的第一个数，而后和“下一个数”开始比较。 我们可以把代码改良，以让它方便于应用在任何个数的元素上。 　 int n[] = {2,3,1,4,0}; 　 int N = n[0]; 　 int count = sizeof(n) / sizeof(n[0]); 　 for( int i = 1; i < count; i++) { ?? if (n[i] > N) ???? N = n[i]; } 　 18.1.2 实例 　 要求： 1、不使用数组，实现让用户输入10个数，然后输出其中最大值。 2、同1，但要求使用数组。 　 既然是两个小题，我们就分别写两个函数吧。 　 //不使用数组的例子: void max1() { ? cout << "请输入10个数（每个数输入后加回车)" << endl; 　 ? int N,n; 　 ? cout << "第1个数：" : ? cin >> N; 　 ? for(int i = 1; i<10; i++) ? { ????? cout << "第" << i+1 << "个数:" ; ????? cin >> n; 　 ????? if( n > N) ???????? N = n; ? } 　 ? cout << "最大值为：" << N << endl; ? ? system("PAUSE");? //让控制台系统暂停。相当于我们以前的cin.get()或 getchar(); } 　 //使用数组的例子： void max2() { ?? cout << "请输入10个数（每个数输入后加回车)" << endl; 　 ?? int n[10]; ?? int N; ? ?? for(int i = 0; i<10; i++) ?? { ????? cout << "第" << i+1 << "个数："; ????? cin >> n[i]; ?? } 　 ?? N = n[0]; ?? for(int i=1; i<10; i++) ?? { ???? if(n[i] > N) ?????? N = n[i]; ?? } 　 ? cout << "最大值为：" << N << endl; ? ? system("PAUSE");? //让控制台系统暂停。 } 　 这样就完成了求最大值实例，如果是要求求最小值呢？改动仅在于那个if判断条件： 　 …… N = n[0]; //一开始假设第一个元素就是最小值 　 for(……） { ? if (n[i] < N) //如果有元素比我们假设的最小值还小，那就让最小值等于它吧 ????? N = n[i]; } …… 　 这套题目我没有提供实际代码，大家找开CB自已完成吧。重要的是，在调通程序之后，认真地比较两种处理方法之间的异同。 结论应该是：“算法的抽象逻辑是一样的，只是用在于不同的数据结构上，会有不同的实现”。前者只使用简单的数据类型，所以它不得不在一边输入的情况下，一边求最大值；而后者采用了数组，所以可以从容地先完成输入工作，然后再求最大值。 当算法经较复杂时，采用良好的数据结构的重要性就开始体现，比如下面的排序，我们必须使用数组或其它更复杂的数据。否则就实现不了。 　 18.2 将数组元素排序 排序，一个经典教学课程。 排序，一个在超高频的实用算法。 第一点是说，我们必须去学。第二点是说，像这样一个实用算法以，事实上C,C++肯定都为我们写好了，以库函数等形式提供给我们使用，而且，这些写好的代码，肯定是最优秀的实现。 可是我们还是要学，而且是从最笨“冒泡算法”学起。所谓的最笨，是指效率差的。 　 学习的原因：1、前面说了，为了锻炼我们的逻辑思维。2、为了在某些时候，我们可以对排过程做更多的控制。 　 18.2.1 现实算法与程序算法的不同 　 大家都是这么整理扑克牌：把54张摊开放在桌面，然后不断地调整各张牌的位置，并把已经有序的牌放到另外一个位置。 生活中的各种算法一般不用考虑“内存”的问题。比如上面的问题，54牌每一张都要占用一点桌面，这算是固定需要的内存，而在“腾挪”各张牌，使之渐渐变得有序的过程中，还需要开辟新的空间，包括手里抓着的牌，即手心也算是一个内存。 程序排序，要求既要占用内存少，又要速度快。这是衡量一个算法是否优秀的两个基本点。 　 若是应用到人整理牌这一例子，则除了实现将54张牌按次序（牌值和牌花）排好以外，还需另有要求： 1、除了54张牌一开始占用的桌面，及你的一个手心以外，你在整理的过程中，不能让牌再占用新的桌面空间。 2、要求“比较两张牌大小”“交换两张的位置”等过程都尽量地少。 　 你可以拿出家里的扑克牌，现在就开始按上面的要求进行手工排序。也可以下载网站上的“扑克排序”的程序，通过它来模拟手工排序：鼠标点击某一张牌，该牌将移到当前的空位上。（正工学员下载课程包中已含该程序） 　 18.2.2 冒泡排序 　 “冒泡”是什么意思？湖底有时会冒出一个气泡，气泡刚在湖底时，是很小的，在向上浮的过程中，才一点地慢慢变大。学过高中的物理的人，应该不难解释这一现象。冒泡排序的过程有点类似这个过程，每前进一步，值就大一点。 　 排序当然有两个方向，一种是从小排到大，一种是从大排到小。大多数教科书里都讲第一种，我们也如此。这样一来，冒泡排序法就改为“沉泡法”了，较大值一点点跑到数组中的末尾。 　 一般教科书里也会说，冒泡排序法是人们最熟悉，及最直观的排序法，我可不这样认为。或许老外在生活中用的是这种最笨的排序法？我猜想，大家在生活中99%使用后面要讲的“选择”排序法。 　 冒泡排序是这么一个过程(从小到大): 　 1、比较相邻的两个元素，如果后面的比前面小，就对调二者。反复比较，到最后两个元素。结果，最大值就跑到了最末位置。 2、反复第一步，直到所有较大值都跑到靠后的位置。 　 看一眼例子： 　 2，5，1，4，3 　 第一遍： ·比较第一对相邻元素：2，5，发现后面的5并不比2小，所以不做处理。 序列保持不变：2，5，1，4，3 ·继续比较后两对元素：5，1，发现后面的1比前面的5小，所以对调二者。现在，序列变为：2，1，5，4，3 ·继续比较后两对元素：5，4……对调，于是：2，1，4，5，3 ·继续比较后两对元素：5，3……对调，于是：2，1，4，3，5 <----- OK,现在最大值5跑到最尾处了。 　 大泡泡“5”浮出来了，但前面的2,1,4,3,还是没有排好，没事，再来一遍，不过，由于最后一个元素肯定是最大值了，所以我们这回只排到倒数第二个即可。 　 第二遍： ·比较第一对相邻元素：2，1，发现1比2小，所以对调：1,2,4,3,5 ·继续比较后两对元素：2，4，不用处理，因为后面的数比较大。序列还是：1,2,4,3,5 ·继续 4，3，对调：1,2,3,4,5。 　 前面说，5 不用再参加比较了。现在的序列是1，2，3，4，5。接下来，我们再来一遍： 　 第三遍： ·比较第一对相邻元素：1，2：不用对调。 ……等等…… 有人说，现在已经是1，2，3，4，5了，完全是排好序了啊，何必再来进行呢？我们确实是看出前面1，2，3也井然有序了，但对于程序来说，它只能明确地知道自己已经排好了两个数：4，5，并不知道的1，2，3凑巧也排好了。所以它必须再排两次，直到确认把3和2都已推到合适的位置上。最后剩一个数是1，因为只有一个数，没得比，所以这才宣告排序结束。 　 那么到底要排几遍？看一看前面的“第一遍”、“第二遍”的过程你可发现，每进行一遍，可以明确地将一个当前的最大值推到末尾，所以如果排 Count 个数，则应排 Count 遍。当然，最后一遍是空走，因为仅剩一个元素，没得比较。 　 下面就动手写冒泡排序法的函数。写成函数是因为我们希望这个排序法可处理任意个元素的数组。 　 //冒泡排序(从小到大)： //num: 要接受排序的数组 //count : 该数组的元素个数 void bubble(int num[],int count) { ??? int tmp; 　 ??? //要排Count个数，则应排Count遍： ??? for (int i = 0; i < count; i++) ??? { ?????? for(int j = 0; j < count - i - 1; j++) ?????? { ?????????? //比较相邻的两个数： ?????????? if(num[j+1] < num[j]) ?????????? { ?????????????? //对调两个数，需要有"第三者"参以 ?????????????? tmp = num[j+1]; ?????????????? num[j+1] = num[j]; ?????????????? num[j] = tmp; ?????????? } ?????? } ??? }????? } 　 注意在内层循环中j的结束值是 count - i - 1。 要理解这段代码，明白为什么结束在count - i -1？如果你忘了如何在CB进行代码调试，如果设置断点，如何单步运行，如何观察变量的值，那么你需要“严重”复习前面有关“调试”的章节；如果你一直是高度着每一章的程序到现在，那么你可以继续下面的内容。 　 排序函数写出一个了，如何调试这个函数？在CB里新建一空白控制台程序，然后在主函数里，让我们写一些代码来调用这个函数，并且观察排序结果。 　 #include <iostream.h> …… void bubble(int num[],int count) { ? …… } 　 int main() //我实在有些懒得写main里两个参数，反正它们暂时对我们都没有用， ?????????? //反正CB会为你自动生成，所以从此刻起，我不写了,除非有必要。 { ?? ?int values[] = {2,5,1,4,3}; ??? int count = sizeof(values[]) / sizeof(values[0]); ??? bubble(value,sizeof); } 　 你要做的工作是单步跟踪上面的代码，看看整个流程是不是像我前面不厌其烦的写的“第一遍第二遍第三遍”所描述的。 　 完成上面的工作了吗？全部过程下来，只花20分钟应该算是速度快或者不认真的了（天知道你是哪一种？天知道你到底是不是没有完成就来骗我？）。现在让这个程序有点输出。我们加一个小小的函数： 　 //输出数组的元素值 //num :待输出的数组 //count:元素个数 void printArray(int num[],int count) { ? for(int i = 0; i < count; i++) ? { ???? count << num[i] << ","; ? } 　 ? cout << endl; } 　 把这个函数加到main()函数头之前，然后我们用它来输出： int main() //我实在有些懒得写main里两个参数，反正它们暂时对我们都没有用， ?????????? //反正CB会为你自动生成，所以从此刻起，我不写了,除非有必要。 { ?? ?int values[] = {2,5,1,4,3}; ??? int count = sizeof(values[]) / sizeof(values[0]); ??? ??? cout << "排序之前：" << endl; ??? printArray(values,count); 　 ??? //冒泡排序： ??? bubble(value,sizeof); 　 ??? cout << "排序之后:"? << endl; ??? printArray(values,count); 　 ??? system("PAUSE"); } 　 后面要讲的其它排序法也将用这个printArray()来作输出。 　 冒泡排序是效率最差劲的方法（速度慢），不过若论起不另外占用内存，则它当属第一。在交换元素中使用了一个临时变量（第三者），还有两个循环因子i和j，这些都属于必须品，其它的它一个变量也没多占。 　 我们现在讲讲如何避免数据其实已经排好，程序仍然空转的的局面。 首先要肯定一点，至少一遍的空转是不可避免的，这包括让人来排，因为你要发现结果已是1，2，3，4，5了，你也是用眼睛从头到尾抄了一遍（如果你视力不好，说不定还要扫两遍呢）。 接下来一点，我们来看看除了第一遍空转，后面的是否可以避免。冒泡排序法的空转意味着什么？因为算法是拿相邻的两个比较，一发现次序不合“从小到大”的目的（小的在大的后头），就进行对调。所以如果这个对调一次也没有进行，那就说明后面的元素必然是已经完全有序了，可以放心地结束。 　 让我们来加个变量，用于标志刚刚完成的这一遍是否空转，如果是空转，就让代码跳出循环。 　 //冒泡排序(从小到大，且加了空转判断)： void bubble(int num[],int count) { ??? int tmp; ??? bool swapped;? //有交换吗？ 　 ??? //要排Count个数，则应排Count遍： ??? for (int i = 0; i < count; i++) ??? { ?????? //第一遍开始之前，我们都假充本遍可能没有交换（空转）： ?????? swapped = false; 　 ?????? for(int j = 0; j < count - i - 1; j++) ?????? { ?????????? //比较相邻的两个数： ?????????? if(num[j+1] < num[j])? //后面的数小于前面的数 ?????????? { ?????????????? swapped = true;? //还是有交换 ???????????? ?????????????? //对调两个数，需要有"第三者"参以 ?????????????? tmp = num[j+1]; ?????????????? num[j+1] = num[j]; ?????????????? num[j] = tmp; ?????????? } ?????? } ?????? ?????? if (!swapped) ????????? break; ??? }????? } 加了swapped标志，这个算法也快不了多少，甚至会慢也有可能。冒泡排序还有一些其它的改进的可能，但同样作用不大，并且会让其丧失仅有优点“代码简单直观”。所以我个人认为真有需要使用冒泡排序时，仅用最原汁原味的“泡”就好。必竟，你选择了冒泡算法，就说明你对本次排序的速度并无多高的要求。 　 对于n个元素，原汁原味的“冒泡排序”算法要做的比较次数是固定的： （n? - 1）* n/2 次的比较。 交换次数呢？如果一开始就是排好序的数据，则交换次数为0。 一般情况下为 3 * (n - 1) * n / 4;最惨时（逆序）为3 *? (n - 1) * n / 2。 　 冒完泡以后——情不自禁看一眼窗台罐头瓶里那只胖金鱼——让我们开始中国人最直观的选择排序法吧。对了，补一句，如果你看到有人在说“上推排序”，那么你要知道，“上推排序”是“冒泡排序”的另一种叫法，惟一的区别是：它不会让我们联想到金鱼。 　 18.2.3 选择排序 　 本章前头我们讲了“求最值”的算法，包括最大值和最小值。其实，有了求最值的算法，排序不也完成了一半？想像一下桌子上摊开着牌，第一次我们从中换挑出大王放在手上，第二次我们挑出小王，然后是黑桃老K……黑桃Q，如此下去直到小A，手中的牌不也就已经排好次序了？ 　 每次从中选出最大值或最小值，依此排成序，这就是选择排序法的过程描述。 　 不过，上述的过程有一点不合要求。我们说过手中只能过一张牌。因此，在程序实现时，我们找出一个最大值之后，就要把它放到数组中最末。那数组中最末位置原来的值？当然是把它放到最大值原来所在位置了。 为了再稍稍直观点，我们改为：每次找的是最小值，找出后改为放到数组前头。 　 //选择排序（从小到大） void select(int num[], int count) { ??? int tmp; ??? int minIndex; //用于记住最小值的下标 　 ??? for (int i = 0; i < count; i++) ??? { ???????? minIndex = i; //每次都假设i所在位置的元素是最小的 ???????? for (int j = i + 1; j < count; j++) //j 从i+1开始，i之前的都已排好,而i是本次的第一个元素 ???????? { ???????????? if (num[minIndex] < num[j]) ??????????????? minIndex = j; ???????? } 　 ??????? //把当前最小元素和前面第i个元素交换： ??????? if(minIndex != i) ??????? { ??????????? tmp = num[i]; ??????????? num[i] = num[minIndex]; ??????????? num[minIndex] = tmp; ??????? } ??? } } 　 同样是两层循环，内层循环非常类似于前面讲的求最值的的方法，重要的区别在于求最小值时，可以直接用N记下最小值，而我们这里是记下最小值元素的下标（位置）。最后把这个位置上的元素值和前面第i个元素交换。这就完成把挑出的最小值放到前面的过程。 　 关于如何调试，如何输出，和“冒泡”那一节一样。大家一会儿再动手吧。我先在纸上简要模拟一番，这样大家调试起来会更加心中有数。 　 2，5，1，4，3 　 第一遍：找出最小值1（下标为2），将它和第一个元素（下标为0）进行交换，结果： 1,5,2,4,3 第二遍：找出最小值2（下标为2），将它和第二个元素进行交换，结果：1,2,5,4,3 第三遍：1,2,3,4,5 同样，我们发现现在已经排好了，但程序的循环过程还得继续。只是后面将是白忙活，什么也没变。最后一遍是剩下一个1，没得比较，外层循环结束，选择排序完成。 但是，由于选择排序中内层循环完成的工作仅是找出其中的最小值，如果它空转了，只是意味着这些剩下元素中中的第一个元素正好就是最小值，并不意味剩下的元素已经有序。所以我们也不就费心去加什么空转标志了。 　 同冒泡排序一样，选择排序的外层循环要进行 n-1次，而内层为 n / 2 次，所以总比较次数为： (n-1) * n / 2。 交换次数最好时为： 3 * (n-1)，最坏时为 n^2 /4 + 3 *(n-1)。 　 18.2.4 快速排序 （选修） 　 排序的算法还有不少。譬如“插入排序法”和“希尔排序法”。前者有点像我们抓牌，抓到新牌，往手中已有牌的合适位置插入，最终牌都到手时，也排好序。，后者是以它的创造者的名字命名。它们都不是最快的算法。我们不去说它了。还是来说说（一般说来是）号称最快的算法吧。 　 “最快”是有代价的。一个是其算法复杂，不直观，根本不是人脑所擅长的思维方式，因为它要求使用“递归”，我想就算是爱因斯坦在整理扑克时，估计也不爱用这种算法。 　 快速排序的基本思想是分割排序对象。先选择一个值，作为“分割值”。将所有大于该值的元素放到数组的一头，而所有小于该值的元素，放到数组的另一头。这样就把数组按这个分割值划为两段。接下来的事情是对这两段分别再进行前述的操作（找分割值，再划两段）……就这样一划二、二划四、四划八进行下去。直到最每一段都只剩一个元素，排序完成。 　 在分段的过程中，每一个数组又是如何被归到某一段中去呢？采用的也是巧妙的交换方法。 　 假设我们仍然是要进行“从小到大”的排序，那么当有了一个分割值以后，就应该把比分割值大的数扔到数组后头，而比分割值小的数扔到数组前头。在快速排序法中，这个扔的过程是一种“对扔”。即：先找好前面的有哪个数需要扔到后面；再找好后面有哪个数需要扔到前头。两个数都找好了，就把这两个数互相“扔”过去，其实还是交换两个数。知道的人明白我是在说“快速排序”，不知道的人还当我是在说小布和老萨扔板砖哪？ 　 所以，每一遍的分割过程是： 1、指定一个“分割值”。 2、从当前分段的数组前头开始往后找，找到下一个大于分割值的元素（准备扔到后头去）； 3、从当前分段的数组后头开始往前找，找到下一个小于分割值的元素（准备扔到前头去）； 4、交换2，3步找到两个元素 5、反复执行2，3，4，步；直到两端都已找不到要扔的元素。 　 这样，就把数组在逻辑上分为两段，前头的所有小于分割值是一段，后头所有大于分割值的是段，程序接下来递归调用快速排序的函数，分别把这两段都再次进行分割。 函数的递归调用也是我们曾经的“选修课”，如果你有些遗忘，可以回头加以复习。 　 每次的分割值是什么并没有太死的限定，但得在当前段数组元素最小值和最大值（含二者）之间，否则，比如元素是： 5，4，3，而分割值取的是6，就会分不出两段了。我们下面做法比较通用：就取当前段最中间那个元素的值，比如5，4，3中的4。 　 我们按照书写顺序，把数组前端称为“左端”，后端称为“右”端。下面的代码中,left 和 L 用来表示数组前端，而right 和 R 表示后端。 　 void quick(int arr, int left, int right) { ?? int tmp; ?? int L = left, R = right; ?? int V;? //分割值。 ?? ? ?? V = arr[ (L + R) / 2];? //分割值取中间那个元素的值。 　 ?? do ?? { ????? //找前端下一个小于分割值的元素： ????? while (L < right && arr[L] < V)? ????????? L++; 　 ????? //找后端下一个大于分割值的元素： ????? while (R > left && arr[R] > V) ???????? R++; 　 ????? if （L > R) //跑出当前段了，结束本段的“互扔”过程 ??????? break; ???? ????? //开始互换，但 L == R 的情况说明是同一个元素，不用交换。 ????? if ( L < R) ????? { ????????? tmp = arr[L]; ????????? arr[L] = arr[R]; ????????? arr[R] = tmp; ????? }? 　 ????? L++； ????? R--； ?? } ?? while (true); 　 ?? //前面还可以分段，继续划分 ?? //由于前面是在 L > R 情况下break出循环，所以R此时已经比L靠前,所以拿它 ?? //来和是前头的left比较，以确定前面的元素是否超过1个。 ?? if (left < R) ????? quick(left, R);?? //递归调用quick() ?? ?? //后面还可以分段，继续划分 ?? //同理，L此时其实比较靠后。 ?? if (L > right) ????? quick(L, right);? //递归调用quick() } 　 　 快速排序的比较和交换的次数分别为：n * log(n) 和 n * log(n) / 6。远远少于前面的两种排序方法。 　 18.3 小结 必须承认，在我要写上面的这些排序法算法时，我需要小心冀冀地地进行，并多次测试。 我已经将上述三种排序算加入到“扑克牌排序”的程序中，你下载以后，可以通过菜单项“扑克”下找它三者，运行后程序将演示将用各种算法来排序1到K十三张牌。不管是哪一种算法，排序13个数，都是雷霆之速，所以我加了恐怖的延时，这样你看清扑克牌的交换过程。注意：每当交换两张牌时，届面上的第14个空白位置就起到交换中“第三者”的作用。 不过，对于快速排序的演示，你可能还是只能看到前一张后一张的牌在对换，而来不及预想出下一次该换哪两张牌。必竟这一算法复杂得很。 　 我写这些代码需要小心冀冀，说明两点： 第一点，说明像quick这样精妙的算法，确实在理解和记忆上都比较难，而我的水平很一般。 第二点，说明我已经很长时间没有写排序法算法了，虽然我一直在用排序算法，那我的用的代码是从哪里来的？结论是：C，C++库提供的，及CB在其它各种场合提供的现成排序算法很好用，“排序？我们一们在用它，代码现成速度又快，效果还真不错！” 　 现在的quick排序算法还很多，连Windows的API也为我们提供了一份。不过无论是哪个现成的函数，我们现在都用不了，因为这个函数需要一个函数指针做为参数。而我们还没有学到指针（指针啊指针~!@#%$^） 　 (哎！最近我的手得了什么炎，?打字相当困难，只能边说边划再让人敲键盘了，原想8号推出这一课程，可一看电脑，得，9号凌晨0点1分。) 　 关于这一章，怎么说呢？算法是值得大家慢慢推敲的一章，因此，本章是值得花工夫的，但如果你觉得有困难，也是正常的。关于在于一个“慢慢”，我说的“慢慢”就是：“长期地，连续地，一点点来”——“就是: 循！序！渐！进！啦！”台下有个同学暴吼。