冒泡排序,两种实现以及优化

前端 0 402 0
发表于: 2021-02-18 16:00:34

简介: 暂无~

冒泡排序

基本原理

比较相邻的元素。如果第一个比第二个大,就交换他们两个。

比如:第一次排序,内层循环两两对比互换位置,将一个最值放到最后,第二次排序,内层循环又继续通过两两对比互换位置,将剩下的值中的最值放到倒数第二个位置,因为互换位置是通过两两对比的方式,所以交换次数的时间复杂度是O(n²)

稳定性

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,是不会再交换的如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也还是不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

总结:冒泡排序是相邻元素两两对比,交换也发生在这两个元素之间。只有两个元素大小不一样才会交换,相邻的相同元素大小一样不会交换位置,相同的元素不相邻,后面通过两两对比交换变成了相邻了,也还是大小一样,不会交换位置!!!假设只有两个元素,且这两个元素相等(只有两个那也代表他们必相邻),他们两两对比,左边的不大/小于右边的,因此不会交换位置!所以冒泡排序是稳定的。

举例子,看代码最直接,假设两个相同元素:[1,1],arr[j] < arr[j + 1]压根就不会成立,因此这两个相同元素不会互换位置,故稳定

function bubbleSort(arr) {
    for (var i = 0; i < arr.length; i++) {
        for (var j = 0; j < arr.length; j++) {
            if (arr[j] < arr[j + 1]) {
                var temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
    return arr
}

复杂度

时间复杂度:O(n²)

实现

实现1

var arr = [1, 2, 3, 4, 5, 6];
// var arr = [6, 5, 4, 3, 2, 1];
// var arr = [32, 14, 6, 9, 20, 58];

// 外层for循环控制互换多少轮
// 里层for循环控制每一轮互换多少次
// 没有任何优化,需要固定循环arr.length*arr.length次数
function bubbleSort(arr) {
    // 外层for循环互换6轮
    for (var i = 0; i < arr.length; i++) {
        // 内层for循环每轮互换6次
        for (var j = 0; j < arr.length; j++) {
            console.log(1)
            // 如果第一个比第二个大,则交换位置,最终就是:小->大
            // if (arr[j] >arr[j + 1]) {
            // 如果第一个比第二个小,则互换位置,最终就是:大->小
            if (arr[j] < arr[j + 1]) {
                var temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
    return arr
}

优化1

// 优化越界问题
// 因为里层for循环会下标+1,当里层j=arr.length+1时,值为undefined
// 优化后,需要固定循环arr.length*(arr.length-1)次数
function bubbleSort1(arr) {
    for (var i = 0; i < arr.length; i++) {
        for (var j = 0; j < arr.length - 1; j++) {
            console.log(1)
            if (arr[j] < arr[j + 1]) {
                var temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
    return arr
}

优化2

/**
 * 每次外层循环后,里层循环不应该固定循环arr.length-1次,
 * 因为每次外层循环后,里层循环都会得出一个最终的最值,
 * 后面的里层循环,这个最值不用重复的继续循环
 * 所以应该每次都相对应的减少里层的循环次数
 * 第一轮内循环互换了5次,第二轮4次,第三轮3次,第四轮2次,第五轮1次,第六轮0次
 * 优化后,需要固定循环(arr.length*(arr.length-1))/2次数
 */
function bubbleSort2(arr) {
    for (var i = 0; i < arr.length; i++) {
        // console.log(i)
        // 互换过的下次就不互换,即每次内层循环次数随着外层越来越小
        // 第一轮内层循环互换arr.length - 1 - 0次,即5次
        // 第二轮内层循环互换arr.length - 1 - 1次,即4次
        // 第三轮内层循环互换arr.length - 1 - 2次,即3次
        // 第四轮内层循环互换arr.length - 1 - 3次,即2次
        // 第五轮内层循环互换arr.length - 1 - 5次,即1次
        // 第六轮内层循环互换arr.length - 1 - 6次,即0次
        for (var j = 0; j < arr.length - 1 - i; j++) {
            console.log(1)
            // console.log(i, j)
            if (arr[j] < arr[j + 1]) {
                var temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
    return arr
}

/**
 * 0 0
 * 0 1
 * 0 2
 * 0 3
 * 0 4
 * 1 0
 * 1 1
 * 1 2
 * 1 3
 * 2 0
 * 2 1
 * 2 2
 * 3 0
 * 3 1
 * 4 0
 */

实现2

/**
 * 前面是从第一个到最后一个往后冒泡
 * 也可以从最后一个到第一个往前冒泡
 * 需要固定循环(arr.length)*(arr.length)次数
 */
function bubbleSort3(arr) {
    for (var i = arr.length - 1; i >= 0; i--) {
        for (var j = 0; j < arr.length; j++) {
            console.log(1)
            // console.log(i,j)
            if (arr[j] < arr[j + 1]) {
                var temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
    return arr
}

优化1

// 优化里层越界问题
// 需要固定循环(arr.length)*(arr.length-1)次数
function bubbleSort4(arr) {
    for (var i = arr.length - 1; i >= 0; i--) {
        for (var j = 0; j < arr.length - 1; j++) {
            console.log(1)
            // console.log(i,j)
            if (arr[j] < arr[j + 1]) {
                var temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
    return arr
}

优化2

// 优化里层循环
// 需要固定循环((arr.length)*(arr.length))/2次数
function bubbleSort5(arr) {
    for (var i = arr.length - 1; i >= 0; i--) {
        // 互换过的下次就不互换,即每次内层循环次数随着外层越来越小
        // 第一轮内层循环互换arr.length - 1 - 0次,即5次
        // 第二轮内层循环互换arr.length - 1 - 1次,即4次
        // 第三轮内层循环互换arr.length - 1 - 2次,即3次
        // 第四轮内层循环互换arr.length - 1 - 3次,即2次
        // 第五轮内层循环互换arr.length - 1 - 5次,即1次
        // 第六轮内层循环互换arr.length - 1 - 6次,即0次
        for (var j = 0; j < i; j++) {
            // console.log(1)
            console.log(i, j)
            if (arr[j] < arr[j + 1]) {
                var temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
    return arr
}
/**
 * 5 0
 * 5 1
 * 5 2
 * 5 3
 * 5 4
 * 4 0
 * 4 1
 * 4 2
 * 4 3
 * 3 0
 * 3 1
 * 3 2
 * 2 0
 * 2 1
 * 1 0
 */

实现3

待定

选择排序

看另一篇文章

插入排序

看另一篇文章

数据结构和算法

最后更新于:2021-02-19 03:33:19

欢迎评论留言~
0/400
支持markdown
Comments | 0 条留言
按时间
按热度
目前还没有人留言~