算法学习（三）：冒泡排序

冒泡排序是最常见和简单的排序算法。
本篇博客主要介绍了冒泡排序的原理和js实现。同时也涉及到了基础冒泡算法的一些优化方法。

原理

定义

冒泡排序(Bubble Sort)是一种经典的排序算法，它重复的走访要排序的数列，依次比较当前元素和下一个元素，如果两个元素的顺序错误就交换两个元素的顺序，直到没有元素需要交换为止。

因为最值数在排序时经由交换，像水中的泡泡冒到水面一样浮动到数列的顶端，因此称其为冒泡排序。

运作过程

根据上文冒泡排序的定义可知，冒泡排序运作的步骤如下：

从第一个元素比较相邻的一对元素，如果第一个元素比第二个大，就交换它们两个。
移动到下一个元素，重复上一步骤，一直到倒数第二个元素，此时数列的最后一个元素，就会是最大值。
重复1，2 步骤一直到倒数第三个元素，此时数列的倒数第二个元素就会是数列第二大的值。
持续对越来越少的待排序元素重复以上的步骤，直到没有任何一对数字需要比较。

下面是冒泡算法的一个运作过程动图，

`JS`实现

根据冒泡算法的定义和运作过程，基础的冒泡算法实现过程如下：

function bubble_sort(arr){
    var len = arr.length;
    for(let i=len-1;i>0;i--){
        for(let j=0;j<i;j++){
            if(arr[j] > arr[j+1]){
                [ arr[j], arr[j+1] ] = [ arr[j+1],arr[j] ]
            }
        }
    }
    return arr;
}

在上面的实现中，我们分析可得冒泡算法的时间频度(即具体执行次数)和问题规模n (即数组长度)的关系为

T(n)=(n-1)+(n-2)+(n-3)+...+1 , 简化表达式后，可得:$$T(n) = \frac{n^2-n}{2}$$

从而可以得出，冒泡算法的时间复杂度为 O( n² ) 。

优化

优化一

在上面的冒泡算法js实现中，内层的for循环在每次循环时都会循环到上次结束循环减一的位置，考虑到在循环结束的位置之前可能已经存在很多顺序正确无需交换的元素，以上实现其实还有继续优化的空间。

根据冒泡算法的原理，遍历一对对相邻元素，顺序不正确的一对元素，会交换其位置，顺序正确的相邻元素不会发生交换。那么我们得出结论，一次循环中最后一次发生交换的位置，其后的所有元素一定是已排好顺序的。

那么我们可以记录每次循环中最后一次交换元素的位置，在下次循环中只需要循环到此位置即可，从而减少循环次数，优化冒泡算法，代码实现如下：

function bubble_sort_two(arr){
    let len = arr.length;
    for(let i=len-1;i > 0;i=pos){
        pos = 0;        //每次内层循环前将最后一次交换位置pos归0从而开始重新记录
        for(let j=0;j<len-1-i;j++){
            if(arr[j] > arr[j+1]){
                [ arr[j], arr[j+1] ] = [ arr[j+1],arr[j] ];
                pos = j;  //记录每次内层循环的最后交换位置。
            }
        }
    }
    return arr;
}

优化二

在上面的冒泡排序过程中，每一遍排序操作都是从头循环到尾找到一个最大值。

考虑到我们可以通过在每一遍排序中进行正向和反向两遍冒泡，从而一次得出两个最终值位于本次循环两端（一个最大一个最小），从而达到节约时间,优化算法的目的。

代码如下:

function bubble_sort_three(arr){
    let len = arr.length;
    for(let i=len-1;i>0;i--){
        //正向循环
        for(let j=len-i;j<i;j++){
            if(arr[j]>arr[j+1]){
                [arr[j],arr[j+1]] = [arr[j+1],arr[j]];
            }
        }
        //反向循环
        for(let k=i;k<len-1-i;k--){
            if(arr[k]<arr[k-1]){
                [arr[k],arr[k-1]] = [arr[k-1],arr[k]];
            }
        }
    }
    return arr;
}

//也可以写成以下更直观的形式
function other_bubble_sort(arr){
    let len = arr.length;
    let right = len - 1;   //排序范围右边界
    let left = 0;          //排序范围左边界
    while(left < right){
        //正向循环
        for(j = left;j<right;j++){
            if(arr[j]>arr[j+1]){
                [arr[j],arr[j+1]] = [arr[j+1],arr[j]];
            }
        }
        right--;
        //反向循环
        for(k = right;k>left;k--){
            if(arr[k]<arr[k-1]){
                 [arr[k],arr[k-1]] = [arr[k-1],arr[k]];
            }
        }
        left++;
    }
}

优化三（鸡尾酒排序）

自然而然的，我们可以综合使用以上两种优化方式，既从两端分别冒泡，又记录每次最后交换的位置。这样经过优化之后的冒泡排序，又称为鸡尾酒排序(shaker Sort)。

function shaker_sort(arr){
    let len = arr.length;
    let right = len - 1;   //排序范围的右边界
    let left = 0;         //排序范围的左边界
    while(left < right){
        lastPosRight = 0;  //正向最后一次交换的位置
        for(j = left;j<right;j++){
            if(arr[j]>arr[j+1]){
                [arr[j],arr[j+1]] = [arr[j+1],arr[j]];
                lastPosRight = j;
            }
        }
        right = lastPosRight；
        lastPOSLeft = len -1 ;    //反向最后一次交换的位置
        for(k = right;k>left;k--){
            if(arr[k]<arr[k-1]){
                [arr[k],arr[k-1]] = [arr[k-1],arr[k]];
                lastPosLeft = k;
            }
        }
        left = lastPosLeft;
    }
    return arr;
}

以上就是关于冒泡排序算法的一些知识，谢谢阅读，希望对大家有所帮助。

原理

定义

运作过程

JS实现

优化

优化一

优化二

优化三（鸡尾酒排序）

`JS`实现