幾種 排序算法,以及排序的算法

幾種 排序算法,以及排序的算法

ID:26691821

大?。?0.00 KB

頁(yè)數(shù):12頁(yè)

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

幾種 排序算法,以及排序的算法_第1頁(yè)
幾種 排序算法,以及排序的算法_第2頁(yè)
幾種 排序算法,以及排序的算法_第3頁(yè)
幾種 排序算法,以及排序的算法_第4頁(yè)
幾種 排序算法,以及排序的算法_第5頁(yè)
資源描述:

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

1、常用的算法的時(shí)間復(fù)雜度和空間復(fù)雜度排序法最差時(shí)間分析平均時(shí)間復(fù)雜度穩(wěn)定度空間復(fù)雜度冒泡排序O(n2)O(n2)穩(wěn)定O(1)快速排序O(n2)O(n*log2n)不穩(wěn)定O(log2n)~O(n)選擇排序O(n2)O(n2)穩(wěn)定O(1)二叉樹排序O(n2)O(n*log2n)不一頂O(n)插入排序O(n2)O(n2)穩(wěn)定O(1)堆排序O(n*log2n)O(n*log2n)不穩(wěn)定O(1)希爾排序OO不穩(wěn)定O(1)1、時(shí)間復(fù)雜度?(1)時(shí)間頻度一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間,從理論上是不能算出來的,必須上機(jī)運(yùn)行測(cè)試才能知道。但我們不可能也沒有必要對(duì)

2、每個(gè)算法都上機(jī)測(cè)試,只需知道哪個(gè)算法花費(fèi)的時(shí)間多,哪個(gè)算法花費(fèi)的時(shí)間少就可以了。并且一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例,哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多,它花費(fèi)時(shí)間就多。一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱為語(yǔ)句頻度或時(shí)間頻度。記為T(n)。?(2)時(shí)間復(fù)雜度在剛才提到的時(shí)間頻度中,n稱為問題的規(guī)模,當(dāng)n不斷變化時(shí),時(shí)間頻度T(n)也會(huì)不斷變化。但有時(shí)我們想知道它變化時(shí)呈現(xiàn)什么規(guī)律。為此,我們引入時(shí)間復(fù)雜度概念。一般情況下,算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù),用T(n)表示,若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無(wú)窮大時(shí),

3、T(n)/f(n)的極限值為不等于零的常數(shù),則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=O(f(n)),稱O(f(n))為算法的漸進(jìn)時(shí)間復(fù)雜度,簡(jiǎn)稱時(shí)間復(fù)雜度。?在各種不同算法中,若算法中語(yǔ)句執(zhí)行次數(shù)為一個(gè)常數(shù),則時(shí)間復(fù)雜度為O(1),另外,在時(shí)間頻度不相同時(shí),時(shí)間復(fù)雜度有可能相同,如T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同,但時(shí)間復(fù)雜度相同,都為O(n2)。按數(shù)量級(jí)遞增排列,常見的時(shí)間復(fù)雜度有:常數(shù)階O(1),對(duì)數(shù)階O(log2n),線性階O(n),線性對(duì)數(shù)階O(nlog2n),平方階O(n2),立方

