Code Signal – 按身高排序(Sort by Height)

Some people are standing in a row in a park. There are trees between them which cannot be moved. Your task is to rearrange the people by their heights in a non-descending order without moving the trees. People can be very tall!

Example：

For a = [-1, 150, 190, 170, -1, -1, 160, 180], the output should be sortByHeight(a) = [-1, 150, 160, 170, -1, -1, 180, 190].

Input/Output:

[execution time limit] 4 seconds (js)

[input] array.integer a

If a[i] = -1, then the ith position is occupied by a tree. Otherwise a[i] is the height of a person standing in the ith position.

Guaranteed constraints:

1 ≤ a.length ≤ 1000,

-1 ≤ a[i] ≤ 1000.

[output] array.integer

Sorted array a with all the trees untouched.

解题思路
重点在于排序，排序，还是排序。

排序时 a[n] = -1 是可以忽略掉的情况。

随后再使用已经排序好的，人的身高 的那部分，去对比原本的 a，当 a[n] = -1，即碰到输的情况时跳过，继续迭代。当 a[n] != -1 为人的身高，去将已经排序好的身高替换原本的身高即可。

时间复杂度为 O ( n l o g ( n ) ) O(n log(n))O(nlog(n))，使用的是 JavaScript 内部实现好的排序方式。

空间复杂度为 O ( n ) O(n)O(n)，最差情况为没有树，全是人。