?? 教學--第18章 數組（三） ---- 最值與排序.htm
字號:
<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;
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 + -