面試排序算法總結(jié)

1、排序算法1、 插入排序：插入即表示將一個新的數(shù)據(jù)插入到一個有序數(shù)組中，并繼續(xù)保持有序。例如有一個長度為N的無序數(shù)組，進行N-1次的插入即能完成排序；第一次，數(shù)組第1個數(shù)認為是有序的數(shù)組，將數(shù)組第二個元素插入僅有1個有序的數(shù)組中；第二次，數(shù)組前兩個元素組成有序的數(shù)組，將數(shù)組第三個元素插入由兩個元素構(gòu)成的有序數(shù)組中.第N-1次，數(shù)組前N-1個元素組成有序的數(shù)組，將數(shù)組的第N個元素插入由N-1個元素構(gòu)成的有序數(shù)組中，則完成了整個插入排序。以下面5個無序的數(shù)據(jù)為例：65 27 59 64 58 （文中僅細化了第四次插入過程）第1次插入: 27 65 59 64 58第2次插入: 27 59

2、65 64 58第3次插入: 27 59 64 65 58第4次插入: 27 58 59 64 65二. 、效率分析穩(wěn)定 空間復(fù)雜度O(1) 時間復(fù)雜度O(n2) 最差情況：反序，需要移動n*(n-1)/2個元素 最好情況：正序，不需要移動元素數(shù)組在已排序或者是“近似排序”時，插入排序效率的最好情況運行時間為O(n)；插入排序最壞情況運行時間和平均情況運行時間都為O(n2)。通常，插入排序呈現(xiàn)出二次排序算法中的最佳性能。對于具有較少元素（如n<=15）的列表來說，二次算法十分有效。在列表已被排序時，插入排序是線性算法O(n)。在列表“近似排序”時，

3、插入排序仍然是線性算法。在列表的許多元素已位于正確的位置上時，就會出現(xiàn)“近似排序”的條件。通過使用O(nlog2n)效率的算法（如快速排序）對數(shù)組進行部分排序，然后再進行選擇排序，某些高級的排序算法就是這樣實現(xiàn)的。三. 算法實現(xiàn)從前向后查找的插入排序：cpp view plain copy1. /* 2. *函數(shù)名稱：InsertSort 3. *參數(shù)說明：pDataArray 無序數(shù)組； 4. *          iDataNum為

4、無序數(shù)據(jù)個數(shù) 5. *說明：    插入排序 6. */  7. void InsertSort(int* pDataArray, int iDataNum)  8.   9.     for (int i = 1; i < iDataNum; i+)    /從第2個數(shù)據(jù)

5、開始插入  10.       11.         int j = 0;  12.         while (j < i && pDataArrayj <= pDataArrayi)  

6、;  /尋找插入的位置  13.             j+;  14.           15.         if (j < i)    /i位置之前，有

7、比pDataArrayi大的數(shù)，則進行挪動和插入  16.           17.             int k = i;  18.             int te

8、mp = pDataArrayi;  19.             while (k > j)    /挪動位置  20.               21.    

9、60;            pDataArrayk = pDataArrayk-1;  22.                 k-;  23.          &#

10、160;    24.             pDataArrayk = temp;    /插入  25.           26.       27.   但樓主發(fā)現(xiàn)從后面

11、查找插入的方式，代碼復(fù)雜程度較低：cpp view plain copy1. /* 2. *函數(shù)名稱：InsertSort 3. *參數(shù)說明：pDataArray 無序數(shù)組； 4. *          iDataNum為無序數(shù)據(jù)個數(shù) 5. *說明：    插入排序 6. */  7. void InsertSort(int* pData

12、Array, int iDataNum)  8.   9.     for (int i = 1; i < iDataNum; i+)    /從第2個數(shù)據(jù)開始插入  10.       11.         i

13、nt j = i - 1;  12.         int temp = pDataArrayi;    /記錄要插入的數(shù)據(jù)  13.         while (j >= 0 && pDataArray

14、j > temp)  /從后向前，找到比其小的數(shù)位置  14.           15.             pDataArrayj+1 = pDataArrayj;    /向后挪動  16.   

