今天動力節(jié)點(diǎn)java培訓(xùn)機(jī)構(gòu)小編為大家介紹Java實(shí)現(xiàn)冒泡排序算法及對其的簡單優(yōu)化示例，冒泡排序的最差時間復(fù)雜度為O(n^2),最優(yōu)時間復(fù)雜度為O(n),存在優(yōu)化的余地，希望能夠幫助到正在學(xué)習(xí)java的零基礎(chǔ)學(xué)員，下面就隨小吧一起看看吧。

　　Java實(shí)現(xiàn)冒泡排序原理

　　java冒泡排序大概是所有程序員都會用的算法，也是最熟悉的算法之一。

　　它的思路并不復(fù)雜：

　　設(shè)現(xiàn)在要給數(shù)組arr[]排序，它有n個元素。

　　1、如果n=1：顯然不用排了。(實(shí)際上這個討論似乎沒什么必要)

　　2、如果n>1：

　?。?）我們從第一個元素開始，把每兩個相鄰元素進(jìn)行比較，如果前面的元素比后面的大，那么在最后的結(jié)果里面前者肯定排在后面。所以，我們把這兩個元素交換。然后進(jìn)行下兩個相鄰的元素的比較。如此直到最后一對元素比較完畢，則第一輪排序完成?？梢钥隙?，最后一個元素一定是數(shù)組中最大的(因?yàn)槊看味及严鄬Υ蟮姆诺胶竺媪?。

　?。?）重復(fù)上述過程，這次我們無需考慮最后一個，因?yàn)樗呀?jīng)排好了。

　?。?）如此直到只剩一個元素，這個元素一定是最小的，那么我們的排序可以結(jié)束了。顯然，進(jìn)行了n-1次排序。

　　上述過程中，每次(或者叫做“輪”)排序都會有一個數(shù)從某個位置慢慢“浮動”到最終的位置(畫個示意圖，把數(shù)組畫成豎直的就可以看出來)，就像冒泡一樣，所以，它被稱為“冒泡排序法”。

　　代碼實(shí)現(xiàn)：

public class BubbleSort{
? ?public static void main(String[] args){
? ? ?int score[] = {67, 69, 75, 87, 89, 90, 99, 100};
? ? ?for (int i = 0; i < score.length -1; i++){? //最多做n-1趟排序
? ? ? ?for(int j = 0 ;j < score.length - i - 1; j++){? //對當(dāng)前無序區(qū)間score[0......length-i-1]進(jìn)行排序(j的范圍很關(guān)鍵，這個范圍實(shí)在逐步縮小的)
? ? ? ? ?if(score[j] < score[j + 1]){? //把小的值交換到后面
? ? ? ? ? ?int temp = score[j];
? ? ? ? ? ?score[j] = score[j + 1];
? ? ? ? ? ?score[j + 1] = temp;
? ? ? ? ?}
? ? ? ?}? ? ??

? ? ? ?System.out.print("第" + (i + 1) + "次排序結(jié)果：");
? ? ? ?for(int a = 0; a < score.length; a++){
? ? ? ? ?System.out.print(score[a] + "\t");
? ? ? ?}
? ? ? ?System.out.println("");
? ? ?}

? ? ? ?System.out.print("最終排序結(jié)果：");
? ? ? ?for(int a = 0; a < score.length; a++){
? ? ? ? ?System.out.print(score[a] + "\t");
? ? ?}
? ?}
?}

算法性能/復(fù)雜度

　　我們忽略掉循環(huán)變量自增和初始化的時間。先分析算法的比較次數(shù)。容易看出，上面這種未經(jīng)任何改進(jìn)的冒泡排序無論輸入數(shù)據(jù)如何都會進(jìn)行n-1輪排序，而每輪排序需要比較的次數(shù)從n-1遞減到0。那么，總的比較次數(shù)即是 (n-1)+(n-2)+...+2+1 = (n-1)n/2≈(n^2)/2。

　　再來看下賦值次數(shù)。這里的賦值是指其中的交換操作，對于上述代碼，1次交換等于三次賦值。由于并非每次都必須交換，因此，賦值操作的次數(shù)與輸入數(shù)據(jù)有關(guān)。最佳情況(best case)下，即一開始就是有序的情況下，賦值次數(shù)為0。 而最壞情況(worst case)下，賦值次數(shù)為(n-1)n/2。假設(shè)輸入數(shù)據(jù)平均(或者說“完全隨機(jī)”)分布，那么大約有交換次數(shù)為比較次數(shù)的一半。由上面的結(jié)果，可以得到平均情況(average case)下，賦值次數(shù)為 3/2 * (n^2)/2 = 3/4*(n^2).

　　綜上，無論在何種情況下，冒泡排序空間復(fù)雜度(額外空間)總是O(1)。

　　改進(jìn)

　　在數(shù)據(jù)完全有序的時候展現(xiàn)出最優(yōu)時間復(fù)雜度，為O(n)。其他情況下，幾乎總是O(n^2)。因此，算法在數(shù)據(jù)基本有序的情況下，性能最好。

　　但是，上面的代碼怎么可能出現(xiàn)O(n)復(fù)雜度呢?實(shí)際上，因?yàn)樯厦孀⒅氐氖腔舅悸?，因此只是最簡單情況，要使算法在最佳情況下有O(n)復(fù)雜度，需要做一些改進(jìn)，改進(jìn)后的代碼為：

public static void bubbleSort(int[] arr) {
? int temp = 0;
? boolean swap;
? for (int i = arr.length - 1; i > 0; --i) { // 每次需要排序的長度
? ? swap=false;
? ? for (int j = 0; j < i; ++j) { // 從第一個元素到第i個元素
? ? ? if (arr[j] > arr[j + 1]) {
? ? ? ? temp = arr[j];
? ? ? ? arr[j] = arr[j + 1];
? ? ? ? arr[j + 1] = temp;
? ? ? ? swap=true;
? ? ? }
? ? }//loop j
? ? if (swap==false){
? ? ? break;
? ? }
? }//loop i
}// method bubbleSort

實(shí)際上，由于在大量數(shù)據(jù)的情況下幾乎不使用冒泡排序，而使用小數(shù)據(jù)的時候增加的布爾變量反而會造成額外的開銷。

　　算法穩(wěn)定性

　　容易看出，在相鄰元素相等時，我們并不需要交換它們的位置，所以，冒泡排序是穩(wěn)定排序。

　　算法適用場景

　　冒泡排序思路簡單，代碼也簡單，特別適合小數(shù)據(jù)的排序。但是，由于算法復(fù)雜度較高，在數(shù)據(jù)量大的時候不適合使用。如果一定要在較多數(shù)據(jù)的時候使用，最好對算法加以改進(jìn)，例如選擇排序法。

以上就是動力節(jié)點(diǎn)java培訓(xùn)機(jī)構(gòu)小編介紹的“Java實(shí)現(xiàn)冒泡排序算法及對其的簡單優(yōu)化示例”的內(nèi)容，希望能夠幫助到大家，更多java最新資訊請繼續(xù)關(guān)注動力節(jié)點(diǎn)java培訓(xùn)機(jī)構(gòu)官網(wǎng)，每天會有精彩內(nèi)容分享與你。

相關(guān)免費(fèi)視頻教程推薦

java新手入門教程下載之冒泡排序分析：http://www.soulsinkind.com/xiazai/2539.html