一、冒泡排序
談到排序算法,首先映入腦中的便是冒泡排序站粟,這也是我接觸的第一種排序算法,的確算是一個比較經(jīng)典的算法曾雕。冒泡排序的算法應(yīng)該是從魚吐泡泡的事件中啟發(fā)出來的奴烙。也應(yīng)該算是最容易理解的一種排序算法了
1.算法思想圖解
從左到右的按照從小到大的順序依次排列
第一次排序
第二輪排序
第三輪排序
隨著比賽輪數(shù)的增加,比賽次數(shù)呈現(xiàn)遞減趨勢
2.時間復(fù)雜度
時間復(fù)雜度的算法:如果是四個數(shù)字排序的話,那第一輪排序需要進(jìn)行3次缸沃,第二輪需要進(jìn)行2次恰起,第三輪需要1次,則為3+2+1次趾牧,推及到Nge數(shù)字排序的話那就是(n-1)+(n-2)+.....+1=n^2/2-n/2.根據(jù)復(fù)雜度的規(guī)則检盼,去掉低階項(xiàng)n/2,和常數(shù)系數(shù),那么時間復(fù)雜度就是O(n^2)
3.空間復(fù)雜度
空間復(fù)雜度就是在交換元素時那個臨時變量所占的內(nèi)存翘单。最優(yōu)的空間復(fù)雜度為開始元素已排序即不需要進(jìn)行交換吨枉,則空間復(fù)雜度為 0;最差的空間復(fù)雜度為原始元素為逆排序哄芜,則空間復(fù)雜度為 O(N);那么平均的空間復(fù)雜度為O(1)貌亭。
4.算法實(shí)現(xiàn)(java)
5.算法改進(jìn)
看一下算法思想圖解中,第二輪排序完成后已經(jīng)完成了所有的排序认臊,但是按照上面的算法實(shí)現(xiàn)圃庭,依然會進(jìn)行第三輪比較排序,雖然單看上面的僅僅進(jìn)行了最后一輪的操作失晴,但是如果數(shù)組中的數(shù)量成百上千呢剧腻,如果數(shù)組的順序一開始就是已經(jīng)排序好了呢,那么這個耗費(fèi)的時間也是不可低估的涂屁,所以要在原來算法的基礎(chǔ)上進(jìn)行改良书在,如下給定一個 整數(shù)型標(biāo)識符 flag ,當(dāng)某次外層循環(huán)中,內(nèi)循環(huán)里沒有發(fā)生相鄰元素的交換拆又,則表示當(dāng)前數(shù)組已排序成功儒旬,直接跳出外層循環(huán)。
二帖族、快速排序
1.算法思想及圖解
(1)算法的思想
是冒泡排序的改進(jìn)型栈源。
a.在數(shù)組中選擇一個基準(zhǔn)點(diǎn)(該基準(zhǔn)點(diǎn)的選取可能影響快速排序的效率),然后分別從數(shù)組的兩端掃描數(shù)組.
b.設(shè)兩個指示標(biāo)志(low指向起始位置竖般,high指向結(jié)束位置)甚垦,首先從尾部逆序開始,如果發(fā)現(xiàn)有元素比該基準(zhǔn)點(diǎn)的值小捻激,就交換low和high位置的值
c.然后從前半部分正序開始掃描制轰,如果有元素大于基準(zhǔn)點(diǎn)的值,就交換low和high位置的值胞谭,如此往復(fù)循環(huán)垃杖,直到lo>=hi,
d.把基準(zhǔn)點(diǎn)的值放到hi這個位置
e.使用遞歸方法對前半部分和后半部分進(jìn)行以上步驟的排序即可。
(2)圖解
第一輪排序:
然后將low和high重合前的數(shù)組和重合后數(shù)字之后的數(shù)組用遞歸方法進(jìn)行一樣的排序
注意:交換的是低位和高位的值丈屹,而不是基準(zhǔn)值
2.時間復(fù)雜度
快速排序時間復(fù)雜度是O(NlogN).
3.算法代碼實(shí)現(xiàn)(java)