15、0;         j-;  17.           18.   19.         if (j != i - 1)    /存在比其小的數(shù)  20.  

16、60;          pDataArrayj+1 = temp;  21.       22.   2、選擇排序：比如在一個長度為N的無序數(shù)組中，在第一趟遍歷N個數(shù)據(jù)，找出其中最小的數(shù)值與第一個元素交換，第二趟遍歷剩下的N-1個數(shù)據(jù)，找出其中最小的數(shù)值與第二個元素交換.第N-1趟遍歷剩下的2個數(shù)據(jù)，找出其中最小的數(shù)值與第N-1個元素交換，至此選擇排序完成。以下面5個無序的數(shù)

17、據(jù)為例：56 12 80 91 20（文中僅細化了第一趟的選擇過程）第1趟：12 56 80 91 20第2趟：12 20 80 91 56第3趟：12 20 56 91 80第4趟：12 20 56 80 91二. 算法分析平均時間復(fù)雜度：O(n2)空間復(fù)雜度：O(1) (用于交換和記錄索引)穩(wěn)定性：不穩(wěn)定 （比如序列【5， 5， 3】第一趟就將第一個5與3交換，導(dǎo)致第一個5挪動到第二個5后面）三. 算法實現(xiàn)cpp view plain copy1. /交換data1和data2所指向的整形  2. void DataSwap(int*

18、60;data1, int* data2)  3.   4.     int temp = *data1;  5.     *data1 = *data2;  6.     *data2 = temp;  7.   8.   9. /* 1

19、0. *函數(shù)名稱：SelectionSort 11. *參數(shù)說明：pDataArray 無序數(shù)組； 12. *          iDataNum為無序數(shù)據(jù)個數(shù) 13. *說明：    選擇排序 14. */  15. void SelectionSort(int* pDataArray, int iDataNum)  16.

20、  17.     for (int i = 0; i < iDataNum - 1; i+)    /從第一個位置開始  18.       19.         int index = i;

21、0; 20.         for (int j = i + 1; j < iDataNum; j+)    /尋找最小的數(shù)據(jù)索引   21.             if (pDataArrayj&#

22、160;< pDataArrayindex)  22.                 index = j;  23.   24.         if (index != i)    /如果最

23、小數(shù)位置變化則交換  25.             DataSwap(&pDataArrayindex, &pDataArrayi);  26.       27.   冒泡排序：依次比較相鄰的數(shù)據(jù)，將小數(shù)據(jù)放在前，大數(shù)據(jù)放在后；即第一趟先比較第1個和第2個數(shù)，大數(shù)在后，小數(shù)在前，再比較第2個數(shù)與第3個數(shù)，大數(shù)在后，小數(shù)在前，以此

24、類推則將最大的數(shù)"滾動"到最后一個位置；第二趟則將次大的數(shù)滾動到倒數(shù)第二個位置.第n-1(n為無序數(shù)據(jù)的個數(shù))趟即能完成排序。以下面5個無序的數(shù)據(jù)為例：40 8 15 18 12 （文中僅細化了第一趟的比較過程）第1趟: 8 15 18 12 40第2趟: 8 15 12 18 40第3趟: 8 12 15 18 40第4趟: 8 12 15 18 40二. 算法分析平均時間復(fù)雜度：O(n2)空間復(fù)雜度：O(1)  (用于交換)穩(wěn)定性：穩(wěn)定三. 算法實現(xiàn)cpp view plain copy1. /交換data1和data2所指向的整形

25、0; 2. void DataSwap(int* data1, int* data2)  3.   4.     int temp = *data1;  5.     *data1 = *data2;  6.     *data2 = temp;  7. &#

26、160; 8.   9. /* 10. *函數(shù)名稱：BubbleSort 11. *參數(shù)說明：pDataArray 無序數(shù)組； 12. *          iDataNum為無序數(shù)據(jù)個數(shù) 13. *說明：    冒泡排序 14. */  15. void BubbleSort(int* pDataArray, int

27、 iDataNum)  16.   17.     for (int i = 0; i < iDataNum - 1; i+)   /走iDataNum-1趟  18.         for (int j = 0; j&#

28、160;< iDataNum - i - 1; j+)      19.             if (pDataArrayj > pDataArrayj + 1)  20.         &#

