思路

使用 hashtable 做记录
如果发现数字 a 就记录 a:1，如果再一次出现就+1，变为 a:2
最后把哈希表的 key 全部打印出来，如果 a:b，那么 a 就要打印 b 次

举例说明

  1. [4,7,1,5,1,2,4]
  2. →循环 i<=array.length
  3. →{0:0
  4.   1:2
  5.   2:1
  6.   3:0
  7.   4:2
  8.   5:1
  9.   6:0
  10.   7:1
  11.  }
  12. →然后历遍这个 hashtable，打印出key，为0的就没有,i<=max
  13. →[1,1,2,4,4,5,7]

实际代码

  1. let sort = (numbers) => {
  2.     let hashTable = {}, max = 0, result = []
  3.     for (let i = 0; i < numbers.length; i++) {
  4.         if (!(numbers[i] in hashTable)) {
  5.             hashTable[numbers[i]] = 1
  6.         } else {
  7.             hashTable[numbers[i]] += 1
  8.         }
  9.         if (numbers[i] > max) {
  10.             max = numbers[i]
  11.         }
  12.     }
  13.     for (let j = 0; j <= max; j++) {
  14.         if (j in hashTable) {
  15.             for (let i = 0; i < hashTable[j]; i++) {
  16.                 result.push(j)
  17.             }
  18.         }
  19.     }
  20.     return result
  21. }

时间复杂度

O(n+max)

优缺点

优点

只遍历一次数组，高效，用空间换时间

缺点

占用的内存多