今天去面试，被问到了以下问题：

从1000个正整数中找出最大的五个数

我的解法

思路：先生成一个含1000个数的随机数组Arr1，然后建立一个空数组Arr2，及一个变量max=0。
然后遍历Arr1，其中大于max的数存入数组2。便利过后，得到递增数组Arr2。
用slice方法取Arr2后五位即为最大五位。
var Arr1 = [];
for (var i = 0; i<1000; i++){
Arr1[i] = Math.floor(Math.random()*1000+1);
}; //先生成1000个正整数

var Arr2 = new Array();
var max = 0;

for (var i = 0; i<1000; i++){
    if (Arr1[i]>max){
        Arr2.push(Arr1[i]);
        max = Arr1[i];
    } 
};
var result = Arr2.slice[-5];
console.log(result);

运行结果如下：

1
(5) [982,985,993,996,998]

这个算法看似能找出最大数，但是存在以下问题：
当Arr1为[100,999,…,1]这样的递减数列时，只能找出第一个最大数，无法将Arr2凑满。而且，面试官还问到了时间复杂度的问题，当时我并没有概念。

问题分析

为妥善解决问题，还是将Arr1数组从小到大重新排列，这样就不会受到原数据中大小次序影响。
因此可以采用算法学中的排序方法，如冒泡排序、选择排序、插入排序等。

概念解释

算法复杂度的概念（包括时间复杂度和空间复杂度）：

http://blog.csdn.net/booirror/article/details/7707551/
http://www.jianshu.com/p/99bac69fdd97

排序算法的Javascript实现：

https://github.com/damonare/Sorts

解法优化

之前解法的时间复杂度为O(n)。
现在采用更稳妥的，可排序的冒泡排序算法，时间复杂度为O(n*n)。代码实现如下：

var Arr1 = [];
for (var i = 0; i<1000; i++){
    Arr1[i] = Math.floor(Math.random()*1000+1);
};

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {        //相邻元素两两对比
                var temp = arr[j+1];        //元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

var Arr2 = bubbleSort(Arr1);
var result = Arr2.slice(-5);
console.log(result);

代码运行截图： 

1
(5) [998,999,999,1000,1000]

补充一个选择排序，仅供娱乐

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
var arr = [],
  newArr = []

for (let i = 0; i < 10; i++) {
  var random = Math.ceil(Math.random() * 100)
  arr.push(random)
}

function finMax(array) {
  var max = array[0]
  for (let i in arr) {
    if (array[i] > max) {
      max = array[i]
    }
  }
  return max
}

function selectSort(array) {
  for (let i = 0, len = array.length; i < len; i++) {
    var max = finMax(array)
    newArr.unshift(max)
    array.splice(array.indexOf(max), 1)
  }
}

console.log(arr)
selectSort(arr)
console.log(newArr)

最后

显然，实现了目的，但是算法上还可以采用时间复杂度更低的算法。

怎样才能找到尽可能优的解法呢？

且听下回分解