📄 第18章 数组（三） ---- 最值与排序.htm
字号:
i++)</SPAN>
<P><SPAN lang=en-us> {</SPAN>
<P><SPAN lang=en-us>
minIndex = i; //</SPAN>每次都假设i所在位置的元素是最小的
<P><SPAN lang=en-us> for
(int j = i + 1; j < count; j++) //j </SPAN>从<SPAN
lang=en-us>i+1</SPAN>开始，<SPAN lang=en-us>i</SPAN>之前的都已排好<SPAN
lang=en-us>,</SPAN>而<SPAN lang=en-us>i</SPAN>是本次的第一个元素
<P><SPAN lang=en-us>
{</SPAN>
<P><SPAN
lang=en-us>
if (num[minIndex] < num[j]) </SPAN>
<P><SPAN
lang=en-us>
minIndex = j;</SPAN>
<P><SPAN lang=en-us>
}</SPAN>
<P>
<P><SPAN lang=en-us>
//</SPAN>把当前最小元素和前面第i个元素交换：
<P><SPAN lang=en-us> if(minIndex
!= i)</SPAN>
<P><SPAN lang=en-us> {</SPAN>
<P><SPAN
lang=en-us>
tmp = num[i];</SPAN>
<P><SPAN
lang=en-us>
num[i] = num[minIndex];</SPAN>
<P><SPAN
lang=en-us>
num[minIndex] = tmp;</SPAN>
<P><SPAN lang=en-us> }</SPAN>
<P><SPAN lang=en-us> }</SPAN>
<P><SPAN lang=en-us>}</SPAN>
<P>
<P>同样是两层循环，内层循环非常类似于前面讲的求最值的的方法，重要的区别在于求最小值时，可以直接用N记下最小值，而我们这里是记下最小值元素的下标（位置）。最后把这个位置上的元素值和前面第i个元素交换。这就完成把挑出的最小值放到前面的过程。
<P>
<P>关于如何调试，如何输出，和“冒泡”那一节一样。大家一会儿再动手吧。我先在纸上简要模拟一番，这样大家调试起来会更加心中有数。
<P>
<P>2，5，1，4，3
<P>
<P>第一遍：找出最小值1（下标为2），将它和第一个元素（下标为0）进行交换，结果：<SPAN lang=en-us> <FONT
color=#ff0000>1</FONT>,5,<FONT color=#ff0000>2</FONT>,4,3</SPAN>
<P>第二遍：找出最小值2（下标为2），将它和第二个元素进行交换，结果：<SPAN lang=en-us>1,<FONT
color=#ff0000>2</FONT>,<FONT color=#ff0000>5</FONT>,4,3</SPAN>
<P>第三遍：<SPAN lang=en-us>1,2,<FONT color=#ff0000>3</FONT>,4,<FONT
color=#ff0000>5</FONT></SPAN><FONT color=#ff0000> </FONT>
<P>同样，我们发现现在已经排好了，但程序的循环过程还得继续。只是后面将是白忙活，什么也没变。最后一遍是剩下一个1，没得比较，外层循环结束，选择排序完成。
<P>但是，由于选择排序中内层循环完成的工作仅是找出其中的最小值，如果它空转了，只是意味着这些剩下元素中中的第一个元素正好就是最小值，并不意味剩下的元素已经有序。所以我们也不就费心去加什么空转标志了。
<P>
<P>同冒泡排序一样，选择排序的外层循环要进行<SPAN lang=en-us> n-1</SPAN>次，而内层为<SPAN lang=en-us>
n / 2</SPAN> 次，所以总比较次数为：<SPAN lang=en-us> (n-1) * n / 2</SPAN>。
<P>交换次数最好时为：<SPAN lang=en-us> 3 * (n-1)</SPAN>，最坏时为<SPAN lang=en-us> n^2
/4 + 3 *(n-1)</SPAN>。
<P>
<H3><B><SPAN lang=en-us><A name=18.2.4>18.2.4</A> </SPAN>快速排序
</B>（选修）</H3>
<P>
<P>排序的算法还有不少。譬如“插入排序法”和“希尔排序法”。前者有点像我们抓牌，抓到新牌，往手中已有牌的合适位置插入，最终牌都到手时，也排好序。，后者是以它的创造者的名字命名。它们都不是最快的算法。我们不去说它了。还是来说说（一般说来是）号称最快的算法吧。
<P>
<P>“最快”是有代价的。一个是其算法复杂，不直观，根本不是人脑所擅长的思维方式，因为它要求使用“递归”，我想就算是爱因斯坦在整理扑克时，估计也不爱用这种算法。
<P>
<P>快速排序的基本思想是分割排序对象。先选择一个值，作为“分割值”。将所有大于该值的元素放到数组的一头，而所有小于该值的元素，放到数组的另一头。这样就把数组按这个分割值划为两段。接下来的事情是对这两段分别再进行前述的操作（找分割值，再划两段）……就这样一划二、二划四、四划八进行下去。直到最每一段都只剩一个元素，排序完成。
<P>
<P>在分段的过程中，每一个数组又是如何被归到某一段中去呢？采用的也是巧妙的交换方法。
<P>
<P>假设我们仍然是要进行“从小到大”的排序，那么当有了一个分割值以后，就应该把比分割值大的数扔到数组后头，而比分割值小的数扔到数组前头。在快速排序法中，这个扔的过程是一种“对扔”。即：先找好前面的有哪个数需要扔到后面；再找好后面有哪个数需要扔到前头。两个数都找好了，就把这两个数互相“扔”过去，其实还是交换两个数。知道的人明白我是在说“快速排序”，不知道的人还当我是在说小布和老萨扔板砖哪？
<P>
<P>所以，每一遍的分割过程是：
<P>1、指定一个“分割值”。
<P>2、从当前分段的数组前头开始往后找，找到下一个大于分割值的元素（准备扔到后头去）；
<P>3、从当前分段的数组后头开始往前找，找到下一个小于分割值的元素（准备扔到前头去）；
<P>4、交换2，3步找到两个元素
<P>5、反复执行2，3，4，步；直到两端都已找不到要扔的元素。
<P>
<P>这样，就把数组在逻辑上分为两段，前头的所有小于分割值是一段，后头所有大于分割值的是段，程序接下来递归调用快速排序的函数，分别把这两段都再次进行分割。
<P>
<P>函数的递归调用也是我们曾经的“选修课”，如果你有些遗忘，可以回头加以复习。
<P>
<P>每次的分割值是什么并没有太死的限定，但得在当前段数组元素最小值和最大值（含二者）之间，否则，比如元素是：<SPAN lang=en-us>
</SPAN>5，<SPAN
lang=en-us>4</SPAN>，3，而分割值取的是6，就会分不出两段了。我们下面做法比较通用：就取当前段最中间那个元素的值，比如5，4，3中的4。
<P>
<P>我们按照书写顺序，把数组前端称为“左端”，后端称为“右”端。下面的代码中<SPAN lang=en-us>,left
</SPAN>和<SPAN lang=en-us> L</SPAN> 用来表示数组前端，而<SPAN lang=en-us>right
</SPAN>和<SPAN lang=en-us> R </SPAN>表示后端。
<P>
<P><SPAN lang=en-us>void quick(int arr, int left, int right)</SPAN>
<P><SPAN lang=en-us>{</SPAN>
<P><SPAN lang=en-us> int tmp;</SPAN>
<P><SPAN lang=en-us> int L = left, R = right;</SPAN>
<P><SPAN lang=en-us> int V; //</SPAN>分割值。
<P><SPAN lang=en-us> </SPAN>
<P> <SPAN lang=en-us>V = arr[ (L + R) / 2];
//</SPAN>分割值取中间那个元素的值。
<P>
<P> <SPAN lang=en-us>do</SPAN>
<P><SPAN lang=en-us> {</SPAN>
<P><SPAN lang=en-us>
//</SPAN>找前端下一个小于分割值的元素：
<P> <SPAN lang=en-us>while</SPAN> <SPAN
lang=en-us>(L < right && arr[L] < V) </SPAN>
<P><SPAN lang=en-us>
L++; </SPAN>
<P>
<P><SPAN lang=en-us>
//</SPAN>找后端下一个大于分割值的元素：
<P><SPAN lang=en-us> while</SPAN> <SPAN
lang=en-us>(R > left && arr[R] > V)</SPAN>
<P><SPAN lang=en-us>
R++;</SPAN>
<P>
<P><SPAN lang=en-us> if</SPAN> （L >
R<SPAN lang=en-us>) //</SPAN>跑出当前段了，结束本段的“互扔”过程
<P><SPAN lang=en-us>
break;</SPAN>
<P><SPAN lang=en-us> </SPAN>
<P> //开始互换，但 <SPAN lang=en-us>L
=</SPAN>=<SPAN lang=en-us> R</SPAN> 的情况说明是同一个元素，不用交换。
<P><SPAN lang=en-us> if ( L < R) </SPAN>
<P><SPAN lang=en-us> {</SPAN>
<P><SPAN lang=en-us>
tmp = arr[L];</SPAN>
<P><SPAN lang=en-us>
arr[L] = arr[R];</SPAN>
<P><SPAN lang=en-us>
arr[R] = tmp;</SPAN>
<P><SPAN lang=en-us> } </SPAN>
<P>
<P> L++；
<P> R--；
<P><SPAN lang=en-us> }</SPAN>
<P><SPAN lang=en-us> while (true);</SPAN>
<P>
<P><SPAN lang=en-us> //</SPAN>前面还可以分段，继续划分
<P><SPAN lang=en-us> //</SPAN>由于前面是在<SPAN lang=en-us> L > R
</SPAN>情况下<SPAN lang=en-us>break</SPAN>出循环，所以R此时已经比L靠前<SPAN
lang=en-us>,</SPAN>所以拿它
<P> //来和是前头的<SPAN lang=en-us>left</SPAN>比较，以确定前面的元素是否超过1个。
<P> <SPAN lang=en-us>if (left < R)</SPAN>
<P><SPAN lang=en-us> quick(left,
R); //</SPAN>递归调用<SPAN lang=en-us>quick()</SPAN>
<P><SPAN lang=en-us> </SPAN>
<P><SPAN lang=en-us> //</SPAN>后面还可以分段，继续划分
<P><SPAN lang=en-us> //</SPAN>同理，L此时其实比较靠后。
<P><SPAN lang=en-us> if (L > right)</SPAN>
<P><SPAN lang=en-us> quick(L, right);
//</SPAN>递归调用<SPAN lang=en-us>quick()</SPAN>
<P><SPAN lang=en-us>}</SPAN>
<P>
<P>
<P>快速排序的比较和交换的次数分别为：<SPAN lang=en-us>n * log(n) </SPAN>和<SPAN lang=en-us>
n * log(n) / 6</SPAN>。远远少于前面的两种排序方法。
<P>
<H3><A name=18.3><SPAN lang=en-us>18.3</SPAN></A> 小结</H3>
<P>必须承认，在我要写上面的这些排序法算法时，我需要小心冀冀地地进行，并多次测试。<SPAN lang=en-us>
</SPAN>我已经将上述三种排序算加入到“扑克牌排序”的程序中，你下载以后，可以通过菜单项“扑克”下找它三者，运行后程序将演示将用各种算法来排序1到K十三张牌。不管是哪一种算法，排序13个数，都是雷霆之速，所以我加了恐怖的延时，这样你看清扑克牌的交换过程。注意：每当交换两张牌时，届面上的第14个空白位置就起到交换中“第三者”的作用。
<P>不过，对于快速排序的演示，你可能还是只能看到前一张后一张的牌在对换，而来不及预想出下一次该换哪两张牌。必竟这一算法复杂得很。
<P>
<P>我写这些代码需要小心冀冀，说明两点：
<P>第一点，说明像<SPAN lang=en-us>quick</SPAN>这样精妙的算法，确实在理解和记忆上都比较难，而我的水平很一般。
<P>第二点，说明我已经很长时间没有写排序法算法了，虽然我一直在用排序算法，那我的用的代码是从哪里来的？结论是：C，C++库提供的，及CB在其它各种场合提供的现成排序算法很好用，“排序？我们一们在用它，代码现成速度又快，效果还真不错！”
<P>
<P>现在的<SPAN lang=en-us>quick</SPAN>排序算法还很多，连<SPAN
lang=en-us>Windows</SPAN>的API也为我们提供了一份。不过无论是哪个现成的函数，我们现在都用不了，因为这个函数需要一个函数指针做为参数。而我们还没有学到指针（指针啊指针<SPAN
lang=en-us>~!@#%$^</SPAN>）
<P>
<P><SPAN lang=en-us>(</SPAN>哎！最近我的手得了什么炎，<SPAN
lang=en-us> </SPAN>打字相当困难，只能边说边划再让人敲键盘了，原想8号推出这一课程，可一看电脑，得，9号凌晨0点1分。<SPAN
lang=en-us>)</SPAN>
<P>
<P>关于这一章，怎么说呢？算法是值得大家慢慢推敲的一章，因此，本章是值得花工夫的，但如果你觉得有困难，也是正常的。关于在于一个“慢慢”，我说的“慢慢”就是：“长期地，连续地，一点点来”——“就是<SPAN
lang=en-us>:
</SPAN>循！序！渐！进！啦！”台下有个同学暴吼。</P></TD></TR></TBODY></TABLE></CENTER></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -