排序算法——冒泡排序

前面介绍了几个常用的数据结构，还剩下两个数据结构：树和图。这两个结构理解概念较为容易，比如树的基本概念，二分搜索树的先序、中序、后序和层序遍历顺序，二分搜索树的插入、查找和删除操作等。但是要将这些东西使用代码实现，就比较困难了，我断断续续看了几天也没有看明白（主要纠结在二分搜索树的删除操作中的递归上）。因此这两个数据结构我还需要再研究研究，以后再写了。
这篇文章介绍冒泡排序算法。以下面的数组为例：

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

当使用冒泡排序对该数组进行排序（升序、降序）时，其核心思路如下：

1. 从数组的第一项开始，比较每一项和其右侧相邻项
2. 如果右侧相邻项大于（或小于，取决于升序排序还是降序排序）当前项，就将右侧相邻项和其进行交换
3. 第一轮比较会得到数组中的最大值（升序排序）或者数组中的最小值（降序排序），第二轮比较会得到数组中的第二最大值或第二最小值，以此类推
4. 假设数组的长度为 n，第一轮比较的次数为 n-1，第二轮比较的次数为 n-2，以此类推，直到比较次数为 1 为止。

下面是冒泡排序的代码实现：

class BubbleSort{
    private dataStore:number[] = null;
    // 装载待比较的数组
    load(arr:number[]):void{
        this.dataStore = arr;
    }
    // 交换数组元素
    swap(arr:number[],index1,index2){
        let tmp:number = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }
    // flag 参数用来设置升序或降序排序，默认为升序
    sort(flag:boolean=false):number[]{
        // 获取带比较数组的长度
        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() 方法实现中，使用了两个 for 循环，其中外层循环用来提供本轮应该比较的次数，内层循环用来从第一项开始，对数组进行相应次数的比较操作。

延伸

从冒泡排序的实现上，可以提取出两个方法：获取数组中最大值的 max() 方法和获取数组中最小值的 min() 方法。下面是这两个方法的实现：

...
// 获取最大值
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

完。