?? 教學--第18章 數組（三） ---- 最值與排序.htm
字號:
<H4><A name=18.1.2>18.1.2</A> 實例</H4>
<P> </P>
<P><B>要求：</B></P>
<P>1、不使用數組，實現讓用戶輸入10個數，然后輸出其中最大值。</P>
<P>2、同1，但要求使用數組。</P>
<P> </P>
<P>既然是兩個小題，我們就分別寫兩個函數吧。</P>
<P> </P>
<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>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -