Java排序算法總結(jié)（三）：冒泡排序
冒泡排序是計(jì)算機(jī)的一種排序方法，它的時(shí)間復(fù)雜度為O（n^2），雖然不及堆排序、快速排序的O（nlogn，底數(shù)為2），但是有兩個優(yōu)點(diǎn)：
1.“編程復(fù)雜度”很低，很容易寫出代碼；
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)的額外的空間，比較和交換的時(shí)間復(fù)雜度都是O(n^2)，自適應(yīng)，對于已基本排序的算法，時(shí)間復(fù)雜度為O(n)。冒泡算法的許多性質(zhì)和插入算法相似，但對于系統(tǒng)開銷高一點(diǎn)點(diǎn)。
排序過程
設(shè)想被排序的數(shù)組R［1..N］垂直豎立，將每個數(shù)據(jù)元素看作有重量的氣泡，根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"，如此反復(fù)進(jìn)行，直至***任何兩個氣泡都是輕者在上，重者在下為止。
代碼實(shí)現(xiàn)：
- // 冒泡排序
- public class BubbleSort {
- public static void sort(Comparable[] data) {
- // 數(shù)組長度
- int len = data.length;
- for (int i = 0; i < len - 1; i++) {
- // 臨時(shí)變量
- Comparable temp = null;
- // 交換標(biāo)志,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ā)生了交換,故將交換標(biāo)志置為真
- 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等基本類型的包裝類已實(shí)現(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ù)進(jìn)行排序，共需要進(jìn)行n-1次的比較。如果本來就是有順序的數(shù)據(jù)，也需要進(jìn)行n-1次比較。冒泡排序法的算法很簡單，效率也較差。
【編輯推薦】
