參考排序算法小結(jié)范文

時間:2022-07-09 09:40:00

導(dǎo)語:參考排序算法小結(jié)范文一文來源于網(wǎng)友上傳,不代表本站觀點,若需要原創(chuàng)文章可咨詢客服老師,歡迎參考。

參考排序算法小結(jié)范文

花了很長時間終于把排序的基礎(chǔ)學(xué)了一下,這段時間學(xué)了很多東西,總結(jié)一下:

學(xué)的排序算法有:插入排序,合并排序,冒泡排序,選擇排序,希爾排序,堆排序,快速排序,計數(shù)排序,基數(shù)排序,桶排序(沒有實現(xiàn))。比較一下學(xué)習(xí)后的心得。

我不是很清楚他們的時間復(fù)雜度,也真的不知道他們到底誰快誰慢,書上的推導(dǎo)我確實只是小小了解,并沒有消化。也沒有完全理解他們的精髓,所以又什么錯誤的還需要高手指點。呵呵。

1.普及一下排序穩(wěn)定,所謂排序穩(wěn)定就是指:如果兩個數(shù)相同,對他們進(jìn)行的排序結(jié)果為他們的相對順序不變。例如A={1,2,1,2,1}這里排序之后是A={1,1,1,2,2}穩(wěn)定就是排序后第一個1就是排序前的第一個1,第二個1就是排序前第二個1,第三個1就是排序前的第三個1。同理2也是一樣。這里用顏色標(biāo)明了。不穩(wěn)定呢就是他們的順序不應(yīng)和開始順序一致。也就是可能會是A={1,1,1,2,2}這樣的結(jié)果。

2.普及一下原地排序:原地排序就是指不申請多余的空間來進(jìn)行的排序,就是在原來的排序數(shù)據(jù)中比較和交換的排序。例如快速排序,堆排序等都是原地排序,合并排序,計數(shù)排序等不是原地排序。

3.感覺誰最好,在我的印象中快速排序是最好的,時間復(fù)雜度:n*log(n),不穩(wěn)定排序。原地排序。他的名字很棒,快速嘛。當(dāng)然快了。我覺得他的思想很不錯,分治,而且還是原地排序,省去和很多的空間浪費。速度也是很快的,n*log(n)。但是有一個軟肋就是如果已經(jīng)是排好的情況下時間復(fù)雜度就是n*n,不過在加入隨機(jī)的情況下這種情況也得以好轉(zhuǎn),而且他可以做任意的比較,只要你能給出兩個元素的大小關(guān)系就可以了。適用范圍廣,速度快。

4.插入排序:n*n的時間復(fù)雜度,穩(wěn)定排序,原地排序。插入排序是我學(xué)的第一個排序,速度還是很快的,特別是在數(shù)組已排好了之后,用它的思想來插入一個數(shù)據(jù),效率是很高的。不用全部排。他的數(shù)據(jù)交換也很少,只是數(shù)據(jù)后移,然后放入要插入的數(shù)據(jù)。(這里不是指調(diào)用插入排序,而是用它的思想)。我覺得,在數(shù)據(jù)大部分都排好了,用插入排序會給你帶來很大的方便。數(shù)據(jù)的移動和交換都很少。

5.冒泡排序,n*n的時間復(fù)雜度,穩(wěn)定排序,原地排序。冒泡排序的思想很不錯,一個一個比較,把小的上移,依次確定當(dāng)前最小元素。他簡單,穩(wěn)定排序,而且好實現(xiàn),所以用處也是比較多的。還有一點就是加上哨兵之后他可以提前退出。