Java數(shù)據(jù)結(jié)構(gòu)和算法之冒泡,選擇和插入排序算法
1、冒泡排序
這個(gè)名詞的由來(lái)很好理解,一般河水中的冒泡,水底剛冒出來(lái)的時(shí)候是比較小的,隨著慢慢向水面浮起會(huì)逐漸增大,這物理規(guī)律我不作過(guò)多解釋,大家只需要了解即可。
冒泡算法的運(yùn)作規(guī)律如下:
①、比較相鄰的元素。如果第一個(gè)比第二個(gè)大,就交換他們兩個(gè)。
②、對(duì)每一對(duì)相鄰元素作同樣的工作,從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后,最后的元素會(huì)是最大的數(shù)(也就是第一波冒泡完成)。
③、針對(duì)所有的元素重復(fù)以上的步驟,除了最后一個(gè)。
④、持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟,直到?jīng)]有任何一對(duì)數(shù)字需要比較。
代碼如下:
package com.ys.sort; public class BubbleSort { public static int[] sort(int[] array){ //這里for循環(huán)表示總共需要比較多少輪 for(int i = 1 ; i < array.length; i++){ //設(shè)定一個(gè)標(biāo)記,若為true,則表示此次循環(huán)沒(méi)有進(jìn)行交換,也就是待排序列已經(jīng)有序,排序已經(jīng)完成。 boolean flag = true; //這里for循環(huán)表示每輪比較參與的元素下標(biāo) //對(duì)當(dāng)前無(wú)序區(qū)間array[0......length-i]進(jìn)行排序 //j的范圍很關(guān)鍵,這個(gè)范圍是在逐步縮小的,因?yàn)槊枯啽容^都會(huì)將最大的放在右邊 for(int j = 0 ; j < array.length-i ; j++){ if(array[j]>array[j+1]){ int temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; flag = false; } } if(flag){ break; } //第 i輪排序的結(jié)果為 System.out.print("第"+i+"輪排序后的結(jié)果為:"); display(array); } return array; } //遍歷顯示數(shù)組 public static void display(int[] array){ for(int i = 0 ; i < array.length ; i++){ System.out.print(array[i]+" "); } System.out.println(); } public static void main(String[] args) { int[] array = {4,2,8,9,5,7,6,1,3}; //未排序數(shù)組順序?yàn)? System.out.println("未排序數(shù)組順序?yàn)椋?); display(array); System.out.println("-----------------------"); array = sort(array); System.out.println("-----------------------"); System.out.println("經(jīng)過(guò)冒泡排序后的數(shù)組順序?yàn)椋?); display(array); } }
結(jié)果如下:
本來(lái)應(yīng)該是 8 輪排序的,這里我們只進(jìn)行了 7 輪排序,因?yàn)榈?7 輪排序之后已經(jīng)是有序數(shù)組了。
冒泡排序解釋:
冒泡排序是由兩個(gè)for循環(huán)構(gòu)成,第一個(gè)for循環(huán)的變量 i 表示總共需要多少輪比較,第二個(gè)for循環(huán)的變量 j 表示每輪參與比較的元素下標(biāo)【0,1,......,length-i】,因?yàn)槊枯啽容^都會(huì)出現(xiàn)一個(gè)最大值放在最右邊,所以每輪比較后的元素個(gè)數(shù)都會(huì)少一個(gè),這也是為什么 j 的范圍是逐漸減小的。相信大家理解之后快速寫出一個(gè)冒泡排序并不難。
冒泡排序性能分析:
假設(shè)參與比較的數(shù)組元素個(gè)數(shù)為 N,則第一輪排序有 N-1 次比較,第二輪有 N-2 次,如此類推,這種序列的求和公式為:
?。∟-1)+(N-2)+...+1 = N*(N-1)/2
當(dāng) N 的值很大時(shí),算法比較次數(shù)約為 N2/2次比較,忽略減1。
假設(shè)數(shù)據(jù)是隨機(jī)的,那么每次比較可能要交換位置,可能不會(huì)交換,假設(shè)概率為50%,那么交換次數(shù)為N2/4。不過(guò)如果是最壞的情況,初始數(shù)據(jù)是逆序的,那么每次比較都要交換位置。
交換和比較次數(shù)都和N2 成正比。由于常數(shù)不算大 O 表示法中,忽略 2 和 4,那么冒泡排序運(yùn)行都需要 O(N2) 時(shí)間級(jí)別。
其實(shí)無(wú)論何時(shí),只要看見(jiàn)一個(gè)循環(huán)嵌套在另一個(gè)循環(huán)中,我們都可以懷疑這個(gè)算法的運(yùn)行時(shí)間為 O(N2)級(jí),外層循環(huán)執(zhí)行 N 次,內(nèi)層循環(huán)對(duì)每一次外層循環(huán)都執(zhí)行N次(或者幾分之N次)。這就意味著大約需要執(zhí)行N2次某個(gè)基本操作?! ?/p>
2、選擇排序
選擇排序是每一次從待排序的數(shù)據(jù)元素中選出最小的一個(gè)元素,存放在序列的起始位置,直到全部待排序的數(shù)據(jù)元素排完。
分為三步:
- ①、從待排序序列中,找到關(guān)鍵字最小的元素
- ②、如果最小元素不是待排序序列的第一個(gè)元素,將其和第一個(gè)元素互換
- ③、從余下的 N - 1 個(gè)元素中,找出關(guān)鍵字最小的元素,重復(fù)(1)、(2)步,直到排序結(jié)束
代碼如下:
package com.ys.sort; public class ChoiceSort { public static int[] sort(int[] array){ //總共要經(jīng)過(guò)N-1輪比較 for(int i = 0 ; i < array.length-1 ; i++){ int min = i; //每輪需要比較的次數(shù) for(int j = i+1 ; j < array.length ; j++){ if(array[j]<array[min]){ min = j;//記錄目前能找到的最小值元素的下標(biāo) } } //將找到的最小值和i位置所在的值進(jìn)行交換 if(i != min){ int temp = array[i]; array[i] = array[min]; array[min] = temp; } //第 i輪排序的結(jié)果為 System.out.print("第"+(i+1)+"輪排序后的結(jié)果為:"); display(array); } return array; } //遍歷顯示數(shù)組 public static void display(int[] array){ for(int i = 0 ; i < array.length ; i++){ System.out.print(array[i]+" "); } System.out.println(); } public static void main(String[] args){ int[] array = {4,2,8,9,5,7,6,1,3}; //未排序數(shù)組順序?yàn)? System.out.println("未排序數(shù)組順序?yàn)椋?); display(array); System.out.println("-----------------------"); array = sort(array); System.out.println("-----------------------"); System.out.println("經(jīng)過(guò)選擇排序后的數(shù)組順序?yàn)椋?); display(array); } }
運(yùn)行結(jié)果:
選擇排序性能分析:
選擇排序和冒泡排序執(zhí)行了相同次數(shù)的比較:N*(N-1)/2,但是至多只進(jìn)行了N次交換。
當(dāng) N 值很大時(shí),比較次數(shù)是主要的,所以和冒泡排序一樣,用大O表示是O(N2) 時(shí)間級(jí)別。但是由于選擇排序交換的次數(shù)少,所以選擇排序無(wú)疑是比冒泡排序快的。當(dāng) N 值較小時(shí),如果交換時(shí)間比選擇時(shí)間大的多,那么選擇排序是相當(dāng)快的。
3、插入排序
直接插入排序基本思想是每一步將一個(gè)待排序的記錄,插入到前面已經(jīng)排好序的有序序列中去,直到插完所有元素為止。
插入排序還分為直接插入排序、二分插入排序、鏈表插入排序、希爾排序等等,這里我們只是以直接插入排序講解,后面講高級(jí)排序的時(shí)候會(huì)將其他的。
代碼如下:
package com.ys.sort; public class InsertSort { public static int[] sort(int[] array){ int j; //從下標(biāo)為1的元素開(kāi)始選擇合適的位置插入,因?yàn)橄聵?biāo)為0的只有一個(gè)元素,默認(rèn)是有序的 for(int i = 1 ; i < array.length ; i++){ int tmp = array[i];//記錄要插入的數(shù)據(jù) j = i; while(j > 0 && tmp < array[j-1]){//從已經(jīng)排序的序列最右邊的開(kāi)始比較,找到比其小的數(shù) array[j] = array[j-1];//向后挪動(dòng) j--; } array[j] = tmp;//存在比其小的數(shù),插入 } return array; } //遍歷顯示數(shù)組 public static void display(int[] array){ for(int i = 0 ; i < array.length ; i++){ System.out.print(array[i]+" "); } System.out.println(); } public static void main(String[] args){ int[] array = {4,2,8,9,5,7,6,1,3}; //未排序數(shù)組順序?yàn)? System.out.println("未排序數(shù)組順序?yàn)椋?); display(array); System.out.println("-----------------------"); array = sort(array); System.out.println("-----------------------"); System.out.println("經(jīng)過(guò)插入排序后的數(shù)組順序?yàn)椋?); display(array); } }
運(yùn)行結(jié)果:
插入排序性能分析:
在第一輪排序中,它最多比較一次,第二輪最多比較兩次,一次類推,第N輪,最多比較N-1次。因此有1+2+3+...+N-1 =N*(N-1)/2。
假設(shè)在每一輪排序發(fā)現(xiàn)插入點(diǎn)時(shí),平均只有全體數(shù)據(jù)項(xiàng)的一半真的進(jìn)行了比較,我們除以2得到:N*(N-1)/4。用大O表示法大致需要需要 O(N2) 時(shí)間級(jí)別。
復(fù)制的次數(shù)大致等于比較的次數(shù),但是一次復(fù)制與一次交換的時(shí)間耗時(shí)不同,所以相對(duì)于隨機(jī)數(shù)據(jù),插入排序比冒泡快一倍,比選擇排序略快。
這里需要注意的是,如果要進(jìn)行逆序排列,那么每次比較和移動(dòng)都會(huì)進(jìn)行,這時(shí)候并不會(huì)比冒泡排序快。
4、總結(jié)
上面講的三種排序,冒泡、選擇、插入用大 O 表示法都需要O(N2) 時(shí)間級(jí)別。一般不會(huì)選擇冒泡排序,雖然冒泡排序書寫是最簡(jiǎn)單的,但是平均性能是沒(méi)有選擇排序和插入排序好的。
選擇排序把交換次數(shù)降低到最低,但是比較次數(shù)還是挺大的。當(dāng)數(shù)據(jù)量小,并且交換數(shù)據(jù)相對(duì)于比較數(shù)據(jù)更加耗時(shí)的情況下,可以應(yīng)用選擇排序。
在大多數(shù)情況下,假設(shè)數(shù)據(jù)量比較小或基本有序時(shí),插入排序是三種算法中最好的選擇。
后面我們會(huì)講解高級(jí)排序,大O表示法的時(shí)間級(jí)別將比O(N2)小?!?/p>
本篇文章就到這里了,希望能夠給你帶來(lái)幫助,也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!
相關(guān)文章
IDEA啟動(dòng)Springboot報(bào)錯(cuò):無(wú)效的目標(biāo)發(fā)行版:17 的解決辦法
這篇文章主要給大家介紹了IDEA啟動(dòng)Springboot報(bào)錯(cuò):無(wú)效的目標(biāo)發(fā)行版:17 的解決辦法,文中通過(guò)代碼示例和圖文講解的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作有一定的幫助,需要的朋友可以參考下2024-02-02Springboot工具類ReflectionUtils使用教程
這篇文章主要介紹了Springboot內(nèi)置的工具類之ReflectionUtils的使用,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)吧2022-12-12Java超詳細(xì)精講數(shù)據(jù)結(jié)構(gòu)之bfs與雙端隊(duì)列
廣搜BFS的基本思想是: 首先訪問(wèn)初始點(diǎn)v并將其標(biāo)志為已經(jīng)訪問(wèn)。接著通過(guò)鄰接關(guān)系將鄰接點(diǎn)入隊(duì)。然后每訪問(wèn)過(guò)一個(gè)頂點(diǎn)則出隊(duì)。按照順序,訪問(wèn)每一個(gè)頂點(diǎn)的所有未被訪問(wèn)過(guò)的頂點(diǎn)直到所有的頂點(diǎn)均被訪問(wèn)過(guò)。廣度優(yōu)先遍歷類似與層次遍歷2022-07-07SpringBoot整合mybatis-plus實(shí)現(xiàn)分頁(yè)查詢功能
這篇文章主要介紹了SpringBoot整合mybatis-plus實(shí)現(xiàn)分頁(yè)查詢功能,pringBoot分頁(yè)查詢的兩種寫法,一種是手動(dòng)實(shí)現(xiàn),另一種是使用框架實(shí)現(xiàn),現(xiàn)在我將具體的實(shí)現(xiàn)流程分享一下,需要的朋友可以參考下2023-11-11springboot 配置日志 打印不出來(lái)sql的解決方法
這篇文章主要介紹了springboot 配置日志 打印不出來(lái)sql的解決方法,幫助大家更好的理解和使用springboot框架,感興趣的朋友可以了解下2020-11-11Java?SpringBoot?@Async實(shí)現(xiàn)異步任務(wù)的流程分析
這篇文章主要介紹了Java?SpringBoot?@Async實(shí)現(xiàn)異步任務(wù),主要包括@Async?異步任務(wù)-無(wú)返回值,@Async?異步任務(wù)-有返回值,@Async?+?自定義線程池的操作代碼,需要的朋友可以參考下2022-12-12Springboot?內(nèi)部服務(wù)調(diào)用方式
這篇文章主要介紹了Springboot?內(nèi)部服務(wù)調(diào)用方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-03-03ZooKeeper開(kāi)發(fā)實(shí)際應(yīng)用案例實(shí)戰(zhàn)
這篇文章主要為大家介紹了ZooKeeper開(kāi)發(fā)的實(shí)際應(yīng)用案例實(shí)戰(zhàn),文中附含詳細(xì)開(kāi)發(fā)應(yīng)用源碼,有需要的朋友可以借鑒參考下,希望能夠有所幫助2022-01-01springboot通過(guò)jar包啟動(dòng)中文日志亂碼問(wèn)題及解決
這篇文章主要介紹了springboot通過(guò)jar包啟動(dòng)中文日志亂碼問(wèn)題及解決方案,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-06-06