C++排序算法大全.docx

《C++排序算法大全.docx》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

1、各種排序算法VC下的實(shí)現(xiàn)排序算法是一種基本并且常用的算法。由于實(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堆的概念，所以這里不于討論。第三

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

3、：這是最原始，也是眾所周知的最慢的算法了。他的名字的由來因?yàn)樗墓ぷ骺磥硐笫敲芭荩?includevoidBubbleSort(int*pData,intCount){intiTemp;for(inti=1;i=i;j--){if(pData[j]

4、r(inti=0;i<7;i++)cout<10,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(

5、交換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)。所以f

6、(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)前的元素一一的同其后的元素比較并交換。#includevoidExchangeSort(int*pData,intCou

7、nt){intiTemp;for(inti=0;i