冒泡排序

发表于 | 分类于

冒泡排序

基本思想

理论：
1.比较轮数n-1。
2.比较次数n-1。
3.符合某个条件交换位置。

核心： 双重for循环。

步骤：

1 .双重for循环。

2 .指定轮数和次数。

3 .判断是否符合标准。如果符合标准交换位置。

版本比较

将数组元素从小到大排序：

初始版

按照前面的步骤很容易写出以下代码：

    var arr = [7,6,5,4,3,2,1];

    //1.双重for循环。(外循环控制轮数)  
    for(var i=0;i<arr.length-1;i++){
        //2.指定轮数和次数（内循环控制次数）
        for(var j=0;j<arr.length-1;j++){
            //3.判断是否符合标准。如果符合标准交换位置。                   
            if(arr[j] > arr[j+1]){
                var temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;

            }
        }
    }

改进思路：每比较一轮，就少比较一次。（每一轮都会比较出一个最大值，后一轮就没有必要再比较那个值了，所以每比较一轮，就少比较一次。）

改进版

var arr = [7,6,5,4,3,2,1];
    var m = 0;
    var n = 0;
for(var i=0;i<arr.length-1;i++){
    for(var j=0;j<arr.length-1-i;j++){               
        if(arr[j] > arr[j+1]){
            var temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
        }
        m++;//记录比较次数
    }
    n++;//记录比较轮数
}
console.log(arr);
console.log(m);
console.log(n);

再升级思路：如果比较完，提前结束比较。（判断，如果本次比较没有移动任何元素，那么说明已经比较完成。）

升级版

var arr = [1, 2, 3, 4, 5, 6, 7];
var m = 0;
var n = 0;
for(var i=0;i<arr.length-1;i++){
    //开闭原则。（写在第一个for循环里，是为了每轮比较先初始化bool变量变为true。）
    var bool = true;
    
    for(var j=0;j<arr.length-1-i;j++){
        if(arr[j] > arr[j+1]){
            var temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
            //如果有交换，则bool置false。
            bool = false;
        }
        m++;
    }
    n++;
    
    //如果本轮比较没有任何元素相互交换位置，那么说明已经比较完成，可以跳出循环。
    if(bool){
        break;
    }
}
console.log(arr);
console.log(m);
console.log(n);
-------------完-------------