前面介紹了幾個常用的數(shù)據(jù)結構，還剩下兩個數(shù)據(jù)結構：樹和圖。這兩個結構理解概念較為容易，比如樹的基本概念，二分搜索樹的先序、中序、后序和層序遍歷順序，二分搜索樹的插入、查找和刪除操作等。但是要將這些東西使用代碼實現(xiàn)，就比較困難了，我斷斷續(xù)續(xù)看了幾天也沒有看明白（主要糾結在二分搜索樹的刪除操作中的遞歸上）。因此這兩個數(shù)據(jù)結構我還需要再研究研究，以后再寫了。
這篇文章介紹冒泡排序算法。以下面的數(shù)組為例：

const arr:number[] = [5,4,6,2,1,8,0];

當使用冒泡排序對該數(shù)組進行排序（升序、降序）時，其核心思路如下：

1. 從數(shù)組的第一項開始，比較每一項和其右側相鄰項
2. 如果右側相鄰項大于（或小于，取決于升序排序還是降序排序）當前項，就將右側相鄰項和其進行交換
3. 第一輪比較會得到數(shù)組中的最大值（升序排序）或者數(shù)組中的最小值（降序排序），第二輪比較會得到數(shù)組中的第二最大值或第二最小值，以此類推
4. 假設數(shù)組的長度為 n，第一輪比較的次數(shù)為 n-1，第二輪比較的次數(shù)為 n-2，以此類推，直到比較次數(shù)為 1 為止。

下面是冒泡排序的代碼實現(xiàn)：

class BubbleSort{
    private dataStore:number[] = null;
    // 裝載待比較的數(shù)組
    load(arr:number[]):void{
        this.dataStore = arr;
    }
    // 交換數(shù)組元素
    swap(arr:number[],index1,index2){
        let tmp:number = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }
    // flag 參數(shù)用來設置升序或降序排序，默認為升序
    sort(flag:boolean=false):number[]{
        // 獲取帶比較數(shù)組的長度
        let len:number = this.dataStore.length;
        for(let i = len - 1;i > 0;i--){
            for(let j = 0; j < i;j++){
                // 升序排序
                if(!flag && this.dataStore[j] > this.dataStore[j + 1]){
                    this.swap(this.dataStore,j,j+1);
                }
                // 降序排序
                if(flag && this.dataStore[j] < this.dataStore[j + 1]){
                    this.swap(this.dataStore,j,j+1);
                }
            }
        }

        return this.dataStore;
    }
    toString():number[]{
        return this.dataStore;
    }
}

測試代碼：

const arr:number[] = [5,4,6,2,1,8,0];
const b = new BubbleSort();
b.load(arr);
b.sort();
console.log(b.toString())
b.sort(true);
console.log(b.toString())

運行結果：

[ 0, 1, 2, 4, 5, 6, 8 ]
[ 8, 6, 5, 4, 2, 1, 0 ]

在上面的 sort() 方法實現(xiàn)中，使用了兩個 for 循環(huán)，其中外層循環(huán)用來提供本輪應該比較的次數(shù)，內層循環(huán)用來從第一項開始，對數(shù)組進行相應次數(shù)的比較操作。

延伸

從冒泡排序的實現(xiàn)上，可以提取出兩個方法：獲取數(shù)組中最大值的 max() 方法和獲取數(shù)組中最小值的 min() 方法。下面是這兩個方法的實現(xiàn)：

...
// 獲取最大值
max():number{
    let 
        len:number = arr.length,
        tmpArr:number[] = [...this.dataStore];
    
    for(let i = len - 1;i > 0;i--){
        if(tmpArr[i] > tmpArr[i + 1]){
            this.swap(tmpArr,i,i+1)
        }
    }
    return tmpArr[len-1];
}
// 獲取最大值
min():number{
    let 
        len:number = arr.length,
        tmpArr:number[] = [...this.dataStore];

    for(let i = len - 1;i > 0;i--){
        if(tmpArr[i] < tmpArr[i + 1]){
            this.swap(tmpArr,i,i+1)
        }
    }
    return tmpArr[len-1];
}
...

測試代碼：

const arr:number[] = [5,4,6,2,1,8,0];
const b = new BubbleSort();
b.load(arr);
console.log(b.max())
console.log(b.min())

運行結果：

8
0

完。