排序算法1:交換排序

一、冒泡排序

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

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末调俘,一起剝皮案震驚了整個濱河市伶棒,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌彩库,老刑警劉巖肤无,帶你破解...
    沈念sama閱讀 222,729評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異骇钦,居然都是意外死亡宛渐,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評論 3 399
  • 文/潘曉璐 我一進(jìn)店門眯搭,熙熙樓的掌柜王于貴愁眉苦臉地迎上來窥翩,“玉大人,你說我怎么就攤上這事鳞仙】芪茫” “怎么了?”我有些...
    開封第一講書人閱讀 169,461評論 0 362
  • 文/不壞的土叔 我叫張陵棍好,是天一觀的道長仗岸。 經(jīng)常有香客問我,道長借笙,這世上最難降的妖魔是什么扒怖? 我笑而不...
    開封第一講書人閱讀 60,135評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮提澎,結(jié)果婚禮上姚垃,老公的妹妹穿的比我還像新娘念链。我一直安慰自己盼忌,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,130評論 6 398
  • 文/花漫 我一把揭開白布掂墓。 她就那樣靜靜地躺著谦纱,像睡著了一般。 火紅的嫁衣襯著肌膚如雪君编。 梳的紋絲不亂的頭發(fā)上跨嘉,一...
    開封第一講書人閱讀 52,736評論 1 312
  • 那天,我揣著相機(jī)與錄音吃嘿,去河邊找鬼祠乃。 笑死,一個胖子當(dāng)著我的面吹牛兑燥,可吹牛的內(nèi)容都是我干的亮瓷。 我是一名探鬼主播,決...
    沈念sama閱讀 41,179評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼降瞳,長吁一口氣:“原來是場噩夢啊……” “哼嘱支!你這毒婦竟也來了蚓胸?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,124評論 0 277
  • 序言:老撾萬榮一對情侶失蹤除师,失蹤者是張志新(化名)和其女友劉穎沛膳,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體汛聚,經(jīng)...
    沈念sama閱讀 46,657評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡锹安,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,723評論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了倚舀。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片八毯。...
    茶點(diǎn)故事閱讀 40,872評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖瞄桨,靈堂內(nèi)的尸體忽然破棺而出话速,到底是詐尸還是另有隱情,我是刑警寧澤芯侥,帶...
    沈念sama閱讀 36,533評論 5 351
  • 正文 年R本政府宣布泊交,位于F島的核電站,受9級特大地震影響柱查,放射性物質(zhì)發(fā)生泄漏廓俭。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,213評論 3 336
  • 文/蒙蒙 一唉工、第九天 我趴在偏房一處隱蔽的房頂上張望研乒。 院中可真熱鬧,春花似錦淋硝、人聲如沸雹熬。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽竿报。三九已至,卻和暖如春继谚,著一層夾襖步出監(jiān)牢的瞬間烈菌,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評論 1 274
  • 我被黑心中介騙來泰國打工花履, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留芽世,地道東北人。 一個月前我還...
    沈念sama閱讀 49,304評論 3 379
  • 正文 我出身青樓诡壁,卻偏偏與公主長得像济瓢,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子欢峰,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,876評論 2 361

推薦閱讀更多精彩內(nèi)容