【前端面试】（五）JavaScript冒泡排序

视频链接：
JavaScript冒泡排序 – Web前端工程师面试题讲解

教学网站：
visualgo.net

参考链接：
程序员内功：八大排序算法

先看如下的动画图理解一下冒泡怎么从小到大排列的：

可以看到每次遍历从第一个元素直至最后一个没有排序的元素，都会两两比较元素的大小，然后不停地切换位置（绿色标记）

这保证了每轮排序的最后一个元素一定是最大的，那么下一轮的对比就不用管最后一个元素了（橙色标记）。

那么开始实战

//创建一个变量作为临时存储数据的地方
const arr = [29,10,14,37,15];
//创建一个bubbleSort函数用来执行冒泡排序
function bubbleSort(arr){
    let temp;//临时交换变量
    //创建一个外围循环来确定要排序多少轮，
    //同时保证下一轮不会重复对比最后一个元素,
    //所以不用遍历到最后一个元素
    for(let i = 0; i < arr.length - 1; i++){
        //镶嵌循环则要做两两元素的比较与缩小每轮比较的目标数量
        for(let j =0; j < arr.length - 1 - i; j++){
            if (arr[j] > arr[j+1]){
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
    return arr;
}

console.log(bubbleSort(arr));

最终返回了正确的结果：

除了手撕代码外，还要清楚该排序算法的有关性质。

是否稳定

首先冒泡排序是稳定排序算法，看它稳不稳定是由在一个待排序数组中两个相同数组的元素在经过排序后的相对位置是否发生改变，而冒泡排序不会改变相同元素的相对位置。

时间复杂度:

最好情况是/(O(n)/),最坏情况是/(O(n2)/),一般选取最坏的作为平均时间复杂度。

优化

由于已经达到有序状态不会发生交换，所以可以尝试定一个变量记录当某一轮是否发生交换行为，若未发生则判定已经排序成功，跳出循环即可。

const arr = [29,10,14,37,15];
function bubbleSort(arr){
    let temp,haveChange;
    for(let i = 0; i < arr.length - 1; i++){
        haveChange=false;
        for(let j =0; j < arr.length - 1 - i; j++){
            if (arr[j] > arr[j+1]){
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
                haveChange=true;
            }
        }
        if(haveChange==false){
            break;
        }
    }
    return arr;
}

console.log(bubbleSort(arr));

可以看到舒服确实变快了