29、160;       DataSwap(&pDataArrayj, &pDataArrayj + 1);  21.   四. 算法優(yōu)化還可以對冒泡排序算法進行簡單的優(yōu)化，用一個標(biāo)記來記錄在一趟的比較過程中是否存在交換，如果不存在交換則整個數(shù)組已經(jīng)有序退出排序過程，反之則繼續(xù)進行下一趟的比較。cpp view plain copy1. /* 2. *函數(shù)名稱：BubbleSort 3. *參數(shù)說明：pD

30、ataArray 無序數(shù)組； 4. *          iDataNum為無序數(shù)據(jù)個數(shù) 5. *說明：    冒泡排序 6. */  7. void BubbleSort(int* pDataArray, int iDataNum)  8.   9.     BOOL 

31、;flag = FALSE;    /記錄是否存在交換  10.     for (int i = 0; i < iDataNum - 1; i+)    /走iDataNum-1趟  11.       12.    &#

32、160;    flag = FALSE;  13.         for (int j = 0; j < iDataNum - i - 1; j+)      14.        

33、;     if (pDataArrayj > pDataArrayj + 1)  15.               16.                 flag

34、60;= TRUE;  17.                 DataSwap(&pDataArrayj, &pDataArrayj + 1);  18.               19.  

35、;         20.         if (!flag)    /上一趟比較中不存在交換，則退出排序  21.             break;  22.     &#

36、160; 23.   快速排序由于排序效率在同為O(N*logN)的幾種排序方法中效率較高，因此經(jīng)常被采 用，再加上快速排序思想-分治法也確實實用，因此很多軟件公司的筆試面試，包括像騰訊，微軟等知名IT公司都喜歡考這個，還有大大小的程序方面的考 試如軟考，考研中也常常出現(xiàn)快速排序的身影?？偟恼f來，要直接默寫出快速排序還是有一定難度的，因為本人就自己的理解對快速排序作了下白話解釋，希望對大家理解有幫助，達到快速排序，快速搞定。 快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法(Divide-and

37、-ConquerMethod)。該方法的基本思想是：1先從數(shù)列中取出一個數(shù)作為基準(zhǔn)數(shù)。2分區(qū)過程，將比這個數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊。3再對左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個數(shù)。 雖然快速排序稱為分治法，但分治法這三個字顯然無法很好的概括快速排序的全部步驟。因此我的對快速排序作了進一步的說明：挖坑填數(shù)+分治法：先來看實例吧，定義下面再給出（最好能用自己的話來總結(jié)定義，這樣對實現(xiàn)代碼會有幫助）。 以一個數(shù)組作為示例，取區(qū)間第一個數(shù)為基準(zhǔn)數(shù)。01234567897265788604283734885初始時，i = 0;  j = 9;&

38、#160;  X = ai = 72由于已經(jīng)將a0中的數(shù)保存到X中，可以理解成在數(shù)組a0上挖了個坑，可以將其它數(shù)據(jù)填充到這來。從 j開始向前找一個比X小或等于X的數(shù)。當(dāng)j=8，符合條件，將a8挖出再填到上一個坑a0中。a0=a8; i+;  這樣一個坑a0就被搞定了，但又形成了一個新坑a8，這怎么辦了？簡單，再找數(shù)字來填a8這個坑。這次從i開始向后找一個大于X的數(shù)，當(dāng) i=3，符合條件，將a3挖出再填到上一個坑中a8=a3; j-; 數(shù)組變?yōu)椋?1234567894865788604283738885 i = 3;   j = 7;

39、  X=72再重復(fù)上面的步驟，先從后向前找，再從前向后找。從j開始向前找，當(dāng)j=5，符合條件，將a5挖出填到上一個坑中，a3 = a5; i+;從i開始向后找，當(dāng)i=5時，由于i=j退出。此時，i = j = 5，而a5剛好又是上次挖的坑，因此將X填入a5。 數(shù)組變?yōu)椋?1234567894865742607283738885可以看出a5前面的數(shù)字都小于它，a5后面的數(shù)字都大于它。因此再對a04和a69這二個子區(qū)間重復(fù)上述步驟就可以了。  對挖坑填數(shù)進行總結(jié)1i =L; j = R; 將基準(zhǔn)數(shù)挖出形成第一個坑ai。2j-由后向前找比它小的數(shù)，找

