本文實(shí)例講述了java利用冒泡排序?qū)?shù)組進(jìn)行排序的方法。分享給大家供大家參考。具體如下：

一、冒泡排序：

利用冒泡排序?qū)?shù)組進(jìn)行排序

二、基本概念：

依次比較相鄰的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面。即在第一趟：首先比較第1個(gè)和第2個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。然后比較第2個(gè)數(shù)和第3個(gè)數(shù)，將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。至此第一趟結(jié)束，將最大的數(shù)放到了最后。在第二趟：仍從第一對(duì)數(shù)開(kāi)始比較（因?yàn)榭赡苡捎诘?個(gè)數(shù)和第3個(gè)數(shù)的交換，使得第1個(gè)數(shù)不再小于第2個(gè)數(shù)），將小數(shù)放前，大數(shù)放后，一直比較到倒數(shù)第二個(gè)數(shù)（倒數(shù)第一的位置上已經(jīng)是最大的），第二趟結(jié)束，在倒數(shù)第二的位置上得到一個(gè)新的最大數(shù)（其實(shí)在整個(gè)數(shù)列中是第二大的數(shù)）。如此下去，重復(fù)以上過(guò)程，直至最終完成排序。

三、實(shí)現(xiàn)思路：

用二重循環(huán)實(shí)現(xiàn)，外循環(huán)變量設(shè)為i，內(nèi)循環(huán)變量設(shè)為j。假如有n個(gè)數(shù)需要進(jìn)行排序，則外循環(huán)重復(fù)n-1次，內(nèi)循環(huán)依次重復(fù)n-1，n-2，...，1次。每次進(jìn)行比較的兩個(gè)元素都是與內(nèi)循環(huán)j有關(guān)的，它們可以分別用a[j]和a[j+1]標(biāo)識(shí)，i的值依次為1,2,...,n-1，對(duì)于每一個(gè)i，j的值依次為0,1,2,...n-i 。

設(shè)數(shù)組長(zhǎng)度為N：
1．比較相鄰的前后二個(gè)數(shù)據(jù)，如果前面數(shù)據(jù)大于后面的數(shù)據(jù)，就將二個(gè)數(shù)據(jù)交換。
2．這樣對(duì)數(shù)組的第0個(gè)數(shù)據(jù)到N-1個(gè)數(shù)據(jù)進(jìn)行一次遍歷后，最大的一個(gè)數(shù)據(jù)就“沉”到數(shù)組第N-1個(gè)位置。
3．N=N-1，如果N不為0就重復(fù)前面二步，否則排序完成。

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

package ArrayDemo; 
/** 
 * @author pplsunny 
 * @category .21 
 */ 
public class ArrayDemo {   
  /** 
   * 用增強(qiáng)for循環(huán)輸出排序結(jié)果 
   */ 
  public static void main(String[] args) { 
   int[] a = { 2, 4, 76, 12, 34, 23, 86 }; 
   ArrayDemo.bubbleSort(a); 
   for (int b : a) { 
    System.out.print(b + " "); 
   } 
  } 
  /* 
   * 冒泡排序函數(shù)，定義為靜態(tài)的方便使用，
 * 也是開(kāi)發(fā)中定義工具類(lèi)的一個(gè)方法 
   */ 
  public static void bubbleSort(int a[]) { 
   for (int i = 1; i < a.length; i++) {
   //這是控制趟數(shù) 
    for (int j = 0; j < a.length - i; j++) {
    //j < a.length - i,比較元素的個(gè)數(shù) 
     if (a[j] > a[j + 1]) { 
      int temp = a[j]; 
      a[j] = a[j + 1]; 
      a[j + 1] = temp; 
     } 
    } 
   } 
  } 
} 

五、性能分析：

若記錄序列的初始狀態(tài)為"正序"，則冒泡排序過(guò)程只需進(jìn)行一趟排序，在排序過(guò)程中只需進(jìn)行n-1次比較，且不移動(dòng)記錄；反之，若記錄序列的初始狀態(tài)為"逆序"，則需進(jìn)行n(n-1）/2次比較和記錄移動(dòng)。因此冒泡排序總的時(shí)間復(fù)雜度為O(n*n)。

六、算法優(yōu)化：

冒泡排序法存在的不足及改進(jìn)方法：
第一，在排序過(guò)程中，執(zhí)行完最后的排序后，雖然數(shù)據(jù)已全部排序完備，但程序無(wú)法判斷是否完成排序，為了解決這一不足，可設(shè)置一個(gè)標(biāo)志位flag，將其初始值設(shè)置為非0，表示被排序的表是一個(gè)無(wú)序的表，每一次排序開(kāi)始前設(shè)置flag值為0，在進(jìn)行數(shù)據(jù)交換時(shí)，修改flag為非0。在新一輪排序開(kāi)始時(shí)，檢查此標(biāo)志，若此標(biāo)志為0，表示上一次沒(méi)有做過(guò)交換數(shù)據(jù)，則結(jié)束排序；否則進(jìn)行排序；

/* 
* 冒泡排序函數(shù)改進(jìn)版 
*/ 
public static void BubbleSort(int[] a) { 
  boolean flag = true; 
  while (flag) { 
   flag = false; 
   for (int i = 0; i < a.length - 1; i++) { 
    for (int j = 0; j < a.length - i ; j++) { 
     if (a[j] > a[j + 1]) { 
      int temp = a[j]; 
      a[j] = a[j + 1]; 
      a[j + 1] = temp; 
      flag = true; 
     } 
    } 
    if (!flag) 
     break; // 如果沒(méi)有發(fā)生交換，則退出循環(huán)  
   } 
  } 
}

第二、在冒泡排序中，一趟掃描有可能無(wú)數(shù)據(jù)交換，也有可能有一次或多次數(shù)據(jù)交換，在傳統(tǒng)的冒泡排序算法及近年來(lái)的一些改進(jìn)的算法中，只記錄一趟掃描有無(wú)數(shù)據(jù)交換的信息，對(duì)數(shù)據(jù)交換發(fā)生的位置信息則不予處理。為了充分利用這一信息，可以在一趟全局掃描中，對(duì)每一反序數(shù)據(jù)對(duì)進(jìn)行局部冒泡排序處理，稱(chēng)之為局部冒泡排序。局部冒泡排序與冒泡排序算法具有相同的時(shí)間復(fù)雜度，并且在正序和逆序的情況下，所需的關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)完全相同。由于局部冒泡排序和冒泡排序的數(shù)據(jù)移動(dòng)次數(shù)總是相同的，而局部冒泡排序所需關(guān)鍵字的比較次數(shù)常少于冒泡排序，這意味著局部冒泡排序很可能在平均比較次數(shù)上對(duì)冒泡排序有所改進(jìn)，當(dāng)比較次數(shù)較少的優(yōu)點(diǎn)不足以抵消其程序復(fù)雜度所帶來(lái)的額外開(kāi)銷(xiāo)，而當(dāng)數(shù)據(jù)量較大時(shí)，局部冒泡排序的時(shí)間性能則明顯優(yōu)于冒泡排序。對(duì)于N個(gè)無(wú)序數(shù)據(jù)，我們?cè)谶M(jìn)行一趟冒泡排序時(shí)，如果第k個(gè)數(shù)據(jù)和第k+1個(gè)數(shù)據(jù)逆序，那么對(duì)第k+1個(gè)數(shù)據(jù)進(jìn)行一趟向前的冒泡排序，使其移動(dòng)到合適的位置，也就是說(shuō)讓前面k+1個(gè)數(shù)據(jù)調(diào)節(jié)為正序。因?yàn)檫@種冒泡法只對(duì)前k+1個(gè)數(shù)據(jù)冒泡處理，所以我們稱(chēng)它為——局部冒泡

希望本文所述對(duì)大家的java程序設(shè)計(jì)有所幫助。

最新評(píng)論