欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java實(shí)現(xiàn)冒泡排序算法及對其的簡單優(yōu)化示例

 更新時(shí)間:2016年05月04日 15:01:22   作者:飛翔的貓咪  
這篇文章主要介紹了Java實(shí)現(xiàn)冒泡排序算法及對其的簡單優(yōu)化示例,冒泡排序的最差時(shí)間復(fù)雜度為O(n^2),最優(yōu)時(shí)間復(fù)雜度為O(n),存在優(yōu)化的余地,需要的朋友可以參考下

原理

冒泡排序大概是所有程序員都會用的算法,也是最熟悉的算法之一。
它的思路并不復(fù)雜:
設(shè)現(xiàn)在要給數(shù)組arr[]排序,它有n個元素。
1.如果n=1:顯然不用排了。(實(shí)際上這個討論似乎沒什么必要)
2.如果n>1:
(1)我們從第一個元素開始,把每兩個相鄰元素進(jìn)行比較,如果前面的元素比后面的大,那么在最后的結(jié)果里面前者肯定排在后面。所以,我們把這兩個元素交換。然后進(jìn)行下兩個相鄰的元素的比較。如此直到最后一對元素比較完畢,則第一輪排序完成。可以肯定,最后一個元素一定是數(shù)組中最大的(因?yàn)槊看味及严鄬Υ蟮姆诺胶竺媪耍?br /> (2)重復(fù)上述過程,這次我們無需考慮最后一個,因?yàn)樗呀?jīng)排好了。
(3)如此直到只剩一個元素,這個元素一定是最小的,那么我們的排序可以結(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í)間。先分析算法的比較次數(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。(由于不知道這里如何打出平方,這里,我用n^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ù)完全有序的時(shí)候展現(xiàn)出最優(yōu)時(shí)間復(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ù)的時(shí)候增加的布爾變量反而會造成額外的開銷。所以個人認(rèn)為上面改進(jìn)后的算法只是純理論的,通常,冒泡排序就寫前面一種就行了。

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

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

相關(guān)文章

  • Mac下用Java調(diào)用c/c++的思路詳解

    Mac下用Java調(diào)用c/c++的思路詳解

    這篇文章主要介紹了Mac下用Java調(diào)用c/c++的方法,本文給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2021-08-08
  • SpringBoot+docker環(huán)境變量配置詳解

    SpringBoot+docker環(huán)境變量配置詳解

    這篇文章主要介紹了SpringBoot+docker環(huán)境變量配置詳解,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-10-10
  • Java日常練習(xí)題,每天進(jìn)步一點(diǎn)點(diǎn)(55)

    Java日常練習(xí)題,每天進(jìn)步一點(diǎn)點(diǎn)(55)

    下面小編就為大家?guī)硪黄狫ava基礎(chǔ)的幾道練習(xí)題(分享)。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧,希望可以幫到你
    2021-08-08
  • Java版畫板的實(shí)現(xiàn)方法

    Java版畫板的實(shí)現(xiàn)方法

    這篇文章主要為大家詳細(xì)介紹了Java版畫板的實(shí)現(xiàn)方法,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2017-07-07
  • java數(shù)據(jù)結(jié)構(gòu)之java實(shí)現(xiàn)棧

    java數(shù)據(jù)結(jié)構(gòu)之java實(shí)現(xiàn)棧

    這篇文章主要介紹了java數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)棧,需要的朋友可以參考下
    2014-03-03
  • spring boot項(xiàng)目使用@JsonFormat失效問題的解決

    spring boot項(xiàng)目使用@JsonFormat失效問題的解決

    這篇文章主要介紹了spring boot項(xiàng)目使用@JsonFormat失效問題的解決,具有很好的參考價(jià)值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-11-11
  • JAVA實(shí)現(xiàn)深拷貝的幾種方式代碼

    JAVA實(shí)現(xiàn)深拷貝的幾種方式代碼

    這篇文章主要給大家介紹了關(guān)于JAVA實(shí)現(xiàn)深拷貝的幾種方式,在Java中深拷貝和淺拷貝是用來復(fù)制對象的兩種不同方式,深拷貝會對所有數(shù)據(jù)類型進(jìn)行拷貝,包括對象所包含的內(nèi)部對象,需要的朋友可以參考下
    2023-09-09
  • SpringBoot使用protobuf格式的接口方式

    SpringBoot使用protobuf格式的接口方式

    這篇文章主要介紹了SpringBoot使用protobuf格式的接口方式,具有很好的參考價(jià)值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-07-07
  • 關(guān)于Java中方法引用的示例

    關(guān)于Java中方法引用的示例

    方法引用可以認(rèn)為是Lambda表達(dá)式的一種特殊形式,Lambda表達(dá)式可以讓開發(fā)者自定義抽象方法的實(shí)現(xiàn)代碼,方法引用則可以讓開發(fā)者直接引用已存在的實(shí)現(xiàn)方法,作為Lambda表達(dá)式的Lambda體(參數(shù)列表得一致),需要的朋友可以參考下
    2023-05-05
  • Linux安裝JDK兩種方式詳細(xì)教程(附圖)

    Linux安裝JDK兩種方式詳細(xì)教程(附圖)

    這篇文章主要給大家介紹了關(guān)于Linux安裝JDK兩種方式詳細(xì)教程的相關(guān)資料,Linux的使用相信大家都要用到j(luò)ava吧,在使用java前我們得先安裝jdk以及配置環(huán)境變量等工作,需要的朋友可以參考下
    2023-11-11

最新評論