40、到后挖出此數(shù)填前一個坑ai中。3i+由前向后找比它大的數(shù)，找到后也挖出此數(shù)填到前一個坑aj中。4再重復(fù)執(zhí)行2，3二步，直到i=j，將基準(zhǔn)數(shù)填入ai中。照著這個總結(jié)很容易實現(xiàn)挖坑填數(shù)的代碼：cpp view plain copy1. int AdjustArray(int s, int l, int r) /返回調(diào)整后基準(zhǔn)數(shù)的位置  2.   3.     int i = l, j = r

41、;  4.     int x = sl; /sl即si就是第一個坑  5.     while (i < j)  6.       7.         / 從右向左找小于x的數(shù)來填si  8.  &#

42、160;      while(i < j && sj >= x)   9.             j-;    10.         if(i < j

43、)   11.           12.             si = sj; /將sj填到si中，sj就形成了一個新的坑  13.             i+; 

44、; 14.           15.   16.         / 從左向右找大于或等于x的數(shù)來填sj  17.         while(i < j && si < x) &

45、#160;18.             i+;    19.         if(i < j)   20.           21.      &#

46、160;      sj = si; /將si填到sj中，si就形成了一個新的坑  22.             j-;  23.           24.       25. 

47、0;   /退出時，i等于j。將x填到這個坑中。  26.     si = x;  27.   28.     return i;  29.   再寫分治法的代碼：cpp view plain copy1. void quick_sort1(int s, int l, int r) &#

48、160;2.   3.     if (l < r)  4.       5.         int i = AdjustArray(s, l, r);/先成挖坑填數(shù)法調(diào)整s  6.        &#

49、160;quick_sort1(s, l, i - 1); / 遞歸調(diào)用   7.         quick_sort1(s, i + 1, r);  8.       9.   這樣的代碼顯然不夠簡潔，對其組合整理下：cpp view plain copy1. /快速排序 &

50、#160;2. void quick_sort(int s, int l, int r)  3.   4.     if (l < r)  5.       6.         /Swap(sl, s(l + r) /&#

51、160;2); /將中間的這個數(shù)和第一個數(shù)交換 參見注1  7.         int i = l, j = r, x = sl;  8.         while (i < j)  9.    &#

52、160;      10.             while(i < j && sj >= x) / 從右向左找第一個小于x的數(shù)  11.             

53、60;   j-;    12.             if(i < j)   13.                 si+ = sj;  14. &

54、#160;             15.             while(i < j && si < x) / 從左向右找第一個大于等于x的數(shù)  16.      &

55、#160;          i+;    17.             if(i < j)   18.               

56、0; sj- = si;  19.           20.         si = x;  21.         quick_sort(s, l, i - 1); / 遞歸調(diào)用

57、60;  22.         quick_sort(s, i + 1, r);  23.       24.   快速排序還有很多改進版本，如隨機選擇基準(zhǔn)數(shù)，區(qū)間內(nèi)數(shù)據(jù)較少時直接用另的方法排序以減小遞歸深度。有興趣的筒子可以再深入的研究下。隨機選取基準(zhǔn)引入的原因：在待排序列是部分有序時，固定選取樞軸使快排效率底下，要緩解這種情況，就引入了隨機選取樞軸/*

58、隨機選擇樞軸的位置，區(qū)間在low和high之間*/int SelectPivotRandom(int arr,int low,int high)/產(chǎn)生樞軸的位置srand(unsigned)time(NULL);int pivotPos = rand()%(high - low) + low;/把樞軸位置的元素和low位置元素互換，此時可以和普通的快排一樣調(diào)用劃分函數(shù)swap(arrpivotPos,arrlow);return arrlow;測試數(shù)據(jù)分析：:這是一種相對安全的策略。由于樞軸的位置是隨機的，那么產(chǎn)生的分割也不會總是會出現(xiàn)劣質(zhì)的分割。在整個數(shù)組數(shù)字全相等時，仍然是最壞情況，時間復(fù)

59、雜度是O(n2）。實際上，隨機化快速排序得到理論最壞情況的可能性僅為1/(2n）。所以隨機化快速排序可以對于絕大多數(shù)輸入數(shù)據(jù)達到O(nlogn）的期望時間復(fù)雜度。一位前輩做出了一個精辟的總結(jié)：“隨機化快速排序可以滿足一個人一輩子的人品需求。”三數(shù)取中（median-of-three）引入的原因：雖然隨機選取樞軸時，減少出現(xiàn)不好分割的幾率，但是還是最壞情況下還是O(n2），要緩解這種情況，就引入了三數(shù)取中選取樞軸分析：最佳的劃分是將待排序的序列分成等長的子序列，最佳的狀態(tài)我們可以使用序列的中間的值，也就是第N/2個數(shù)?？墒?，這很難算出來，并且會明顯減慢快速排序的速度。這樣的中值的估計可以通過隨機

60、選取三個元素并用它們的中值作為樞紐元而得到。事實上，隨機性并沒有多大的幫助，因此一般的做法是使用左端、右端和中心位置上的三個元素的中值作為樞紐元。顯然使用三數(shù)中值分割法消除了預(yù)排序輸入的不好情形，并且減少快排大約14%的比較次數(shù)舉例：待排序序列為：8 1 4 9 6 3 5 2 7 0左邊為：8，右邊為0，中間為6.我們這里取三個數(shù)排序后，中間那個數(shù)作為樞軸，則樞軸為6注意：在選取中軸值時，可以從由左中右三個中選取擴大到五個元素中或者更多元素中選取，一般的，會有（2t1）平均分區(qū)法（median-of-(2t+1)，三平均分區(qū)法英文為median-of-three）。具體思想：對待排序序列中l(wèi)

61、ow、mid、high三個位置上數(shù)據(jù)進行排序，取他們中間的那個數(shù)據(jù)作為樞軸，并用0下標(biāo)元素存儲樞軸。即：采用三數(shù)取中，并用0下標(biāo)元素存儲樞軸。cpp view plain copy1. /*函數(shù)作用：取待排序序列中l(wèi)ow、mid、high三個位置上數(shù)據(jù)，選取他們中間的那個數(shù)據(jù)作為樞軸*/  2. int SelectPivotMedianOfThree(int arr,int low,int high)  3.   4.     int

62、 mid = low + (high - low) >> 1);/計算數(shù)組中間的元素的下標(biāo)  5.   6.     /使用三數(shù)取中法選擇樞軸  7.     if (arrmid > arrhigh)/目標(biāo): arrmid <= arrhigh  8.  

63、;     9.         swap(arrmid,arrhigh);  10.       11.     if (arrlow > arrhigh)/目標(biāo): arrlow <= arrhigh  12.    

64、0;  13.         swap(arrlow,arrhigh);  14.       15.     if (arrmid > arrlow) /目標(biāo): arrlow >= arrmid  16.      

65、0;17.         swap(arrmid,arrlow);  18.       19.     /此時，arrmid <= arrlow <= arrhigh  20.     return arrlow;  21.   &#

66、160; /low的位置上保存這三個位置中間的值  22.     /分割時可以直接使用low位置的元素作為樞軸，而不用改變分割函數(shù)了  23.   測試數(shù)據(jù)分析：使用三數(shù)取中選擇樞軸優(yōu)勢還是很明顯的，但是還是處理不了重復(fù)數(shù)組注1， 有的書上是以中間的數(shù)作為基準(zhǔn)數(shù)的，要實現(xiàn)這個方便非常方便，直接將中間的數(shù)和第一個數(shù)進行交換就可以了。優(yōu)化1、當(dāng)待排序序列的長度分割到一定大小后，使用插入排序。原因：對于很小和部分有序的數(shù)組，快排不如插排好。當(dāng)待排序序列的長度分割到一定大小后，繼續(xù)分割的效率

67、比插入排序要差，此時可以使用插排而不是快排截止范圍：待排序序列長度N = 10，雖然在520之間任一截止范圍都有可能產(chǎn)生類似的結(jié)果，這種做法也避免了一些有害的退化情形。摘自數(shù)據(jù)結(jié)構(gòu)與算法分析Mark Allen Weiness 著cpp view plain copyif (high - low + 1 < 10) InsertSort(arr,low,high); return; /else時，正常執(zhí)行快排 測試數(shù)據(jù)分析：針對隨機數(shù)組，使用三數(shù)取中選擇樞軸+插排，效率還是可以提高一點，真是針對已排序的數(shù)組，是沒有任何用處的。因為待排序序列是已經(jīng)有序的，那么每次劃分只能使待排序序列減一。

68、此時，插排是發(fā)揮不了作用的。所以這里看不到時間的減少。另外，三數(shù)取中選擇樞軸+插排還是不能處理重復(fù)數(shù)組優(yōu)化2、在一次分割結(jié)束后，可以把與Key相等的元素聚在一起，繼續(xù)下次分割時，不用再對與key相等元素分割舉例：待排序序列 1 4 6 7 6 6 7 6 8 6三數(shù)取中選取樞軸：下標(biāo)為4的數(shù)6轉(zhuǎn)換后，待分割序列：6 4 6 7 1 6 7 6 8 6             樞軸key：6本次劃分后，未對與key元素相等處理的結(jié)果：1 4 6 6 7 6 7 6 8 6下次的兩個子序列為：1 4

69、 6 和 7 6 7 6 8 6本次劃分后，對與key元素相等處理的結(jié)果：1 4 6 6 6 6 6 7 8 7下次的兩個子序列為：1 4 和 7 8 7經(jīng)過對比，我們可以看出，在一次劃分后，把與key相等的元素聚在一起，能減少迭代次數(shù)，效率會提高不少具體過程：在處理過程中，會有兩個步驟第一步，在劃分過程中，把與key相等元素放入數(shù)組的兩端第二步，劃分結(jié)束后，把與key相等的元素移到樞軸周圍舉例：待排序序列 1 4 6 7 6 6 7 6 8 6三數(shù)取中選取樞軸：下標(biāo)為4的數(shù)6轉(zhuǎn)換后，待分割序列：6 4 6 7 1 6 7

70、6 8 6             樞軸key：6第一步，在劃分過程中，把與key相等元素放入數(shù)組的兩端結(jié)果為：6 4 1 6(樞軸) 7 8 7 6 6 6此時，與6相等的元素全放入在兩端了第二步，劃分結(jié)束后，把與key相等的元素移到樞軸周圍結(jié)果為：1 4 66(樞軸)  6 6 6 7 8 7此時，與6相等的元素全移到樞軸周圍了之后，在1 4 和 7 8 7兩個子序列進行快排代碼cpp view plain copy1. void QSort

71、(int arr,int low,int high)  2.   3.     int first = low;  4.     int last = high;  5.   6.     int left = low;  7.  

72、;   int right = high;  8.   9.     int leftLen = 0;  10.     int rightLen = 0;  11.   12.     if (high - low +

73、 1 < 10)  13.       14.         InsertSort(arr,low,high);  15.         return;  16.       17.    

74、   18.     /一次分割  19.     int key = SelectPivotMedianOfThree(arr,low,high);/使用三數(shù)取中法選擇樞軸  20.           21.     while(low < high

75、)  22.       23.         while(high > low && arrhigh >= key)  24.           25.       

76、      if (arrhigh = key)/處理相等元素  26.               27.                 swap(arrright,arrhigh);&

77、#160; 28.                 right-;  29.                 rightLen+;  30.        &#

78、160;      31.             high-;  32.           33.         arrlow = arrhigh;  34.  &

79、#160;      while(high > low && arrlow <= key)  35.           36.             if (arrlow = k

80、ey)  37.               38.                 swap(arrleft,arrlow);  39.           

81、      left+;  40.                 leftLen+;  41.               42.      

82、60;      low+;  43.           44.         arrhigh = arrlow;  45.       46.     arrlow = key;  47.   48.     /一次快排結(jié)束  49.     /把與樞軸key相同的元素移到樞軸最終位置周圍  50.     int i&