前面介绍了几个常用的数据结构，还剩下两个数据结构：树和图。这两个结构理解概念较为容易，比如树的基本概念，二分搜索树的先序、中序、后序和层序遍历顺序，二分搜索树的插入、查找和删除操作等。但是要将这些东西使用代码实现，就比较困难了，我断断续续看了几天也没有看明白（主要纠结在二分搜索树的删除操作中的递归上）。因此这两个数据结构我还需要再研究研究，以后再写了。
这篇文章介绍冒泡排序算法。以下面的数组为例：
const arr:number[] = [5,4,6,2,1,8,0];
当使用冒泡排序对该数组进行排序（升序、降序）时，其核心思路如下：
- 从数组的第一项开始，比较每一项和其右侧相邻项
- 如果右侧相邻项大于（或小于，取决于升序排序还是降序排序）当前项，就将右侧相邻项和其进行交换
- 第一轮比较会得到数组中的最大值（升序排序）或者数组中的最小值（降序排序），第二轮比较会得到数组中的第二最大值或第二最小值，以此类推
- 假设数组的长度为
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
完。
