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

1、頁眉內(nèi)容C/C+筆試面試題目匯總3 各種排序算法原文：排序算法是一種基本并且常用的算法。由于實際工作中處理的數(shù)量巨大，所以排序算法對算法本身的速度要求很高。而一般我們所謂的算法的性能主要是指算法的復雜度，一般用0方法來表示。在后面我將給岀詳細的說明。對于排序的算法我想先做一點簡單的介紹，也是給這篇文章理一個提綱。我將按照算法的復雜度，從簡單到難來分析算法。第一部分是簡單排序算法，后面你將看到他們的共同點是算法復雜度為O(N*N)(因為沒有使用word,所以無法打?qū)缟蠘撕拖聵?。第二部分是高級排序算法，復雜度為O(Log2(N)。這里我們只介紹一種算法。另外還有幾種算法因為涉及樹與堆的概念，所以

2、這里不于討論。第三部分類似動腦筋。這里的兩種算法并不是最好的(甚至有最慢的)，但是算法本身比較奇特，值得參 考(編程的角度)。同時也可以讓我們從另外的角度來認識這個問題。第四部分是我送給大家的一個餐后的甜點一一一個基于模板的通用快速排序。由于是模板函數(shù)可以對任何數(shù)據(jù)類型排序(抱歉，里面使用了一些論壇專家的呢稱)。一、簡單排序算法由于程序比較簡單，所以沒有加什么注釋。所有的程序都給岀了完整的運行代碼，并在我的VC環(huán)境下運行通過。因為沒有涉及 MFC和WINDOWS的內(nèi)容，所以在BORLAND C+的平臺上應該也不會有什么問 題的。在代碼的后面給岀了運行過程示意，希望對理解有幫助。1. 冒泡法：(

3、Gilbert :點這里有視頻)這是最原始，也是眾所周知的最慢的算法了。他的名字的由來因為它的工作看來象是冒泡：#include void BubbleSort(int* pData,int Count)int iTemp;for(int i=1;i=i;j-)if(pDatajpDataj-1)iTemp = pDataj-1;pDataj-1 = pDatajpDataj = iTemp;void main()int data = 10,9,8,7,6,5,4;BubbleSort(data,7);for (int i=0;i7;i+)cout10,9,7,8-10,7,9,8-7,10,

4、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ù)是固定

