一、算法原理

比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數(shù)。

針對所有的元素重復以上的步驟，除了最后一個。

持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。 

二、實現(xiàn)思路

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

設數(shù)組長度為N：

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

三、代碼實現(xiàn)

package sort;
import java.util.Arrays;
/**
 * 冒泡排序
 * 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
 * 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數(shù)。
 * 針對所有的元素重復以上的步驟，除了最后一個。
 * 持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。
 */

public class BubbleSort {
  public static void bubbleSort(int[] arr) {
    boolean flag=true;
    while (flag) {
      flag=false;
      int temp = 0;
      for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
          if (arr[j] > arr[j + 1]) {   //交換兩數(shù)位置
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
            flag=true;
          }
        }
        if (!flag){
          break;
        }
        }
      }
    }
  public static void main(String[] args){
    int a[]=new int[]{345,22,43,12,65,335,124,636,3};
    BubbleSort.bubbleSort(a);
    System.out.print(Arrays.toString(a));
  }
}

 四、性能分析

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

五、算法優(yōu)化

冒泡排序法存在的不足及改進方法：

第一、在排序過程中，執(zhí)行完最后的排序后，雖然數(shù)據(jù)已全部排序完備，但程序無法判斷是否完成排序，為了解決這一不足，可設置一個標志位flag，將其初始值設置為true，表示被排序的表是一個無序的表，每一次排序開始前設置flag值為true，在進行數(shù)據(jù)交換時，修改flag為false。在新一輪排序開始時，檢查此標志，若此標志為false，表示上一次沒有做過交換數(shù)據(jù)，則結束排序；否則進行排序；

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

package sort;

import java.util.Arrays;

public class BubbleSort {
  public static void bubbleSort(int[] arr) {
    boolean flag=true;
    while (flag) {
      flag=false;
      int temp = 0;
      for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
          if (arr[j] > arr[j + 1]) {   //交換兩數(shù)位置
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
            flag=true;
          }
        }
        if (!flag){
          break;
        }
        }
      }
    }
  public static void main(String[] args){
    int a[]=new int[]{345,22,43,12,65,335,124,636,3};
    BubbleSort.bubbleSort(a);
    System.out.print(Arrays.toString(a));
  }
}

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

最新評論