基本思想

比較每兩個(gè)相鄰記錄的關(guān)鍵字,如果反序則交換

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

最好的情況是 O(n)
最壞的情況是 O(n^2)
平均時(shí)間復(fù)雜度是 O(n^2)

冒泡排序算法的過程如下：（從后往前進(jìn)行,得到遞減數(shù)組）

1. 比較相鄰的兩個(gè)元素。如果后一個(gè)比前一個(gè)大，就交換他們兩個(gè)。
2. 對每一對相鄰元素作同樣的工作，從第一對到最后一對。最后的元素應(yīng)該會是最大的數(shù)。
3. 針對所有的元素重復(fù)以上的步驟，除了已排好順序的。
4. 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。

javascript 實(shí)現(xiàn)

     function bubbleSort(arr) {
        var temp, n = arr.length;
        for (var i = n; i > 0; --i) {
            for (var j = 0; j < i - 1; j++) {
                if (arr[j] < arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        return arr;
    }

    var arr = [3, 2, 4, 9, 1, 5, 7, 6, 8];
    var arrSorted = bubbleSort(arr);
    console.log(arrSorted);//9, 8, 7, 6, 5, 4, 3, 2, 1