数组排序问题

Question

对一个已知数组array('1','3','100','5','99','2'); 数组个数为1000000000；里面值是无序的，进行排序，找出第二大的数。要求：用时最少的排序算法。 语言不限。 指导指导。

Answer 1

就用冒泡排序不就ok了。你百度一下js的冒泡排序

Answer 2

如果只是要找出第二大的数，根本不需要排序啊。O(N) 啊~

Answer 3

你要找出第二大的数字，只需要维护最大值和第二大的值即可，对数组进行遍历，遍历一次就可以得到这两个值，这个操作的时间复杂度就是O(N).

Answer 4

如果不用原生排序的话,可以用快排，至于最快也没办法直接肯定，快排还是存在不稳定因素

function qSort(list) {
    if (list.length == 0) {
        return [];
    }
    var lesser = [];
    var greater = [];
    var pivot = list[0];
    for (var i = 1; i < list.length; i++) {
        if (list[i] < pivot) {
            lesser.push(list[i]);
        } else {
            greater.push(list[i]);
        }
    }
    return qSort(lesser).concat(pivot, qSort(greater));
}

Answer 5

function findTheSecondLargestNumber(arr) {
  if (arr.length < 2) {
    throw 'the number of the array is less than 2'
  }

  let largestNum = -Infinity, secondLargestNum = -Infinity;

  arr.forEach(item => {
    if (item > largestNum) {
      [largestNum, secondLargestNum] = [item, largestNum]
    } else if (item > secondLargestNum) {
      secondLargestNum = item;
    }
  })

  return secondLargestNum
}


console.log(findTheSecondLargestNumber(['1','3','100','5','99','2']))
console.log(findTheSecondLargestNumber([]))

维护最大值和次大值即可