冒泡排序

原理：遍历整个数组，依次比较相邻的两个值，如果前一个值比后面的值大，即交换他们的位置，依照这个规则进行多次并且递减的迭代，直到顺序正确。

代码实现：

function bubbleSort(arr) {

    // 检测传入的 arr 是否为数组，如果不是数组，直接返回该本身
    if (Object.prototype.toString.call(arr) !== '[object Array]') {
        return arr;
    }

    var len = arr.length;
    
    // 如果长度为1或者为0，直接返回该数组
    if (len <= 1) {
        return arr;
    }

    for (var i = 0; i < len - 1; i++) {
        for (var j = 0; j < len - 1 - i; j++) {

            if (arr[j] > arr[j + 1]) {
                var temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
            }

        }
    }

    return arr;
}

算法概念

• 时间复杂度指的是一个算法执行所耗费的时间
• 空间复杂度指运行完一个程序所需内存的大小
• 稳定指如果a=b，a在b的前面，排序后a仍然在b的前面
• 不稳定指如果a=b，a在b的前面，排序后可能会交换位置

时间复杂度测试

/**
 * 生成随机数
 * @param lower 开始的数值
 * @param upper 结尾的数值
 * @returns 生成[lower, upper] 之间的随机数
 */
function getRandom(lower, upper) {
    return Math.floor(Math.random() * (upper - lower)) + lower;
}

/**
 * 获取随机数组
 * @param len 生成数组长度
 * @returns 随机生成长度为len的数组
 */
function getArr(len) {
    var arr = [];
    for (var i = 0; i < len; i++) {
        arr.push(getRandom(1, len));
    }

    return arr;
}

/**
 *  测试最好情况生成的有序数组
 * @param len 生成数组长度
 * @returns 生成有序长度为len的数组
 */
function getBestArr(len) {
    var bestArr = []
    for (var i = 1; i <= len; i++) {
        bestArr.push(i);
    }

    return bestArr;
}

/**
 * 测试最坏情况所有的数字随机（极少情况下重复）
 * @param len 生成数组长度
 * @returns 随机无序不重复长度为len的数组
 */
function getBadArr(len) {
    var badArr = []
    for (var i = len; i > 0; i--) {
        badArr.push(i + getRandom(1, 100));
    }

    return badArr;
}

/**
 * 测试算法sortName运行opCount个排序操作所需要的时间
 * @param sortName 算法名字
 * @param opCount 操作的个数
 * @returns 耗时间
 */
function testSortCountTime(sortName, opCount) {
    // 记录排序前当前时间
    var nowTime = new Date().getTime();
    sortName(opCount);
    // 记录排序完时间
    var doneTime = new Date().getTime();

    return "耗时：" + ((doneTime - nowTime) / 1000.0) + "s";
}

// 需要测试的个数
const TEXT_NUM = 10000;
console.log("测试的个数为：" + TEXT_NUM);

// 平均时间复杂度测试（随机）
console.log("平均时间复杂度" + testSortCountTime(bubbleSort, getArr(TEXT_NUM)));

// 测试最好的时间复杂度测试情况
console.log("最好的时间复杂度" + testSortCountTime(bubbleSort, getBestArr(TEXT_NUM)));

// 测试最坏的时间复杂度测试情况
console.log("最坏的时间复杂度" + testSortCountTime(bubbleSort, getBadArr(TEXT_NUM)));

/**
 *   JSFunction git:(master)  node bubbleSort.js
 测试的个数为：10000
 平均时间复杂度耗时：0.589s
 最好的时间复杂度耗时：0.569s
 最坏的时间复杂度耗时：0.591s
   JSFunction git:(master)  node bubbleSort.js
 测试的个数为：20000
 平均时间复杂度耗时：2.291s
 最好的时间复杂度耗时：2.213s
 最坏的时间复杂度耗时：2.323s
   JSFunction git:(master)  node bubbleSort.js
 测试的个数为：30000
 平均时间复杂度耗时：5.202s
 最好的时间复杂度耗时：4.955s
 最坏的时间复杂度耗时：5.297s
   JSFunction git:(master)  node bubbleSort.js
 测试的个数为：40000
 平均时间复杂度耗时：9.216s
 最好的时间复杂度耗时：8.822s
 最坏的时间复杂度耗时：9.74s
   JSFunction git:(master)  node bubbleSort.js
 测试的个数为：50000
 平均时间复杂度耗时：14.619s
 最好的时间复杂度耗时：13.655s
 最坏的时间复杂度耗时：14.708s

 Tips: 耗时时可能会有偏差，因电脑的配置有一点关系，不过影响不会很大。
 */

总结

冒泡排序分析

• 时间复杂度： 平均时间复杂度O(n*n) 、最好情况O(n)、最差情况O(n*n)
• 空间复杂度： O(1)
• 稳定性：稳定

冒泡排序优缺点

• 排序算法的基础，简单实用易于理解
• 缺点是比较次数多，效率较低