5、的，為1+2+.+n-1。寫成公式就是1/2*(n-1)*n?，F(xiàn)在注意，我們給岀 0方法的定義：若存在一常量K和起點n0，使當n=n0時，有f(n)v=K*g(n),則f(n) = O(g(n)。(呵呵，不要說沒學好 數(shù)學呀，對于編程數(shù)學是非常重要的！ ！)現(xiàn)在我們來看 1/2*(n-1)*n，當 K=1/2，n0=1，g(n)=n*n 時，1/2*(n-1)*n=1/2*n*n=K*g(n)。所以 (n)=O(g(n)=O(n*n)。所以我們程序循環(huán)的復雜度為0(n*n)。再看交換。從程序后面所跟的表可以看到，兩種情況的循環(huán)相同，交換不同。其實交換本身同數(shù)據(jù)源的有 序程度有極大的關系，當數(shù)據(jù)

6、處于倒序的情況時，交換次數(shù)同循環(huán)一樣(每次循環(huán)判斷都會交換)，復雜 度為0(n*n)。當數(shù)據(jù)為正序，將不會有交換。復雜度為0(0)。亂序時處于中間狀態(tài)。正是由于這樣的原因, 我們通常都是通過循環(huán)次數(shù)來對比算法。2. 交換法：交換法的程序最清晰簡單，每次用當前的元素一一的同其后的元素比較并交換。#include void ExchangeSort(int* pData,int Count)int iTemp;for（int i=0;iCount-1;i+）for（int j=i+1;jCount;j+）if（pDatajvpDatai）iTemp = pDatai;pDatai = pDataj

7、;pDataj = iTemp;void main（）int data = 10,9,8,7,6,5,4;ExchangeSort（data,7）;for （int i=0;i7;i+）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 次）

8、第一輪：7,8,10,9-7,8,9,10（交換 1 次）循環(huán)次數(shù)：6次交換次數(shù)：3次從運行的表格來看，交換幾乎和冒泡一樣糟。事實確實如此。循環(huán)次數(shù)和冒泡一樣也是1/2*（n-1）*n，所以算法的復雜度仍然是O（n*n）。由于我們無法給出所有的情況，所以只能直接告訴大家他們在交換上面也是 一樣的糟糕（在某些情況下稍好，在某些情況下稍差）。3. 選擇法：現(xiàn)在我們終于可以看到一點希望：選擇法，這種方法提高了一點性能（某些情況下） 這種方法類似我們?nèi)藶榈呐判蛄晳T：從數(shù)據(jù)中選擇最小的同第一個值交換，在從省下的部分中選擇最小的 與第二個交換，這樣往復下去。#include void SelectSort

9、(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 = pDatajiPos = 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+)cout(iTemp=9)10,9,8,7-(iTemp=8)10,9,8,7-

10、(iTemp=7)7,9,8,10(第二輪：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(第二輪：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次

11、交換次數(shù)：3次遺憾的是算法需要的循環(huán)次數(shù)依然是1/2*(n-1)*n。所以算法復雜度為 O(n*n)我們來看他的交換。由于每次外層循環(huán)只產(chǎn)生一次交換（只有一個最小值）。所以f（n）v=n所以我們有f（n）=O（n）。所以，在數(shù)據(jù)較亂的時候，可以減少一定的交換次數(shù)。4. 插入法：插入法較為復雜，它的基本工作原理是抽岀牌，在前面的牌中尋找相應的位置插入，然后繼續(xù)下一張#include void InsertSort(int* pData,int Count)int iTemp;int iPos;for(int i=1;i=0) & (iTempvpDataiPos)pDataiPos+1 = pD

12、ataiPos;iPos-;pDataiPos+1 = iTemp;void main()int data = 10,9,8,7,6,5,4;InsertSort(data,7);for (int i=0;i7;i+)coutdataivv;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(8.10.7.9- 7,8,10,9(交換0次）（循環(huán)1次）交換1

13、次）（循環(huán)2次）第一輪：7,8,10,9-7,8,9,10(交換 1 次)(循環(huán) 1 次)循環(huán)次數(shù)：4次交換次數(shù)：2次上面結尾的行為分析事實上造成了一種假象，讓我們認為這種算法是簡單算法中最好的，其實不是，因為 其循環(huán)次數(shù)雖然并不固定，我們?nèi)钥梢允褂肙方法。從上面的結果可以看出，循環(huán)的次數(shù)f(n)=1/2*n*(n-1)v=1/2*n*n 。所以其復雜度仍為O(n*n)(這里說明一下，其實如果不是為了展示這些簡單排序的 不同，交換次數(shù)仍然可以這樣推導)?，F(xiàn)在看交換，從外觀上看，交換次數(shù)是O(n)(推導類似選擇法)，但我們每次要進行與內(nèi)層循環(huán)相同次數(shù)的操作。正常的一次交換我們需要三次，而這里顯然

14、多了一些，所以我們浪費了時間。最終，我個人認為，在簡單排序算法中，選擇法是最好的。二、高級排序算法：高級排序算法中我們將只介紹這一種，同時也是目前我所知道(我看過的資料中)的最快的。它的工作看起來仍然象一個二叉樹。首先我們選擇一個中間值middle程序中我們使用數(shù)組中間值，然后把比它小的放在左邊，大的放在右邊(具體的實現(xiàn)是從兩邊找，找到一對后交換)。然后對兩邊分別使用這 個過程(最容易的方法遞歸)。1.快速排序：#include void run(int* pData,int left,int right)int i,j;int middle,iTemp;i = left;j = right;

15、middle = pData(left+right)/2; / 求中間值dowhile(pDataimiddle) & (imiddle) & (jleft)/從右掃描大于中值的數(shù)j-;if(i=j)找到了一對值/交換iTemp = pDatai;pDatai = pDataj;pDataj = iTemp;i+;j-;while(ii)，遞歸右半邊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;Q

16、uickSort(data,7);for (int i=0;i7;i+)coutdataivv;coutn;這里我沒有給岀行為的分析，因為這個很簡單，我們直接來分析算法：首先我們考慮最理想的情況1.數(shù)組的大小是2的冪，這樣分下去始終可以被2整除。假設為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所以算法復雜度為O(log2(n)*n)其他的情況只會比這種情況差，最差的情況是每次選擇到的midd

17、le都是最小值或最大值，那么他將變成交換法(由于使用了遞歸，情況更糟)。但是你認為這種情況發(fā)生的幾率有多大？呵呵，你完全不必擔心 這個問題。實踐證明，大多數(shù)的情況，快速排序總是最好的。如果你擔心這個問題，你可以使用堆排序，這是一種穩(wěn)定的O(log2(n)*n)算法，但是通常情況下速度要慢于快速排序(因為要重組堆)。三、其他排序1.雙向冒泡：通常的冒泡是單向的，而這里是雙向的，也就是說還要進行反向的工作。代碼看起來復雜，仔細理一下就明白了，是一個來回震蕩的方式。寫這段代碼的作者認為這樣可以在冒泡的基礎上減少一些交換(我不這么認為，也許我錯了)。反正我認為這是一段有趣的代碼，值得一看。#inclu

18、de 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(pDataivpDatai-1)iTemp = pDatai; pDatai = pDatai-1; pDatai-1 = iTemp;t = i;left = t+1;/反向的部分for(i=left;iright+1;i+)if(pDataivpDatai-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,5,4; Bubble2Sort(data,7);for (int i=0;i7;i+) coutvdataivv;coutn;2.SHELL 排序這個排序非常復雜，看了程序就知道了。首先需要一個遞減的步長，這里我們使用的是9、5、3、1 (最后的步長必須是1 )。工作原理是首先對相隔9-1個元素的所有內(nèi)容排序，然后再使用同樣的方法對相隔5-1個元素的排序以次類推。#include void ShellSort(int* p