📄 第18章 数组（三） ---- 最值与排序.htm
字号:
<P><SPAN
lang=en-us>
tmp = num[j+1];</SPAN>
<P><SPAN
lang=en-us>
num[j+1] = num[j];</SPAN>
<P><SPAN
lang=en-us>
num[j] = tmp;</SPAN>
<P><SPAN
lang=en-us> }
</SPAN>
<P><SPAN lang=en-us> }</SPAN>
<P><SPAN lang=en-us> }
</SPAN>
<P><SPAN lang=en-us>}</SPAN>
<P>
<P>注意在内层循环中j的结束值是<SPAN lang=en-us> count - i - 1</SPAN>。
要理解这段代码，明白为什么结束在<SPAN lang=en-us>count - i
-1</SPAN>？如果你忘了如何在CB进行代码调试，如果设置断点，如何单步运行，如何观察变量的值，那么你需要“严重”复习前面有关“调试”的章节；如果你一直是高度着每一章的程序到现在，那么你可以继续下面的内容。
<P>
<P>排序函数写出一个了，如何调试这个函数？在CB里新建一空白控制台程序，然后在主函数里，让我们写一些代码来调用这个函数，并且观察排序结果。
<P>
<P><SPAN lang=en-us>#include <iostream.h></SPAN>
<P>……
<P><SPAN lang=en-us>void bubble(int num[],int count)</SPAN>
<P><SPAN lang=en-us>{</SPAN>
<P><SPAN lang=en-us> </SPAN>……
<P><SPAN lang=en-us>}</SPAN>
<P>
<P><SPAN lang=en-us>int main() //</SPAN>我实在有些懒得写<SPAN
lang=en-us>main</SPAN>里两个参数，反正它们暂时对我们都没有用，
<P><SPAN
lang=en-us>
//</SPAN>反正CB会为你自动生成，所以从此刻起，我不写了<SPAN lang=en-us>,</SPAN>除非有必要。
<P><SPAN lang=en-us>{</SPAN>
<P> <SPAN lang=en-us> int values[] = {2,5,1,4,3};</SPAN>
<P><SPAN lang=en-us> int count = sizeof(values[]) /
sizeof(values[0]);</SPAN>
<P><SPAN lang=en-us> bubble(value,sizeof);</SPAN>
<P><SPAN lang=en-us>}</SPAN>
<P>
<P>你要做的工作是单步跟踪上面的代码，看看整个流程是不是像我前面不厌其烦的写的“第一遍第二遍第三遍”所描述的。
<P>
<P>完成上面的工作了吗？全部过程下来，只花20分钟应该算是速度快或者不认真的了（天知道你是哪一种？天知道你到底是不是没有完成就来骗我？）。现在让这个程序有点输出。我们加一个小小的函数：
<P>
<P><SPAN lang=en-us>//</SPAN>输出数组的元素值
<P><SPAN lang=en-us>//num :</SPAN>待输出的数组
<P><SPAN lang=en-us>//count:</SPAN>元素个数
<P><SPAN lang=en-us>void printArray(int num[],int count)</SPAN>
<P><SPAN lang=en-us>{</SPAN>
<P><SPAN lang=en-us> for(int i = 0; i < count; i++)</SPAN>
<P><SPAN lang=en-us> {</SPAN>
<P><SPAN lang=en-us> count << num[i]
<< ",";</SPAN>
<P><SPAN lang=en-us> }</SPAN>
<P>
<P><SPAN lang=en-us> cout << endl;</SPAN>
<P><SPAN lang=en-us>}</SPAN>
<P>
<P>把这个函数加到<SPAN lang=en-us>main()</SPAN>函数头之前，然后我们用它来输出：
<P><SPAN lang=en-us>int main() //</SPAN>我实在有些懒得写<SPAN
lang=en-us>main</SPAN>里两个参数，反正它们暂时对我们都没有用，
<P><SPAN
lang=en-us>
//</SPAN>反正CB会为你自动生成，所以从此刻起，我不写了<SPAN lang=en-us>,</SPAN>除非有必要。
<P><SPAN lang=en-us>{</SPAN>
<P> <SPAN lang=en-us> int values[] = {2,5,1,4,3};</SPAN>
<P><SPAN lang=en-us> int count = sizeof(values[]) /
sizeof(values[0]);</SPAN>
<P><SPAN lang=en-us> </SPAN>
<P><SPAN lang=en-us> cout << "</SPAN>排序之前：<SPAN
lang=en-us>" << endl;</SPAN>
<P><SPAN lang=en-us> printArray(values,count);</SPAN>
<P>
<P><SPAN lang=en-us> //</SPAN>冒泡排序：
<P><SPAN lang=en-us> bubble(value,sizeof);</SPAN>
<P>
<P><SPAN lang=en-us> cout << "</SPAN>排序之后<SPAN
lang=en-us>:" << endl;</SPAN>
<P><SPAN lang=en-us> printArray(values,count);</SPAN>
<P>
<P><SPAN lang=en-us> system("PAUSE");</SPAN>
<P><SPAN lang=en-us>}</SPAN>
<P>
<P>后面要讲的其它排序法也将用这个<SPAN lang=en-us>printArray()</SPAN>来作输出。
<P>
<P>冒泡排序是效率最差劲的方法（速度慢），不过若论起不另外占用内存，则它当属第一。在交换元素中使用了一个临时变量（第三者），还有两个循环因子i和j，这些都属于必须品，其它的它一个变量也没多占。
<P>
<P>我们现在讲讲如何避免数据其实已经排好，程序仍然空转的的局面。
<P>首先要肯定一点，至少一遍的空转是不可避免的，这包括让人来排，因为你要发现结果已是1，2，3，4，5了，你也是用眼睛从头到尾抄了一遍（如果你视力不好，说不定还要扫两遍呢）。
<P>接下来一点，我们来看看除了第一遍空转，后面的是否可以避免。冒泡排序法的空转意味着什么？因为算法是拿相邻的两个比较，一发现次序不合“从小到大”的目的（小的在大的后头），就进行对调。所以如果这个对调一次也没有进行，那就说明后面的元素必然是已经完全有序了，可以放心地结束。
<P>
<P>让我们来加个变量，用于标志刚刚完成的这一遍是否空转，如果是空转，就让代码跳出循环。
<P>
<P><SPAN lang=en-us>//</SPAN>冒泡排序<SPAN
lang=en-us>(</SPAN>从小到大，且加了空转判断<SPAN lang=en-us>)</SPAN>：
<P><SPAN lang=en-us>void bubble(int num[],int count)</SPAN>
<P><SPAN lang=en-us>{</SPAN>
<P><SPAN lang=en-us> int tmp;</SPAN>
<P><SPAN lang=en-us> bool swapped; //</SPAN>有交换吗？
<P>
<P><SPAN lang=en-us> //</SPAN>要排<SPAN
lang=en-us>Count</SPAN>个数，则应排<SPAN lang=en-us>Count</SPAN>遍：
<P><SPAN lang=en-us> for (int i = 0; i < count;
i++)</SPAN>
<P><SPAN lang=en-us> {</SPAN>
<P><SPAN lang=en-us>
//</SPAN>第一遍开始之前，我们都假充本遍可能没有交换（空转）：
<P><SPAN lang=en-us> swapped =
false;</SPAN>
<P>
<P><SPAN lang=en-us> for(int j = 0; j
< <B>count - i - 1</B>; j++)</SPAN>
<P><SPAN lang=en-us> {</SPAN>
<P><SPAN
lang=en-us>
//</SPAN>比较相邻的两个数：
<P><SPAN
lang=en-us>
if(num[j+1] < num[j]) //</SPAN>后面的数小于前面的数
<P><SPAN
lang=en-us>
{</SPAN>
<P><SPAN
lang=en-us>
swapped = true; //</SPAN>还是有交换
<P><SPAN
lang=en-us>
</SPAN>
<P><SPAN
lang=en-us>
//</SPAN>对调两个数，需要有<SPAN lang=en-us>"</SPAN>第三者<SPAN lang=en-us>"</SPAN>参以
<P><SPAN
lang=en-us>
tmp = num[j+1];</SPAN>
<P><SPAN
lang=en-us>
num[j+1] = num[j];</SPAN>
<P><SPAN
lang=en-us>
num[j] = tmp;</SPAN>
<P><SPAN
lang=en-us> }
</SPAN>
<P><SPAN lang=en-us> }</SPAN>
<P><SPAN lang=en-us> </SPAN>
<P><SPAN lang=en-us> if
(!swapped)</SPAN>
<P><SPAN lang=en-us>
break;</SPAN>
<P><SPAN lang=en-us> }
</SPAN>
<P><SPAN lang=en-us>}</SPAN>
<P>
<P>加了<SPAN
lang=en-us>swapped</SPAN>标志，这个算法也快不了多少，甚至会慢也有可能。冒泡排序还有一些其它的改进的可能，但同样作用不大，并且会让其丧失仅有优点“代码简单直观”。所以我个人认为真有需要使用冒泡排序时，仅用最原汁原味的“泡”就好。必竟，你选择了冒泡算法，就说明你对本次排序的速度并无多高的要求。
<P>
<P>对于n个元素，原汁原味的“冒泡排序”算法要做的比较次数是固定的： （n<SPAN lang=en-us> -
1</SPAN>）<SPAN lang=en-us>* n/2 </SPAN>次的比较。
<P>交换次数呢？如果一开始就是排好序的数据，则交换次数为0。
<P>一般情况下为<SPAN lang=en-us> 3 * (n - 1) * n / 4;</SPAN>最惨时（逆序）为<SPAN
lang=en-us>3 * (n - 1) * n / 2</SPAN>。
<P>
<P>冒完泡以后——情不自禁看一眼窗台罐头瓶里那只胖金鱼——让我们开始中国人最直观的选择排序法吧。对了，补一句，如果你看到有人在说“上推排序”，那么你要知道，“上推排序”是“冒泡排序”的另一种叫法，惟一的区别是：它不会让我们联想到金鱼。
<P>
<H4><B><A name=18.2.3>18.2.3</A> 选择排序</B></H4>
<P>
<P>本章前头我们讲了“求最值”的算法，包括最大值和最小值。其实，有了求最值的算法，排序不也完成了一半？想像一下桌子上摊开着牌，第一次我们从中换挑出大王放在手上，第二次我们挑出小王，然后是黑桃老K……黑桃Q，如此下去直到小A，手中的牌不也就已经排好次序了？
<P>
<P>每次从中选出最大值或最小值，依此排成序，这就是选择排序法的过程描述。
<P>
<P>不过，上述的过程有一点不合要求。我们说过手中只能过一张牌。因此，在程序实现时，我们找出一个最大值之后，就要把它放到数组中最末。那数组中最末位置原来的值？当然是把它放到最大值原来所在位置了。
<P>为了再稍稍直观点，我们改为：每次找的是最小值，找出后改为放到数组前头。
<P>
<P>//选择排序（从小到大）
<P><SPAN lang=en-us>void select(int num[], int count)</SPAN>
<P><SPAN lang=en-us>{</SPAN>
<P><SPAN lang=en-us> int tmp;</SPAN>
<P><SPAN lang=en-us> int minIndex; //</SPAN>用于记住最小值的下标
<P>
<P><SPAN lang=en-us> for (int i = 0; i < count;
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -