CC++筆試面試題目匯總3_各種排序算法.doc

.C/C+筆試面試題目匯總3各種排序算法 原文:/u/1222/showart_318070.html排序算法是一種基本并且常用的算法。由于實(shí)際工作中處理的數(shù)量巨大，所以排序算法對(duì)算法本身的速度要求很高。而一般我們所謂的算法的性能主要是指算法的復(fù)雜度，一般用O方法來表示。在后面我將給出詳細(xì)的說明。對(duì)于排序的算法我想先做一點(diǎn)簡(jiǎn)單的介紹，也是給這篇文章理一個(gè)提綱。我將按照算法的復(fù)雜度，從簡(jiǎn)單到難來分析算法。第一部分是簡(jiǎn)單排序算法，后面你將看到他們的共同點(diǎn)是算法復(fù)雜度為O(N*N)（因?yàn)闆]有使用word,所以無法打出上標(biāo)和下標(biāo)）。第二部分是高級(jí)排序算法，復(fù)雜度為O(Log2(N)。這里我們只介紹一種算法。另外還有幾種算法因?yàn)樯婕皹渑c堆的概念，所以這里不于討論。第三部分類似動(dòng)腦筋。這里的兩種算法并不是最好的（甚至有最慢的），但是算法本身比較奇特，值得參考（編程的角度）。同時(shí)也可以讓我們從另外的角度來認(rèn)識(shí)這個(gè)問題。第四部分是我送給大家的一個(gè)餐后的甜點(diǎn)一個(gè)基于模板的通用快速排序。由于是模板函數(shù)可以對(duì)任何數(shù)據(jù)類型排序（抱歉，里面使用了一些論壇專家的呢稱）。一、簡(jiǎn)單排序算法由于程序比較簡(jiǎn)單，所以沒有加什么注釋。所有的程序都給出了完整的運(yùn)行代碼，并在我的VC環(huán)境下運(yùn)行通過。因?yàn)闆]有涉及MFC和WINDOWS的內(nèi)容，所以在BORLAND C+的平臺(tái)上應(yīng)該也不會(huì)有什么問題的。在代碼的后面給出了運(yùn)行過程示意，希望對(duì)理解有幫助。1.冒泡法：（Gilbert：點(diǎn)這里有視頻）這是最原始，也是眾所周知的最慢的算法了。他的名字的由來因?yàn)樗墓ぷ骺磥硐笫敲芭荩?include void BubbleSort(int* pData,int Count) int iTemp; for(int i=1;i=i;j-) if(pDatajpDataj-1) iTemp = pDataj-1; pDataj-1 = pDataj; pDataj = iTemp; void main() int data = 10,9,8,7,6,5,4; BubbleSort(data,7); for (int i=0;i7;i+) coutdatai ; cout10,9,7,8-10,7,9,8-7,10,9,8(交換3次)第二輪：7,10,9,8-7,10,8,9-7,8,10,9(交換2次)第一輪：7,8,10,9-7,8,9,10(交換1次)循環(huán)次數(shù)：6次交換次數(shù)：6次其他：第一輪：8,10,7,9-8,10,7,9-8,7,10,9-7,8,10,9(交換2次)第二輪：7,8,10,9-7,8,10,9-7,8,10,9(交換0次)第一輪：7,8,10,9-7,8,9,10(交換1次)循環(huán)次數(shù)：6次交換次數(shù)：3次上面我們給出了程序段，現(xiàn)在我們分析它：這里，影響我們算法性能的主要部分是循環(huán)和交換，顯然，次數(shù)越多，性能就越差。從上面的程序我們可以看出循環(huán)的次數(shù)是固定的，為1+2+.+n-1。寫成公式就是1/2*(n-1)*n?，F(xiàn)在注意，我們給出O方法的定義： 若存在一常量K和起點(diǎn)n0，使當(dāng)n=n0時(shí)，有f(n)=K*g(n),則f(n) = O(g(n)。（呵呵，不要說沒學(xué)好數(shù)學(xué)呀，對(duì)于編程數(shù)學(xué)是非常重要的?。┈F(xiàn)在我們來看1/2*(n-1)*n，當(dāng)K=1/2，n0=1，g(n)=n*n時(shí)，1/2*(n-1)*n=1/2*n*n=K*g(n)。所以(n)=O(g(n)=O(n*n)。所以我們程序循環(huán)的復(fù)雜度為O(n*n)。再看交換。從程序后面所跟的表可以看到，兩種情況的循環(huán)相同，交換不同。其實(shí)交換本身同數(shù)據(jù)源的有序程度有極大的關(guān)系，當(dāng)數(shù)據(jù)處于倒序的情況時(shí)，交換次數(shù)同循環(huán)一樣（每次循環(huán)判斷都會(huì)交換），復(fù)雜度為O(n*n)。當(dāng)數(shù)據(jù)為正序，將不會(huì)有交換。復(fù)雜度為O(0)。亂序時(shí)處于中間狀態(tài)。正是由于這樣的原因，我們通常都是通過循環(huán)次數(shù)來對(duì)比算法。2.交換法：交換法的程序最清晰簡(jiǎn)單，每次用當(dāng)前的元素一一的同其后的元素比較并交換。#include void ExchangeSort(int* pData,int Count) int iTemp; for(int i=0;iCount-1;i+) for(int j=i+1;jCount;j+) if(pDatajpDatai) iTemp = pDatai; pDatai = pDataj; pDataj = iTemp; void main() int data = 10,9,8,7,6,5,4; ExchangeSort(data,7); for (int i=0;i7;i+) coutdatai ; cout9,10,8,7-8,10,9,7-7,10,9,8(交換3次)第二輪：7,10,9,8-7,9,10,8-7,8,10,9(交換2次)第一輪：7,8,10,9-7,8,9,10(交換1次)循環(huán)次數(shù)：6次交換次數(shù)：6次其他：第一輪：8,10,7,9-8,10,7,9-7,10,8,9-7,10,8,9(交換1次)第二輪：7,10,8,9-7,8,10,9-7,8,10,9(交換1次)第一輪：7,8,10,9-7,8,9,10(交換1次)循環(huán)次數(shù)：6次交換次數(shù)：3次從運(yùn)行的表格來看，交換幾乎和冒泡一樣糟。事實(shí)確實(shí)如此。循環(huán)次數(shù)和冒泡一樣也是1/2*(n-1)*n，所以算法的復(fù)雜度仍然是O(n*n)。由于我們無法給出所有的情況，所以只能直接告訴大家他們?cè)诮粨Q上面也是一樣的糟糕（在某些情況下稍好，在某些情況下稍差）。3.選擇法：現(xiàn)在我們終于可以看到一點(diǎn)希望：選擇法，這種方法提高了一點(diǎn)性能（某些情況下）這種方法類似我們?nèi)藶榈呐判蛄?xí)慣：從數(shù)據(jù)中選擇最小的同第一個(gè)值交換，在從省下的部分中選擇最小的與第二個(gè)交換，這樣往復(fù)下去。#include void SelectSort(int* pData,int Count) int iTemp; int iPos; for(int i=0;iCount-1;i+) iTemp = pDatai; iPos = i; for(int j=i+1;jCount;j+) if(pDatajiTemp) iTemp = pDataj; iPos = j; pDataiPos = pDatai; pDatai = iTemp; void main() int data = 10,9,8,7,6,5,4; SelectSort(data,7); for (int i=0;i7;i+) coutdatai ; cout(iTemp=9)10,9,8,7-(iTemp=8)10,9,8,7-(iTemp=7)7,9,8,10(交換1次)第二輪：7,9,8,10-7,9,8,10(iTemp=8)-(iTemp=8)7,8,9,10(交換1次)第一輪：7,8,9,10-(iTemp=9)7,8,9,10(交換0次)循環(huán)次數(shù)：6次交換次數(shù)：2次其他：第一輪：8,10,7,9-(iTemp=8)8,10,7,9-(iTemp=7)8,10,7,9-(iTemp=7)7,10,8,9(交換1次)第二輪：7,10,8,9-(iTemp=8)7,10,8,9-(iTemp=8)7,8,10,9(交換1次)第一輪：7,8,10,9-(iTemp=9)7,8,9,10(交換1次)循環(huán)次數(shù)：6次交換次數(shù)：3次遺憾的是算法需要的循環(huán)次數(shù)依然是1/2*(n-1)*n。所以算法復(fù)雜度為O(n*n)。我們來看他的交換。由于每次外層循環(huán)只產(chǎn)生一次交換（只有一個(gè)最小值）。所以f(n)=n所以我們有f(n)=O(n)。所以，在數(shù)據(jù)較亂的時(shí)候，可以減少一定的交換次數(shù)。4.插入法：插入法較為復(fù)雜，它的基本工作原理是抽出牌，在前面的牌中尋找相應(yīng)的位置插入，然后繼續(xù)下一張#include void InsertSort(int* pData,int Count) int iTemp; int iPos; for(int i=1;i=0) & (iTemppDataiPos) pDataiPos+1 = pDataiPos; iPos-; pDataiPos+1 = iTemp; void main() int data = 10,9,8,7,6,5,4; InsertSort(data,7); for (int i=0;i7;i+) coutdatai ; cout9,10,8,7(交換1次)(循環(huán)1次)第二輪：9,10,8,7-8,9,10,7(交換1次)(循環(huán)2次)第一輪：8,9,10,7-7,8,9,10(交換1次)(循環(huán)3次)循環(huán)次數(shù)：6次交換次數(shù)：3次其他：第一輪：8,10,7,9-8,10,7,9(交換0次)(循環(huán)1次)第二輪：8,10,7,9-7,8,10,9(交換1次)(循環(huán)2次)第一輪：7,8,10,9-7,8,9,10(交換1次)(循環(huán)1次)循環(huán)次數(shù)：4次交換次數(shù)：2次上面結(jié)尾的行為分析事實(shí)上造成了一種假象，讓我們認(rèn)為這種算法是簡(jiǎn)單算法中最好的，其實(shí)不是，因?yàn)槠溲h(huán)次數(shù)雖然并不固定，我們?nèi)钥梢允褂肙方法。從上面的結(jié)果可以看出，循環(huán)的次數(shù)f(n)= 1/2*n*(n-1)=1/2*n*n。所以其復(fù)雜度仍為O(n*n)（這里說明一下，其實(shí)如果不是為了展示這些簡(jiǎn)單排序的不同，交換次數(shù)仍然可以這樣推導(dǎo)）?，F(xiàn)在看交換，從外觀上看，交換次數(shù)是O(n)（推導(dǎo)類似選擇法），但我們每次要進(jìn)行與內(nèi)層循環(huán)相同次數(shù)的=操作。正常的一次交換我們需要三次=，而這里顯然多了一些，所以我們浪費(fèi)了時(shí)間。最終，我個(gè)人認(rèn)為，在簡(jiǎn)單排序算法中，選擇法是最好的。二、高級(jí)排序算法：高級(jí)排序算法中我們將只介紹這一種，同時(shí)也是目前我所知道（我看過的資料中）的最快的。它的工作看起來仍然象一個(gè)二叉樹。首先我們選擇一個(gè)中間值middle程序中我們使用數(shù)組中間值，然后把比它小的放在左邊，大的放在右邊（具體的實(shí)現(xiàn)是從兩邊找，找到一對(duì)后交換）。然后對(duì)兩邊分別使用這個(gè)過程（最容易的方法遞歸）。1.快速排序：#include void run(int* pData,int left,int right) int i,j; int middle,iTemp; i = left; j = right; middle = pData(left+right)/2; /求中間值 do while(pDataimiddle) & (imiddle) & (jleft)/從右掃描大于中值的數(shù) j-; if(i=j)/找到了一對(duì)值 /交換 iTemp = pDatai; pDatai = pDataj; pDataj = iTemp; i+; j-; while(i=j);/如果兩邊掃描的下標(biāo)交錯(cuò)，就停止（完成一次） /當(dāng)左邊部分有值(leftj)，遞歸左半邊 if(lefti)，遞歸右半邊 if(righti) run(pData,i,right);void QuickSort(int* pData,int Count) run(pData,0,Count-1);void main() int data = 10,9,8,7,6,5,4; QuickSort(data,7); for (int i=0;i7;i+) coutdatai ; coutn;這里我沒有給出行為的分析，因?yàn)檫@個(gè)很簡(jiǎn)單，我們直接來分析算法：首先我們考慮最理想的情況1.數(shù)組的大小是2的冪，這樣分下去始終可以被2整除。假設(shè)為2的k次方，即k=log2(n)。2.每次我們選擇的值剛好是中間值，這樣，數(shù)組才可以被等分。第一層遞歸，循環(huán)n次，第二層循環(huán)2*(n/2).所以共有n+2(n/2)+4(n/4)+.+n*(n/n) = n+n+n+.+n=k*n=log2(n)*n所以算法復(fù)雜度為O(log2(n)*n)其他的情況只會(huì)比這種情況差，最差的情況是每次選擇到的middle都是最小值或最大值，那么他將變成交換法（由于使用了遞歸，情況更糟）。但是你認(rèn)為這種情況發(fā)生的幾率有多大？呵呵，你完全不必?fù)?dān)心這個(gè)問題。實(shí)踐證明，大多數(shù)的情況，快速排序總是最好的。如果你擔(dān)心這個(gè)問題，你可以使用堆排序，這是一種穩(wěn)定的O(log2(n)*n)算法，但是通常情況下速度要慢于快速排序（因?yàn)橐亟M堆）。三、其他排序1.雙向冒泡：通常的冒泡是單向的，而這里是雙向的，也就是說還要進(jìn)行反向的工作。代碼看起來復(fù)雜，仔細(xì)理一下就明白了，是一個(gè)來回震蕩的方式。寫這段代碼的作者認(rèn)為這樣可以在冒泡的基礎(chǔ)上減少一些交換（我不這么認(rèn)為，也許我錯(cuò)了）。反正我認(rèn)為這是一段有趣的代碼，值得一看。#include void Bubble2Sort(int* pData,int Count) int iTemp; int left = 1; int right =Count -1; int t; do /正向的部分 for(int i=right;i=left;i-) if(pDataipDatai-1) iTemp = pDatai; pDatai = pDatai-1; pDatai-1 = iTemp; t = i; left = t+1; /反向的部分 for(i=left;iright+1;i+) if(pDataipDatai-1) iTemp = pDatai; pDatai = pDatai-1; pDatai-1 = iTemp; t = i; right = t-1; while(left=right);void main() int data = 10,9,8,7,6,