4、階O(n3),...,k次方階O(nk),指數(shù)階O(2n)。隨著問題規(guī)模n的不斷增大,上述時(shí)間復(fù)雜度不斷增大,算法的執(zhí)行效率越低。2、空間復(fù)雜度與時(shí)間復(fù)雜度類似,空間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所需存儲(chǔ)空間的度量。記作:S(n)=O(f(n))我們一般所討論的是除正常占用內(nèi)存開銷外的輔助存儲(chǔ)單元規(guī)模。討論方法與時(shí)間復(fù)雜度類似,不再贅述。?(3)漸進(jìn)時(shí)間復(fù)雜度評(píng)價(jià)算法時(shí)間性能  主要用算法時(shí)間復(fù)雜度的數(shù)量級(jí)(即算法的漸近時(shí)間復(fù)雜度)評(píng)價(jià)一個(gè)算法的時(shí)間性能。?2、類似于時(shí)間復(fù)雜度的討論,一個(gè)算法的空間復(fù)雜度(SpaceComplexity

5、)S(n)定義為該算法所耗費(fèi)的存儲(chǔ)空間,它也是問題規(guī)模n的函數(shù)。漸近空間復(fù)雜度也常常簡(jiǎn)稱為空間復(fù)雜度。?空間復(fù)雜度(SpaceComplexity)是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度。一個(gè)算法在計(jì)算機(jī)存儲(chǔ)器上所占用的存儲(chǔ)空間,包括存儲(chǔ)算法本身所占用的存儲(chǔ)空間,算法的輸入輸出數(shù)據(jù)所占用的存儲(chǔ)空間和算法在運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間這三個(gè)方面。算法的輸入輸出數(shù)據(jù)所占用的存儲(chǔ)空間是由要解決的問題決定的,是通過參數(shù)表由調(diào)用函數(shù)傳遞而來的,它不隨本算法的不同而改變。存儲(chǔ)算法本身所占用的存儲(chǔ)空間與算法書寫的長(zhǎng)短成正比,要壓縮這方面的

6、存儲(chǔ)空間,就必須編寫出較短的算法。算法在運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間隨算法的不同而異,有的算法只需要占用少量的臨時(shí)工作單元,而且不隨問題規(guī)模的大小而改變,我們稱這種算法是“就地"進(jìn)行的,是節(jié)省存儲(chǔ)的算法,如這一節(jié)介紹過的幾個(gè)算法都是如此;有的算法需要占用的臨時(shí)工作單元數(shù)與解決問題的規(guī)模n有關(guān),它隨著n的增大而增大,當(dāng)n較大時(shí),將占用較多的存儲(chǔ)單元,例如將在第九章介紹的快速排序和歸并排序算法就屬于這種情況。如當(dāng)一個(gè)算法的空間復(fù)雜度為一個(gè)常量,即不隨被處理數(shù)據(jù)量n的大小而改變時(shí),可表示為O(1);當(dāng)一個(gè)算法的空間復(fù)雜度與以2為底的n的對(duì)數(shù)

7、成正比時(shí),可表示為0(10g2n);當(dāng)一個(gè)算法的空I司復(fù)雜度與n成線性比例關(guān)系時(shí),可表示為0(n).若形參為數(shù)組,則只需要為它分配一個(gè)存儲(chǔ)由實(shí)參傳送來的一個(gè)地址指針的空間,即一個(gè)機(jī)器字長(zhǎng)空間;若形參為引用方式,則也只需要為其分配存儲(chǔ)一個(gè)地址的空間,用它來存儲(chǔ)對(duì)應(yīng)實(shí)參變量的地址,以便由系統(tǒng)自動(dòng)引用實(shí)參變量。?分類:?數(shù)據(jù)結(jié)構(gòu)及算法1.排序排序定義是將一個(gè)數(shù)據(jù)元素的任意序列,重新排列成為一個(gè)按關(guān)鍵字有序的序列排序分類:按待排序記錄所在位置內(nèi)在排序:待排序記錄存放內(nèi)存外部排序:外排序過程需對(duì)外存進(jìn)行訪問排序按排序依據(jù)原則:插入排序:直接插入排

8、序,折半插入排序,希爾排序交換排序:冒泡排序,快速排序選擇排序:簡(jiǎn)單選擇排序,堆排序歸并排序:2-路歸并排序基數(shù)排序插入排序(1)直接插入排序每次從無(wú)序表中取出第一個(gè)元素,把它插入到有序表的合適位置,使有序

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

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

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無(wú)此問題,請(qǐng)放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫(kù)負(fù)責(zé)整理代發(fā)布。如果您對(duì)本文檔版權(quán)有爭(zhēng)議請(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)等原因無(wú)法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶請(qǐng)聯(lián)系客服處理。