一、冒泡排序
談到排序算法，首先映入腦中的便是冒泡排序站粟，這也是我接觸的第一種排序算法，的確算是一個比較經(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）
