排序算法大全

排序算法大全

ID:25908253

大?。?2.50 KB

頁數(shù):10頁

時(shí)間:2018-11-23

排序算法大全_第1頁
排序算法大全_第2頁
排序算法大全_第3頁
排序算法大全_第4頁
排序算法大全_第5頁
資源描述:

《排序算法大全》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、排序算法是一種基本并且常用的算法。由于實(shí)際工作中處理的數(shù)量巨大,所以排序算法對(duì)算法本身的速度要求很高。而一般我們所謂的算法的性能主要是指算法的復(fù)雜度,一般用O方法來表示。在后面我將給出詳細(xì)的說明。對(duì)于排序的算法我想先做一點(diǎn)簡單的介紹,也是給這篇文章理一個(gè)提綱。我將按照算法的復(fù)雜度,從簡單到難來分析算法。第一部分是簡單排序算法,后面你將看到他們的共同點(diǎn)是算法復(fù)雜度為O(N*N)(因?yàn)闆]有使用word,所以無法打出上標(biāo)和下標(biāo))。第二部分是高級(jí)排序算法,復(fù)雜度為O(Log2(N))。這里我們只介紹一種算法。另外還有幾種算法因

2、為涉及樹與堆的概念,所以這里不于討論。第三部分類似動(dòng)腦筋。這里的兩種算法并不是最好的(甚至有最慢的),但是算法本身比較奇特,值得參考(編程的角度)。同時(shí)也可以讓我們從另外的角度來認(rèn)識(shí)這個(gè)問題?,F(xià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、Sort(data,7);for(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-

5、>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é)

6、是非常重要的?。。。┈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(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)。正是由于這樣的原

7、因,我們通常都是通過循環(huán)次數(shù)來對(duì)比算法。2.交換法:交換法的程序最清晰簡單,每次用當(dāng)前的元素一一的同其后的元素比較并交換。#includevoidExchangeSort(int*pData,intCount){intiTemp;for(inti=0;i

8、){intdata[]={10,9,8,7,6,5,4};ExchangeSort(data,7);for(inti=0;i<7;i++)cout<9,10,8,7->8,10,9,7->7,10,9,8(交換3次)第二輪:7,10,9,

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無此問題,請(qǐng)放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負(fù)責(zé)整理代發(fā)布。如果您對(duì)本文檔版權(quán)有爭議請(qǐng)及時(shí)聯(lián)系客服。
3. 下載前請(qǐng)仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時(shí)可能由于網(wǎng)絡(luò)波動(dòng)等原因無法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶請(qǐng)聯(lián)系客服處理。