js冒泡排序算法详解

冒泡排序：相邻的两个元素比较，如果前一个数大于后一个数，交换位置。

冒泡排序原理：依次比较相邻的两个值，如果后面的比前面的小，则将小的元素排到前面。依照这个规则进行多次并且递减的迭代，直到顺序正确。

具体的来说就是

1、每一次排序将无序数列中的最大值找到；

2、一个含有n的序列最多经过n-1次排序即可有序；

3、经过排序后，数列会分为两部分，一部分有序，一部分无序；

4、一旦出现前一个数大于后一个数，就交换位置。

/*
 冒泡排序：
 1.外层循环-1 含有n个数的序列 最多经过n-1次即可有效
 2.内层循环-1 arr[j + 1] 会超过数组的下标范围  出现undefined
 3.内层循环 -i  数列排序 后会分为两部分 一部分有序 一部分无序
    - i 不用反复 排序有序部分的数值
 */

function bubble_sort(arr){
 for (var i = 0; i < arr.length - 1; i++) {
    //假设 数组有序 flag用来标记某一趟排序是否发生交换
    var flag = 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;
            //一旦进入此分支  前一个数大于后一个数的情况产生 数组此时 无序
            flag = false;
        }
    }
    if(flag){
        break;
    }
    
 }        
}

示例

<div id="test">旧: 49,38,65,97,76,13,27,49</div>
<div id="test2"></div>

var arr = [49, 38, 65, 97, 76, 13, 27, 49];
bubble_sort(arr);
document.getElementById('test2').innerHTML = '新: ' + arr.join(',')

运行结果：

旧: 49,38,65,97,76,13,27,49

新: 13,27,38,49,49,65,76,97

尝试一下

解释：

当i=0的时候，里面的循环完整执行，从j=0执行到j=6,这也就是第一遍排序，结果是将最大的数排到了最后，这一遍循环结束后的结果应该是[8,15,88,55,76,21,39,94]

当i=1的时候，里面的循环再次完整执行，由于最大的数已经在最后了，没有必要去比较数组的最后两项，这也是j<arr.length-1-i的巧妙之处，结果是[8,15,55,76,21,39,88,94]

说到这里，规律就清楚了，每次将剩下数组里面最大的一个数排到最后面，当第一个循环执行到最后的时候，也就是i=6,此时，j=0,只需要比较数组的第一和第二项，比较完毕，返回。