Java 十大排序算法之冒泡排序刨析
冒泡排序原理
①比較相鄰的元素，如果前一個元素比后一個元素大，則交換這兩個元素的位置
②對每一對相鄰的元素循環(huán)上面的步驟，最終最后面的元素就是最大值
冒泡排序API設(shè)計
| 類名 | Bubble |
| 構(gòu)造方法 | Bubble:創(chuàng)建Bubble對象 |
| 成員方法 |
1.public static void sort(Comparable[] a):對數(shù)組內(nèi)元素進行排序 2.private static void greater(Comparable v,Comparable w)；判斷v是否大于w 3.private static void exchange(Comparable[] a,int x,int y):交換a數(shù)組中，索引x和索引y處的值 |
冒泡排序的代碼實現(xiàn)
public class Bubble {
//對數(shù)組a進行排序
public static void sort(Comparable[] a){
for(int i=a.length-1;i>0;i--){
for(int j=0;j<i;j++){
if(greater(a[j],a[j+1])){
exchange(a,j,j+1);
}
}
}
}
//比較v元素是否大于w元素
private static boolean greater(Comparable v,Comparable w){
return v.compareTo(w)>0;
}
//數(shù)組元素x和y交換位置
private static void exchange(Comparable[] a,int x,int y){
Comparable t=a[x];
a[x]=a[y];
a[y]=t;
}
}
//測試代碼
class Test{
public static void main(String[] args) {
Integer[] a={4,5,6,3,2,1};
Bubble.sort(a);
System.out.println(Arrays.toString(a));
}
}
測試結(jié)果：
冒泡排序的時間復(fù)雜度分析
冒泡排序雖然采用了雙層for循環(huán)遍歷，但是真正完成排序的代碼在內(nèi)循環(huán)中，所以主要分析內(nèi)層循環(huán)體的執(zhí)行次數(shù)即可
在最壞的情況下。即數(shù)組為{6,5,4,3,2,1}的逆序
元素的比較次數(shù)為：(N-1)+(N-2)+(N-3)+...+2+1=
((N-1)+1)*(N-1)/2=N^2/2-N/2;
元素的交換次數(shù)為：(N-1)+(N-2)+(N-3)+...+2+1=
((N-1)+1)*(N-1)/2=N^2/2-N/2;
總執(zhí)行次數(shù)為：2*(N^2/2-N/2)=N^2-N;
根據(jù)大O推導(dǎo)法則，保留最高階項，即冒泡排序的時間復(fù)雜度為O(N^2)
到此這篇關(guān)于Java 十大排序算法之冒泡排序刨析的文章就介紹到這了,更多相關(guān)Java 冒泡排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
深入理解Spring注解@Async解決異步調(diào)用問題
這篇文章主要介紹了深入理解Spring注解@Async解決異步調(diào)用問題，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-07-07
順序表是用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲。本文主要介紹了順序表的實現(xiàn)與常用操作，需要的可以參考一下2022-09-09
這篇文章主要介紹了Java集合中的LinkedHashMap使用解析,LinkedHashMap是繼承于HashMap的,所以它的很多屬性和方法都是HashMap中的,那么它是怎么實現(xiàn)有序存儲的呢,需要的朋友可以參考下2023-12-12
在使用Jmeter進行性能測試或者接口自動化測試工作中,經(jīng)常會用到的一個功能,就是斷言,本文主要介紹了jmeter斷言的三種實現(xiàn)方式,2024-01-01
程序中的變量是?null，就意味著它沒有引用指向或者說沒有指針。這時，我們對這個變量進行任何操作，都必然會引發(fā)空指針異常，本文主要介紹了Java中怎樣處理空指針異常，感興趣的可以了解一下2022-05-05
Java中new關(guān)鍵字和newInstance方法的區(qū)別分享
在初始化一個類，生成一個實例的時候，newInstance()方法和new關(guān)鍵字除了一個是方法一個是關(guān)鍵字外，最主要的區(qū)別是創(chuàng)建對象的方式不同2013-07-07
spring動態(tài)控制定時任務(wù)的實現(xiàn)
在實際項目中,經(jīng)常需要動態(tài)的控制定時任務(wù),比如通過接口增加、啟動、停止、刪除定時任務(wù),本文主要介紹了spring動態(tài)控制定時任務(wù)的實現(xiàn),感興趣的可以了解一下2024-01-01
本文先介紹線性表的幾個基本組成部分：數(shù)組、單向鏈表、雙向鏈表；隨后給出雙向鏈表的C、C++和Java三種語言的實現(xiàn),需要的朋友可以參考下2015-07-07
JAVA WSIMPORT生成WEBSERVICE客戶端401認證過程圖解
這篇文章主要介紹了JAVA WSIMPORT生成WEBSERVICE客戶端401認證過程圖解,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-10-10
SpringMVC實現(xiàn)返回響應(yīng)的項目實踐
本文主要介紹了SpringMVC實現(xiàn)返回響應(yīng)的項目實踐,包含返回靜態(tài)頁面,返回數(shù)據(jù),返回html片段等實例,具有一定的參考價值,感興趣的可以了解一下2024-02-02