排序算法——冒泡排序

思路

① 遍历数组arr，对所有相邻的数字进行比较，若后边的数字大于前边的，则交换位置
② 经过第一步后，最大的数字已经冒泡在数组末尾了，就不用遍历了。对arr 索引区间在0~arr.length-1的部分重复步骤①
③ 不断重复步骤②直到区间范围为0~1，此时数组中所有数字都已经排序完毕
另外，当某一次遍历没有任何元素交换顺序时，可以认为排序已经完成

JavaScript实现

/**
 * 冒泡排序
 * @param arr
 * @returns
 */
function bubbleSort(arr){
    if(!(arr instanceof  Array)) return [];
    if(arr.length<=1) return arr;
    //over用来判断排序是否已经结束，若某一次遍历完后没有发生交换，说明已经结束
    var i, j,over;
    for(i=0;i<arr.length;i++){
        var over=true;
        //最后一个元素就不需要再和后边的元素比较了，后边没有了，所有要-1
        for(j=0;j<arr.length-i-1;j++){
            if(arr[j+1]<arr[j]){
                arr.splice(j,0,arr.splice(j+1,1)[0]);
                over=false;
            }
        }
        if(over){
            break;
        }
    }
    return arr;
}