排序算法系列之——冒泡排序

上一次说完了快速排序，那么继续往下走，本次我们来理解冒泡排序算法

废话少说，进入正题

如有误，辛苦指正

背景介绍

$\color{#ea4335}{冒泡排序}$ （Bubble Sort），是一种计算机科学领域的较简单的排序算法。

它 $\color{#4285f4}{重复}$ 地走访过要排序的元素列， $\color{#34a853}{依次比较}$ 两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行 $\color{#34a853}{直到没有相邻元素需要交换}$ ，也就是说该元素列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。 ---冒泡排序算法

核心特点

比较相邻的元素。如果第一个比第二个大/小，将这两个元素交换位置。

循环对每一对相邻元素做 1 的操作，依次比较后，此时最后的元素应该是最大/小的元素。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

举个例子

[ 1, 5, 4, 3, 6, 2, 7 ]

1、先将 1 和 5 做比较5更大不需要换位置，所以得到

[ 1, 5, 4, 3, 6, 2, 7 ]

2、将 5 和 4 做比较，4比5小，所以交换位置，所以得到

[ 1, 4, 5, 3, 6, 2, 7 ]

3、将 5 和 3作比较，3比5小，所以交换位置，所以得到

[ 1, 4, 3, 5, 6, 2, 7 ]

4、依次类推，最后一次比较时候应该是6和7做比较，第一轮循环最终得到

[ 1, 4, 3, 5, 2, 6, 7 ]

...
此时，我们已经将最大的数“冒泡”到了序列的最后一个位置，稍后我们继续重复此步骤直到没有任何一组元素需要对比位置

此时应该大概了解了冒泡排序的算法流程，但是对细节还略有模糊，那么我们在结合代码做理解

代码示例

1、我们创建一个排序方法，并接受一个参数，就是我们需要排序的数组

function bubbleSort( _array ){
    
}

2、ok，我们来实现第一个循环，不停的将相邻的两个元素做比较，这里使用循环结束条件为数组的长度 - 1，举个例子说明原因：
例如： [1,3,2] 当循环索引为 1时，就是数组中元素值为3的下标，此时3 和 2 比较完成后，3已经“冒泡”到了最右边，没有必要再去使用3和他的后面一个元素做比较了

function bubbleSort( _array ){
    //cache用于元素交换位置
    var cache = '';
    //这里我们从下标为0的第一个元素开始循环
    for( let j = 0; j < _array.length - 1; j++ ){
        //判断当前的元素是否大于它后面的元素，当前元素下标为0，则后一个就是0 +1
        if( _array[j] > _array[j+1] ){
              //如果大于则交换位置
              cache = _array[j];
              _array[j] = _array[j+1]
              _array[j+1] = cache;
        }
    }
}

3、经过步骤2 后我们就完成了一次逐个对比前后两个元素的循环，那么根据和核心特点，此时我们需要不停的重复这个步骤，直到元素排序完毕。
我们来增加一个外部的循坏来不停的重复里面这个步骤

function bubbleSort( _array ){
    //cache用于元素交换位置
    var cache = '';
    //这里我们使用一个外部循坏来重复下面的动作
    for( let i = 0; i < _array.length; i++ ){
        //这里我们从下标为0的第一个元素开始循环
        for( let j = 0; j < _array.length - 1; j++ ){
            //判断当前的元素是否大于它后面的元素，当前元素下标为0，则后一个就是0 +1
            if( _array[j] > _array[j+1] ){
                //如果大于则交换位置
                cache = _array[j];
                _array[j] = _array[j+1]
                _array[j+1] = cache;
            }
        }
    }

    return _array;
}

至此我们就完成了冒泡排序的基本实现。

引申

在理解了上述以后，我们来略微的提高一下性能问题
依然是举个例子：
有如下数组：

var a = [1,4,3,5,2]

经历一次循环分别比较了 [1,4] [4,3] [4,5] [5,2] 总共比较了 4 次最后得到数组

[1,3,4,2,5]

经历第二次循环分别比较了 [1,3] [3,4] [4,2] 总共比较了 3 次最后得到数组

[1,3,2,4,5]

可以发现每次循坏比较的次数是依次减一的，因为每次循坏过后都能得到最大的值，所以我们的内部循环结束条件可以优化为

function bubbleSort( _array ){
    //cache用于元素交换位置
    var cache = '';
    //这里我们使用一个外部循坏来重复下面的动作
    for( let i = 0; i < _array.length; i++ ){
        //这里我们从下标为0的第一个元素开始循环
        for( let j = 0; j < _array.length - 1 - i; j++ ){
            //判断当前的元素是否大于它后面的元素，当前元素下标为0，则后一个就是0 +1
            if( _array[j] > _array[j+1] ){
                //如果大于则交换位置
                cache = _array[j];
                _array[j] = _array[j+1]
                _array[j+1] = cache;
            }
        }
    }

    return _array;
}

后续其实可以在通过增加变量来跳过多余的比较操作再来继续优化，老规矩，我们等待系列完毕后，在进行优化相关的知识讨论

$\color{#34a853}{感谢阅读！}$