摘要:算法思想冒泡排序?qū)儆谝环N典型的交換排序。冒泡排序常規(guī)版代碼實(shí)現(xiàn)下面詳細(xì)分析一下常規(guī)版的冒泡排序,整個(gè)算法流程其實(shí)就是上面實(shí)例所分析的過(guò)程。
算法思想
冒泡排序?qū)儆谝环N典型的交換排序。
交換排序顧名思義就是通過(guò)元素的兩兩比較,判斷是否符合要求,如過(guò)不符合就交換位置來(lái)達(dá)到排序的目的。冒泡排序名字的由來(lái)就是因?yàn)樵诮粨Q過(guò)程中,類(lèi)似水冒泡,小(大)的元素經(jīng)過(guò)不斷的交換由水底慢慢的浮到水的頂端。
冒泡排序的思想就是利用的比較交換,利用循環(huán)將第 i 小或者大的元素歸位,歸位操作利用的是對(duì) n 個(gè)元素中相鄰的兩個(gè)進(jìn)行比較,如果順序正確就不交換,如果順序錯(cuò)誤就進(jìn)行位置的交換。通過(guò)重復(fù)的循環(huán)訪問(wèn)數(shù)組,直到?jīng)]有可以交換的元素,那么整個(gè)排序就已經(jīng)完成了。
示例我們通過(guò)一個(gè)示例來(lái)理解一下基本的冒泡排序,假設(shè)當(dāng)前我們有一個(gè)數(shù)組 a,內(nèi)部元素為 3,4,1,5,2,即初始狀態(tài),如下圖所示。我們的目的就是通過(guò) n 趟比較來(lái)實(shí)現(xiàn)有底向上從大到小的的順序。
第一遍排序我們首先進(jìn)行第一遍排序,如下圖所示,紅色代表當(dāng)前比較的元素,綠色代表已經(jīng)歸位的元素。
(1)比較第一個(gè)和第二個(gè)元素,4>3,交換。
(2)比較第二個(gè)和第三個(gè)元素,1<3,不交換。
(3)比較第三個(gè)和第四個(gè)元素,5>1,交換。
(4)比較第四個(gè)和第五個(gè)元素,2>1,交換。
最后,我們可以看到 1 已經(jīng)位于最頂部。第一遍需要盡心四次比較才能把五個(gè)數(shù)比較完。
第二遍排序第二遍排序的初始狀態(tài)是第一遍排序的最終狀態(tài),即4,3,5,2,1。
(1)比較第一個(gè)和第二個(gè)元素,3<4,不交換。
(2)比較第二個(gè)和第三個(gè)元素,5>3,交換。
(3)比較第三個(gè)和第四個(gè)元素,2<3,不交換。
第二遍排序,會(huì)讓 2 歸位,并且這一遍只用進(jìn)行三次比較就可以了。
第三遍排序的初始狀態(tài)是第二遍排序的最終狀態(tài),即4,5,3,2,1。
(1)比較第一個(gè)和第二個(gè)元素,5>4,交換。
(2)比較第二個(gè)和第三個(gè)元素,3<4,不交換。
第三遍排序,會(huì)讓 3 歸位,并且這一遍只用進(jìn)行兩次比較就可以了。
然而我們可以看到這一次五個(gè)數(shù)已經(jīng)全部完成了歸位,但是當(dāng)我們采用普通的冒泡排序的時(shí)候,算法仍然會(huì)繼續(xù)向下進(jìn)行。
第四遍排序的初始狀態(tài)是第三遍排序的最終狀態(tài),即5,4,3,2,1。
這個(gè)時(shí)候就可以看出,排序?qū)嶋H上在第三遍已經(jīng)完成了,但是算法還是會(huì)繼續(xù)向下進(jìn)行,下面就進(jìn)行代碼實(shí)現(xiàn),看一下究竟是什么情況。。
算法 | 最好時(shí)間 | 最壞時(shí)間 | 平均時(shí)間 | 額外空間 | 穩(wěn)定性 |
---|---|---|---|---|---|
冒泡 | O(n) | O(n2) | O(n2) | 1 | 穩(wěn)定 |
關(guān)于穩(wěn)定性:因?yàn)樵诒容^的過(guò)程中,當(dāng)兩個(gè)相同大小的元素相鄰,只比較大或者小,所以相等的時(shí)候是不會(huì)交換位置的。而當(dāng)兩個(gè)相等元素離著比較遠(yuǎn)的時(shí)候,也只是會(huì)把他們交換到相鄰的位置。他們的位置前后關(guān)系不會(huì)發(fā)生任何變化,所以算法是穩(wěn)定的。
關(guān)于最優(yōu)時(shí)間復(fù)雜度為什么是O(n),當(dāng)然是優(yōu)化過(guò)算法之后了!大家繼續(xù)向下看就知道了!。
冒泡排序常規(guī)版-代碼實(shí)現(xiàn)下面詳細(xì)分析一下常規(guī)版的冒泡排序,整個(gè)算法流程其實(shí)就是上面實(shí)例所分析的過(guò)程。可以看出,我們?cè)谶M(jìn)行每一次大循環(huán)的時(shí)候,還要進(jìn)行一個(gè)小循環(huán)來(lái)遍歷相鄰元素并交換。所以我們的代碼中首先要有兩層循環(huán)。
外層循環(huán):即主循環(huán),需要輔助我們找到當(dāng)前第 i 小的元素來(lái)讓它歸位。所以我們會(huì)一直遍歷 n-2 次,這樣可以保證前 n-1 個(gè)元素都在正確的位置上,那么最后一個(gè)也可以落在正確的位置上了。
內(nèi)層循環(huán):即副循環(huán),需要輔助我們進(jìn)行相鄰元素之間的比較和換位,把大的或者小的浮到水面上。所以我們會(huì)一直遍歷 n-1-i 次這樣可以保證沒(méi)有歸位的盡量歸位,而歸位的就不用再比較了。
而上面的問(wèn)題,出現(xiàn)的原因也來(lái)源于這兩次無(wú)腦的循環(huán),正是因?yàn)檠h(huán)不顧一切的向下執(zhí)行,所以會(huì)導(dǎo)致在一些特殊情況下得多余。例如 5,4,3,1,2 的情況下,常規(guī)版會(huì)進(jìn)行四次循環(huán),但實(shí)際上第一次就已經(jīng)完成排序了。
/** * @author jyroy * 冒泡排序常規(guī)版 */ public class BubbleSortNormal { public static void main(String[] args) { int[] list = {3,4,1,5,2}; int temp = 0; // 開(kāi)辟一個(gè)臨時(shí)空間, 存放交換的中間值 // 要遍歷的次數(shù) for (int i = 0; i < list.length-1; i++) { System.out.format("第 %d 遍: ", i+1); //依次的比較相鄰兩個(gè)數(shù)的大小,遍歷一次后,把數(shù)組中第i小的數(shù)放在第i個(gè)位置上 for (int j = 0; j < list.length-1-i; j++) { // 比較相鄰的元素,如果前面的數(shù)小于后面的數(shù),就交換 if (list[j] < list[j+1]) { temp = list[j+1]; list[j+1] = list[j]; list[j] = temp; } System.out.format("第 %d 遍的第%d 次交換:", i+1,j+1); for(int count:list) { System.out.print(count); } System.out.println(""); } System.out.format("第 %d 遍最終結(jié)果:", i+1); for(int count:list) { System.out.print(count); } System.out.println(" #########################"); } } }
運(yùn)行結(jié)果
經(jīng)過(guò)了上述的討論和編碼,常規(guī)的冒泡排序已經(jīng)被我們實(shí)現(xiàn)了。那么接下來(lái)我們要討論的就是剛剛分析時(shí)候提出的問(wèn)題。
首先針對(duì)第一個(gè)問(wèn)題,當(dāng)我們進(jìn)行完第三遍的時(shí)候,實(shí)際上整個(gè)排序都已經(jīng)完成了,但是常規(guī)版還是會(huì)繼續(xù)排序。
可能在上面這個(gè)示例下,可能看不出來(lái)效果,但是當(dāng)數(shù)組是,5,4,3,1,2 的時(shí)候的時(shí)候就非常明顯了,實(shí)際上在第一次循環(huán)的時(shí)候整個(gè)數(shù)組就已經(jīng)完成排序,但是常規(guī)版的算法仍然會(huì)繼續(xù)后面的流程,這就是多余的了。
為了解決這個(gè)問(wèn)題,我們可以設(shè)置一個(gè)標(biāo)志位,用來(lái)表示當(dāng)前第 i 趟是否有交換,如果有則要進(jìn)行 i+1 趟,如果沒(méi)有,則說(shuō)明當(dāng)前數(shù)組已經(jīng)完成排序。實(shí)現(xiàn)代碼如下:
/** * @author jyroy * 冒泡排序優(yōu)化第一版 */ public class BubbleSoerOpt1 { public static void main(String[] args) { int[] list = {5,4,3,1,2}; int temp = 0; // 開(kāi)辟一個(gè)臨時(shí)空間, 存放交換的中間值 // 要遍歷的次數(shù) for (int i = 0; i < list.length-1; i++) { int flag = 1; //設(shè)置一個(gè)標(biāo)志位 //依次的比較相鄰兩個(gè)數(shù)的大小,遍歷一次后,把數(shù)組中第i小的數(shù)放在第i個(gè)位置上 for (int j = 0; j < list.length-1-i; j++) { // 比較相鄰的元素,如果前面的數(shù)小于后面的數(shù),交換 if (list[j] < list[j+1]) { temp = list[j+1]; list[j+1] = list[j]; list[j] = temp; flag = 0; //發(fā)生交換,標(biāo)志位置0 } } System.out.format("第 %d 遍最終結(jié)果:", i+1); for(int count:list) { System.out.print(count); } System.out.println(""); if (flag == 1) {//如果沒(méi)有交換過(guò)元素,則已經(jīng)有序 return; } } } }
運(yùn)行結(jié)果:可以看到優(yōu)化效果非常明顯,比正常情況下少了兩次的循環(huán)。
這個(gè)時(shí)候我們就來(lái)討論一下上面留下的一個(gè)小地方!沒(méi)錯(cuò)就是最優(yōu)時(shí)間復(fù)雜度為O(n)的問(wèn)題,我們?cè)谶M(jìn)行了這一次算法優(yōu)化之后,就可以做到了。
當(dāng)給我們一個(gè)數(shù)列,5,4,3,2,1,讓我們從大到小排序。沒(méi)錯(cuò),這是已經(jīng)排好序的啊,也就是說(shuō)因?yàn)闃?biāo)志位的存在,上面的循環(huán)只會(huì)進(jìn)行一遍,flag沒(méi)有變成1,整個(gè)算法就結(jié)束了,這也就是 O(n) 的來(lái)歷了!
算法的第二次優(yōu)化除了上面這個(gè)問(wèn)題,在冒泡排序中還有一個(gè)問(wèn)題存在,就是第 i 趟排的第 i 小或者大的元素已經(jīng)在第 i 位上了,甚至可能第 i-1 位也已經(jīng)歸位了,那么在內(nèi)層循環(huán)的時(shí)候,有這種情況出現(xiàn)就會(huì)導(dǎo)致多余的比較出現(xiàn)。例如:6,4,7,5,1,3,2,當(dāng)我們進(jìn)行第一次排序的時(shí)候,結(jié)果為6,7,5,4,3,2,1,實(shí)際上后面有很多次交換比較都是多余的,因?yàn)闆](méi)有產(chǎn)生交換操作。
我們用剛剛優(yōu)化過(guò)一次的算法,跑一下這個(gè)數(shù)組。
/** * @author jyroy * 冒泡排序優(yōu)化第一版 */ public class BubbleSoerOpt1 { public static void main(String[] args) { int[] list = {6,4,7,5,1,3,2}; int len = list.length-1; int temp = 0; // 開(kāi)辟一個(gè)臨時(shí)空間, 存放交換的中間值 // 要遍歷的次數(shù) for (int i = 0; i < list.length-1; i++) { int flag = 1; //設(shè)置一個(gè)標(biāo)志位 //依次的比較相鄰兩個(gè)數(shù)的大小,遍歷一次后,把數(shù)組中第i小的數(shù)放在第i個(gè)位置上 for (int j = 0; j < len-i; j++) { // 比較相鄰的元素,如果前面的數(shù)小于后面的數(shù),交換 if (list[j] < list[j+1]) { temp = list[j+1]; list[j+1] = list[j]; list[j] = temp; flag = 0; //發(fā)生交換,標(biāo)志位置0 } System.out.format("第 %d 遍第%d 趟結(jié)果:", i+1, j+1); for(int count:list) { System.out.print(count); } System.out.println(""); } System.out.format("第 %d 遍最終結(jié)果:", i+1); for(int count:list) { System.out.print(count); } System.out.println(""); if (flag == 1) {//如果沒(méi)有交換過(guò)元素,則已經(jīng)有序 return; } } } }
運(yùn)行結(jié)果:可以看出,第三趟的多次比較實(shí)際上可以沒(méi)有,因?yàn)橹虚g幾個(gè)位置在第二趟就沒(méi)有過(guò)交換。
針對(duì)上述的問(wèn)題,我們可以想到,利用一個(gè)標(biāo)志位,記錄一下當(dāng)前第 i 趟所交換的最后一個(gè)位置的下標(biāo),在進(jìn)行第 i+1 趟的時(shí)候,只需要內(nèi)循環(huán)到這個(gè)下標(biāo)的位置就可以了,因?yàn)楹竺嫖恢蒙系脑卦谏弦惶酥袥](méi)有換位,這一次也不可能會(huì)換位置了。基于這個(gè)原因,我們可以進(jìn)一步優(yōu)化我們的代碼。
/** * @author jyroy * 冒泡排序優(yōu)化第二版 */ public class BubbleSoerOpt2 { public static void main(String[] args) { int[] list = {6,4,7,5,1,3,2}; int len = list.length-1; int temp = 0; // 開(kāi)辟一個(gè)臨時(shí)空間, 存放交換的中間值 int tempPostion = 0; // 記錄最后一次交換的位置 // 要遍歷的次數(shù) for (int i = 0; i < list.length-1; i++) { int flag = 1; //設(shè)置一個(gè)標(biāo)志位 //依次的比較相鄰兩個(gè)數(shù)的大小,遍歷一次后,把數(shù)組中第i小的數(shù)放在第i個(gè)位置上 for (int j = 0; j < len; j++) { // 比較相鄰的元素,如果前面的數(shù)小于后面的數(shù),交換 if (list[j] < list[j+1]) { temp = list[j+1]; list[j+1] = list[j]; list[j] = temp; flag = 0; //發(fā)生交換,標(biāo)志位置0 tempPostion = j; //記錄交換的位置 } System.out.format("第 %d 遍第%d 趟結(jié)果:", i+1, j+1); for(int count:list) { System.out.print(count); } System.out.println(""); } len = tempPostion; //把最后一次交換的位置給len,來(lái)縮減內(nèi)循環(huán)的次數(shù) System.out.format("第 %d 遍最終結(jié)果:", i+1); for(int count:list) { System.out.print(count); } System.out.println(""); if (flag == 1) {//如果沒(méi)有交換過(guò)元素,則已經(jīng)有序 return; } } } }
運(yùn)行結(jié)果:
可以清楚的看到,部分內(nèi)循環(huán)多余的比較已經(jīng)被去掉了,算法得到了進(jìn)一步的優(yōu)化
因?yàn)樗接邢蓿詫?duì)算法的描述和分析存在一些缺陷,而且選取的例子可能有些不恰當(dāng),大家可以多試一些數(shù)列。
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://m.specialneedsforspecialkids.com/yun/75727.html
摘要:之所以把冒泡排序選擇排序插入排序放在一起比較,是因?yàn)樗鼈兊钠骄鶗r(shí)間復(fù)雜度都為。其中,冒泡排序就是原地排序算法。所以冒泡排序是穩(wěn)定的排序算法。選擇排序思路選擇排序算法的實(shí)現(xiàn)思路有點(diǎn)類(lèi)似插入排序,也分已排序區(qū)間和未排序區(qū)間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 算法為王。 想學(xué)好前端,先練好內(nèi)功,...
摘要:外層循環(huán)讓內(nèi)層循環(huán)繼續(xù)排沒(méi)有排序過(guò)的數(shù)組,排序過(guò)的不用再排。那么優(yōu)化后的算法能快多少呢。我們都以數(shù)組長(zhǎng)度為來(lái)計(jì)算傳統(tǒng)冒泡排序步,優(yōu)化后的冒泡排序步。因?yàn)閮?yōu)化后的冒泡排序,每排完一次,最后一個(gè)數(shù)已經(jīng)是最大的,就不需要再比較了。 冒泡排序的時(shí)間用大O表示法是O(N^2). 傳統(tǒng)的冒泡排序: /** * @param total 要排序的數(shù)組長(zhǎng)度 */ public void sort(in...
摘要:函數(shù)詳解函數(shù)原型函數(shù)的作用及用法函數(shù)的參數(shù)函數(shù)實(shí)例排序一個(gè)整型數(shù)組排序一個(gè)結(jié)構(gòu)體用冒泡排序模擬一個(gè)函數(shù)函數(shù)原型函數(shù)的作用及用法函數(shù)的功能是對(duì)數(shù)組進(jìn)行排序,數(shù)組有個(gè)元素,每個(gè)元素大小為可以排序數(shù)字,字符,結(jié)構(gòu)體等多種類(lèi)型 ...
閱讀 462·2023-04-25 23:00
閱讀 3493·2021-11-22 13:54
閱讀 1892·2021-10-27 14:14
閱讀 1485·2019-08-30 13:59
閱讀 3510·2019-08-23 16:15
閱讀 1957·2019-08-23 16:06
閱讀 3326·2019-08-23 15:26
閱讀 1256·2019-08-23 13:48