?? 教學--第18章 數組（三） ---- 最值與排序.htm
字號:
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>參以
<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>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -