JAVA十大排序算法之冒泡排序詳解

更新時(shí)間：2021年08月23日 09:36:14 作者：阿粵Ayue

這篇文章主要介紹了java中的冒泡排序，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下

冒泡排序

1.從數(shù)組頭開始，比較相鄰的元素。如果第一個(gè)比第二個(gè)大(小)，就交換它們兩個(gè)

2.對每一對相鄰元素作同樣的工作，從開始第一對到尾部的最后一對，這樣在最后的元素應(yīng)該會是最大(小)的數(shù)

3.重復(fù)步驟1~2，重復(fù)次數(shù)等于數(shù)組的長度，直到排序完成

代碼實(shí)現(xiàn)

對下面數(shù)組實(shí)現(xiàn)排序：{24, 7, 43, 78, 62, 98, 82, 18, 54, 37, 73, 9}

代碼實(shí)現(xiàn)

public class BubbleSort {
    public static final int[] ARRAY = {24, 7, 43, 78, 62, 98, 82, 18, 54, 37, 73, 9};
    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY));
    }
    public static int[] sort(int[] array) {
        if (array.length == 0) {
            return array;
        }
        for (int i = 0; i < array.length; i++) {
            //array.length - 1 -i 已經(jīng)冒泡到合適位置無需在進(jìn)行排序，減少比較次數(shù)
            for (int j = 0; j < array.length - 1 -i; j++) {
                //前面的數(shù)大于后面的數(shù)交換
                if (array[j + 1] < array[j]) {
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
        }
        return array;
    }
    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }
}

時(shí)間復(fù)雜度

對于上面12個(gè)數(shù)據(jù)項(xiàng)，從第一個(gè)元素開始，第一趟比較了11次，第二趟比較了10次，依次類推，一直到最后一趟，就是：

11 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 66次

若有n個(gè)元素，則第一趟比較為(n-1)次，第二趟比較為(n-2)次，依次類推：

(n-1) + (n-2) + (n-3) + ...+ 2 + 1 = n * (n-1)/2

在大O表示法中，去掉常數(shù)系數(shù)和低階項(xiàng)，該排序方式的時(shí)間復(fù)雜度為：O(n2)

算法穩(wěn)定性

假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的?！俣劝倏?/p>

在代碼中可以看到，array[j + 1] = array[j]的時(shí)候，我們可以不移動array[i]和array[j]，所以冒泡排序是穩(wěn)定的。