Java排序算法總結(jié)之冒泡排序

更新時間：2015年05月19日 10:41:57 作者：一羽清寧

這篇文章主要介紹了Java排序算法總結(jié)之冒泡排序,較為詳細的分析了冒泡排序的原理與java實現(xiàn)技巧,需要的朋友可以參考下

本文實例講述了Java排序算法總結(jié)之冒泡排序。分享給大家供大家參考。具體分析如下：

前言：冒泡排序（BubbleSort）就是依次比較相鄰的兩個數(shù)，將小數(shù)放在前面，大數(shù)放在后面。

下面讓我們一起來看冒泡排序在Java中的算法實現(xiàn)。

冒泡排序是計算機的一種排序方法，它的時間復雜度為O（n^2），雖然不及堆排序、快速排序的O（nlogn，底數(shù)為2），但是有兩個優(yōu)點：

1.“編程復雜度”很低，很容易寫出代碼；
2.具有穩(wěn)定性，這里的穩(wěn)定性是指原序列中相同元素的相對順序仍然保持到排序后的序列，而堆排序、快速排序均不具有穩(wěn)定性。

不過，一路、二路歸并排序、不平衡二叉樹排序的速度均比冒泡排序快，且具有穩(wěn)定性，但速度不及堆排序、
快速排序。冒泡排序是經(jīng)過n-1趟子排序完成的，第i趟子排序從第1個數(shù)至第n-i個數(shù)，若第i個數(shù)比后一個數(shù)大
（則升序，小則降序）則交換兩數(shù)。

冒泡排序算法穩(wěn)定，O(1)的額外的空間，比較和交換的時間復雜度都是O(n^2)，自適應(yīng)，對于已基本排序的算法，時間復雜度為O(n)。冒泡算法的許多性質(zhì)和插入算法相似，但對于系統(tǒng)開銷高一點點。

排序過程

設(shè)想被排序的數(shù)組R［1..N］垂直豎立，將每個數(shù)據(jù)元素看作有重量的氣泡，根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"，如此反復進行，直至最后任何兩個氣泡都是輕者在上，重者在下為止。

代碼實現(xiàn)：

// 冒泡排序   
public class BubbleSort{
  public static void sort(Comparable[] data){
    // 數(shù)組長度 
    int len = data.length; 
    for (int i = 0; i < len - 1; i++){
      // 臨時變量 
      Comparable temp = null; 
      // 交換標志,false表示未交換 
      boolean isExchanged = false; 
      for (int j = len - 1; j > i; j--){
        // 如果data[j]小于data[j - 1],交換 
        if (data[j].compareTo(data[j - 1]) < 0){
          temp = data[j]; 
          data[j] = data[j - 1]; 
          data[j - 1] = temp; 
          // 發(fā)生了交換,故將交換標志置為真 
          isExchanged = true; 
        }// end if 
      }// end for 
      // 本趟排序未發(fā)生交換,提前終止算法,提高效率 
      if (!isExchanged){
        return; 
      }// end if 
    }// end for 
  }// end sort 
  public static void main(String[] args){
    // 在JDK1.5版本以上,基本數(shù)據(jù)類型可以自動裝箱
    // int,double等基本類型的包裝類已實現(xiàn)了Comparable接口
    Comparable[] c = { 4, 9, 23, 1, 45, 27, 5, 2 };
    sort(c);
    for (Comparable data : c){
      System.out.println(data);
    }
  }
}

使用冒泡排序法對n個數(shù)據(jù)進行排序，共需要進行n-1次的比較。如果本來就是有順序的數(shù)據(jù)，也需要進行n-1次比較。冒泡排序法的算法很簡單，效率也較差。

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

您可能感興趣的文章: