由如何找出数组中第二大的数引发的思考？

面试好多总会被问及排序问题，大多都是冒泡、二分、快速等，想想排序的原理，如果不深刻理解，面试的时候我自己都觉得自己蒙圈。。。比如冒泡排序，第一轮其实就能找到最大值，再找第二最大值怎么办？直接再来一轮，跟最大值比较呢？是否可以？因为要考虑算法复杂度的问题，假如数组很大，有重复数字的话，结果是否准确？我们怎么实现？

关键词：第二最大、算法复杂度、准确

首先看一下冒泡排序。

function getSecondBigNum(arr){    let temp;    for(let i = 0; i < 2; i++){        for(let j = 0; j < arr.length-1; j++){            if(arr[j]>arr[j+1]){                temp = arr[j]                arr[j] = arr[j+1]                arr[j+1] = temp            }        }    }    return arr[arr.length-2]}var arr = [8,6,2,7,3]console.log(getSecondBigNum(arr))

两轮循环即可，时间复杂度为2n，效率还可以，使用数组[8,6,2,7,3]来测试返回结果也没有问题，但是忽略了一个细节，题目中没有说明数组中的值是不重复的，所以对于[8,8,6,2,7,3]来说，返回结果就是错误的。

于是考虑两次迭代后判断最后两个值是否相等，如果相等再继续第三次冒泡排序，以此类推总能找到，但是面试官就问你了，你知道这样复杂度会怎样吗？极端情况下。数组很大，而且重复的有很多，那就是n²，效率太低。

再想想，既然第一次迭代就找出最大值，那就把最大值移出去，剩下的在做一次冒泡时间复杂度3n,差不多可以接受。代码如下：

function getSecondBigNum(arr){    let temp;    let newArr = []    for(let j = 0; j < arr.length-1; j++){        if(arr[j]>arr[j+1]){            temp = arr[j]            arr[j] = arr[j+1]            arr[j+1] = temp        }    }    //把最大值去除，包括重复的最大值    for(let i = 0; i< arr.length-1;i++){        if(arr[i] != arr[arr.length-1]){            newArr[i] = arr[i]        }    }    for(let j = 0; j< newArr.length-1; j++) {        if(newArr[j]>newArr[j+1]){            temp = newArr[j]            newArr[j] = newArr[j+1]            newArr[j+1] = temp        }    }
    return newArr[newArr.length-1]}var arr = [8,8,8,8,6,2,7,3]//即使有重复，也是可以的console.log(getSecondBigNum(arr))