冒泡排序

基本原理

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

比如：第一次排序，内层循环两两对比互换位置，将一个最值放到最后，第二次排序，内层循环又继续通过两两对比互换位置，将剩下的值中的最值放到倒数第二个位置，因为互换位置是通过两两对比的方式，所以交换次数的时间复杂度是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

待定

选择排序

看另一篇文章

插入排序

看另一篇文章