面试常考算法之 冒泡排序

126 阅读1分钟

冒泡排序

运用双层for循环,复杂程度是 n*n。
两个两个之间比较,这里不再多赘述,直接贴代码

下面这个是第一层for循环
var arr = [5, 3, 15, 66, 1, 2, 21, 16, 11, 34, 44]

    for (var j = 0; j < arr.length - 1; j ++) {
    // 这里j过滤完第一遍之后,最后一位一定是最大的
        var temp
        if (arr[j] > arr[j + 1]) {
            temp = arr[j] // 先把比较大的这一个保存起来
            arr[j] = arr[j + 1] // 把最小的值移动过来
            arr[j + 1] = temp  // 最大的值赋值在后面
        }
    }

外面第二层for循环
    for (var i = 0; i < arr.length; i ++) {
        for (var j = 0; j = arr.length - i - 1; j ++) {
        //  这里arr.length - i - 1解释一下 因为是不重复比较放最后面的最大值,
        //  所以每次都要减去 i
            var temp
            if (arr[j] > arr[j + 1]) {
                temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
            //这里的判断赋值可以用ES6 的解构赋值来做
            // 简化为 [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
        }
    }
完整的形式
    function bobbleSort (arr) {
        if (Object.prototype.toString.call(arr) !== '[object Array]') { return new Error('参数必须是数组') }
        var len = arr.length
        for (var i = 0; i < len; i ++) {
            for (j = 0; j < len - i - 1; j ++) {
                if (arr[j] > arr[j + 1]) {
                    [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
                }
            }
        }
        return arr
}