📄 第18章 数组（三） ---- 最值与排序.htm
字号:
<P><SPAN lang=en-us>//</SPAN>不使用数组的例子<SPAN lang=en-us>:</SPAN></P>
<P><SPAN lang=en-us>void max1()</SPAN></P>
<P><SPAN lang=en-us>{</SPAN></P>
<P><SPAN lang=en-us> cout << "</SPAN>请输入10个数（每个数输入后加回车<SPAN
lang=en-us>)" << endl;</SPAN></P>
<P> </P>
<P><SPAN lang=en-us> int N,n;</SPAN></P>
<P> </P>
<P><SPAN lang=en-us> cout << "</SPAN>第1个数：<SPAN lang=en-us>"
:</SPAN></P>
<P><SPAN lang=en-us> cin >> N;</SPAN></P>
<P> </P>
<P><SPAN lang=en-us> for(int i = 1; i<10; i++)</SPAN></P>
<P><SPAN lang=en-us> {</SPAN></P>
<P><SPAN lang=en-us> cout <<
"</SPAN>第<SPAN lang=en-us>" << i+1 << "</SPAN>个数<SPAN
lang=en-us>:" ;</SPAN></P>
<P><SPAN lang=en-us> cin >>
n;</SPAN></P>
<P> </P>
<P><SPAN lang=en-us> if( n >
N)</SPAN></P>
<P><SPAN lang=en-us> N =
n;</SPAN></P>
<P><SPAN lang=en-us> }</SPAN></P>
<P> </P>
<P><SPAN lang=en-us> cout << "</SPAN>最大值为：<SPAN lang=en-us>"
<< N << endl;</SPAN></P>
<P><SPAN lang=en-us> </SPAN></P>
<P><SPAN lang=en-us> system("PAUSE");
//</SPAN>让控制台系统暂停。相当于我们以前的<SPAN lang=en-us>cin.get()</SPAN>或<SPAN
lang=en-us> getchar();</SPAN></P>
<P><SPAN lang=en-us>}</SPAN></P>
<P> </P>
<P><SPAN lang=en-us>//</SPAN>使用数组的例子：</P>
<P><SPAN lang=en-us>void max2()</SPAN></P>
<P><SPAN lang=en-us>{</SPAN></P>
<P><SPAN lang=en-us> cout <<
"</SPAN>请输入10个数（每个数输入后加回车<SPAN lang=en-us>)" << endl;</SPAN></P>
<P> </P>
<P><SPAN lang=en-us> int n[10];</SPAN></P>
<P><SPAN lang=en-us> int N;</SPAN></P>
<P><SPAN lang=en-us> </SPAN></P>
<P><SPAN lang=en-us> for(int i = 0; i<10; i++)</SPAN></P>
<P><SPAN lang=en-us> {</SPAN></P>
<P><SPAN lang=en-us> cout <<
"</SPAN>第<SPAN lang=en-us>" << i+1 << "</SPAN>个数：<SPAN
lang=en-us>";</SPAN></P>
<P><SPAN lang=en-us> cin >>
n[i];</SPAN></P>
<P><SPAN lang=en-us> }</SPAN></P>
<P> </P>
<P><SPAN lang=en-us> N = n[0];</SPAN></P>
<P><SPAN lang=en-us> for(int i=1; i<10; i++)</SPAN></P>
<P><SPAN lang=en-us> {</SPAN></P>
<P><SPAN lang=en-us> if(n[i] > N)</SPAN></P>
<P><SPAN lang=en-us> N =
n[i];</SPAN></P>
<P><SPAN lang=en-us> }</SPAN></P>
<P> </P>
<P><SPAN lang=en-us> cout << "</SPAN>最大值为：<SPAN lang=en-us>"
<< N << endl;</SPAN></P>
<P><SPAN lang=en-us> </SPAN></P>
<P><SPAN lang=en-us> system("PAUSE"); //</SPAN>让控制台系统暂停。</P>
<P><SPAN lang=en-us>}</SPAN></P>
<P> </P>
<P>这样就完成了求最大值实例，如果是要求求最小值呢？改动仅在于那个if判断条件：</P>
<P> </P>
<P>……</P>
<P><SPAN lang=en-us>N = n[0]; //</SPAN>一开始假设第一个元素就是最小值</P>
<P> </P>
<P><SPAN lang=en-us>for(</SPAN>……）</P>
<P><SPAN lang=en-us>{</SPAN></P>
<P><SPAN lang=en-us> if (n[i] <B><FONT color=#ff0000><</FONT></B>
N) //</SPAN>如果有元素比我们假设的最小值还小，那就让最小值等于它吧</P>
<P><SPAN lang=en-us> N = n[i];</SPAN></P>
<P><SPAN lang=en-us>}</SPAN></P>
<P>……</P>
<P> </P>
<P>这套题目我没有提供实际代码，大家找开CB自已完成吧。重要的是，在调通程序之后，认真地比较两种处理方法之间的异同。</P>
<P>结论应该是：“算法的抽象逻辑是一样的，只是用在于不同的数据结构上，会有不同的实现”。前者只使用简单的数据类型，所以它不得不在一边输入的情况下，一边求最大值；而后者采用了数组，所以可以从容地先完成输入工作，然后再求最大值。</P>
<P>当算法经较复杂时，采用良好的数据结构的重要性就开始体现，比如下面的排序，我们必须使用数组或其它更复杂的数据。否则就实现不了。</P>
<P> </P>
<H3><B><A name=18.2>18.2</A> 将数组元素排序</B></H3>
<P>
<P>排序，一个经典教学课程。
<P>排序，一个在超高频的实用算法。
<P>第一点是说，我们必须去学。第二点是说，像这样一个实用算法以，事实上C,C++肯定都为我们写好了，以库函数等形式提供给我们使用，而且，这些写好的代码，肯定是最优秀的实现。
<P>可是我们还是要学，而且是从最笨“冒泡算法”学起。所谓的最笨，是指效率差的。
<P>
<P>学习的原因：1、前面说了，为了锻炼我们的逻辑思维。2、为了在某些时候，我们可以对排过程做更多的控制。
<P>
<H4><B><A name=18.2.1>18.2.1</A> 现实算法与程序算法的不同</B></H4>
<P>
<P>大家都是这么整理扑克牌：把54张摊开放在桌面，然后不断地调整各张牌的位置，并把已经有序的牌放到另外一个位置。
<P>生活中的各种算法一般不用考虑“内存”的问题。比如上面的问题，54牌每一张都要占用一点桌面，这算是固定需要的内存，而在“腾挪”各张牌，使之渐渐变得有序的过程中，还需要开辟新的空间，包括手里抓着的牌，即手心也算是一个内存。
<P>程序排序，要求既要占用内存少，又要速度快。这是衡量一个算法是否优秀的两个基本点。
<P>
<P>若是应用到人整理牌这一例子，则除了实现将54张牌按次序（牌值和牌花）排好以外，还需另有要求：
<P>1、除了54张牌一开始占用的桌面，及你的一个手心以外，你在整理的过程中，不能让牌再占用新的桌面空间。
<P>2、要求“比较两张牌大小”“交换两张的位置”等过程都尽量地少。
<P>
<P>你可以拿出家里的扑克牌，现在就开始按上面的要求进行手工排序。也可以下载网站上的“扑克排序”的程序，通过它来模拟手工排序：鼠标点击某一张牌，该牌将移到当前的空位上。（正工学员下载课程包中已含该程序）
<P>
<H4><B><A name=18.2.2>18.2.2</A> 冒泡排序</B></H4>
<P>
<P>“冒泡”是什么意思？湖底有时会冒出一个气泡，气泡刚在湖底时，是很小的，在向上浮的过程中，才一点地慢慢变大。学过高中的物理的人，应该不难解释这一现象。冒泡排序的过程有点类似这个过程，每前进一步，值就大一点。
<P>
<P>排序当然有两个方向，一种是从小排到大，一种是从大排到小。大多数教科书里都讲第一种，我们也如此。这样一来，冒泡排序法就改为“沉泡法”了，较大值一点点跑到数组中的末尾。
<P>
<P>一般教科书里也会说，冒泡排序法是人们最熟悉，及最直观的排序法，我可不这样认为。或许老外在生活中用的是这种最笨的排序法？我猜想，大家在生活中99%使用后面要讲的“选择”排序法。
<P>
<P>冒泡排序是这么一个过程(从小到大):
<P>
<P>1、比较相邻的两个元素，如果后面的比前面小，就对调二者。反复比较，到最后两个元素。结果，最大值就跑到了最末位置。
<P>2、反复第一步，直到所有较大值都跑到靠后的位置。
<P>
<P>看一眼例子：
<P>
<P>2，5，1，4，3
<P>
<P>第一遍：
<P>·比较第一对相邻元素：2，5，发现后面的5并不比2小，所以不做处理。 序列保持不变：2，5，1，4，3
<P>·继续比较后两对元素：5，1，发现后面的1比前面的5小，所以对调二者。现在，序列变为：2，<FONT
color=#ff0000>1，5</FONT>，4，3
<P>·继续比较后两对元素：5，4……对调，于是：2，1，<FONT color=#ff0000>4，5</FONT>，3
<P>·继续比较后两对元素：5，3……对调，于是：<SPAN lang=en-us>2</SPAN>，<SPAN
lang=en-us>1</SPAN>，<SPAN lang=en-us>4</SPAN>，<FONT color=#ff0000><SPAN
lang=en-us>3</SPAN>，<SPAN lang=en-us>5</SPAN> <SPAN
lang=en-us><</SPAN>-----<SPAN lang=en-us>
</SPAN>OK,现在最大值5跑到最尾处了。</FONT>
<P>
<P>大泡泡“<SPAN lang=en-us>5</SPAN>”浮出来了，但前面的<SPAN
lang=en-us>2,1,4,3,</SPAN>还是没有排好，没事，再来一遍，不过，由于最后一个元素肯定是最大值了，所以我们这回只排到倒数第二个即可。
<P>
<P>第二遍：
<P>·比较第一对相邻元素：2，1，发现1比2小，所以对调：<SPAN lang=en-us><FONT
color=#ff0000>1,2</FONT>,4,3,5</SPAN>
<P>·继续比较后两对元素：2，4，不用处理，因为后面的数比较大。序列还是：<SPAN lang=en-us>1,2,4,3,5</SPAN>
<P>·继续 4，3，对调：<SPAN lang=en-us>1,2,<FONT
color=#ff0000>3,4</FONT>,5</SPAN>。
<P>
<P>前面说，5 不用再参加比较了。现在的序列是1，2，3，4，5。接下来，我们再来一遍：
<P>
<P>第三遍：
<P>·比较第一对相邻元素：1，2：不用对调。
<P>……等等……
<P>有人说，现在已经是1，2，3，4，5了，完全是排好序了啊，何必再来进行呢？我们确实是看出前面1，2，3也井然有序了，但对于程序来说，它<B>只能明确地知道自己已经排好了两个数</B>：4，5，并不知道的1，2，3凑巧也排好了。所以它必须再排两次，直到确认把3和2都已推到合适的位置上。最后剩一个数是1，因为只有一个数，没得比，所以这才宣告排序结束。
<P>
<P>那么到底要排几遍？看一看前面的“第一遍”、“第二遍”的过程你可发现，每进行一遍，可以明确地将一个当前的最大值推到末尾，所以如果排<SPAN
lang=en-us> Count </SPAN>个数，则应排<SPAN lang=en-us> </SPAN>Count<SPAN
lang=en-us> </SPAN>遍。当然，最后一遍是空走，因为仅剩一个元素，没得比较。
<P>
<P>下面就动手写冒泡排序法的函数。写成函数是因为我们希望这个排序法可处理任意个元素的数组。
<P>
<P><SPAN lang=en-us>//</SPAN>冒泡排序<SPAN lang=en-us>(</SPAN>从小到大<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 bubble(int num[],int count)</SPAN>
<P><SPAN lang=en-us>{</SPAN>
<P><SPAN lang=en-us> int tmp;</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> 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>
//</SPAN>对调两个数，需要有<SPAN lang=en-us>"</SPAN>第三者<SPAN lang=en-us>"</SPAN>参以
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -