Javascript 双重排序算法

Question

我最近接受了一次采访，他们让我想出一个真正让我失望的排序算法。如果要用 javascript 完成，有人知道解决方案吗？

Problem 1: Double Sort

Please write a method which accepts an array of strings. Each element can either be a number ("165") or a word ("dog"). Your method should sort and print the array such that (1) The words are printed in alphabetical order and the numbers in numerical order, and (2) the order of words and numbers within the array is the same.

Examples (input => output):

sort(['5', '4', 'dog', '1', 'cat'])
=> ['1', '4', 'cat', '5', 'dog']

sort(['dog', 'cat'])
=> ['cat', 'dog']

sort('5', '3')
=> ['3', '5']

You can use standard library sort functions, and should assume that all inputs will be valid. If you make any other assumptions, please document those as well. You can use any programming language that you'd like.

Additionally, you may assume that you'll be given a utility method that returns whether a given String is a valid number (e.g. isNumber(), where isNumber('dog') returns false, and isNumber('15') returns true).

Answer 1

这是一个简单的方法 - 将输入数组过滤为单独的仅包含字符串和仅包含数字的数组。然后按照它们的自然顺序对同构类型的数组进行排序。然后生成由原始数组中的索引类型填充的最终排序数组。

例如:

function doubleSort(arr) {
  // Separate the values by type.
  var numbers=[], strings=[];
  arr.forEach(function(x) {
    if (isNumber(x)) {
      numbers.push(Number(x));
    } else {
      strings.push(x);
    }
  });
  // Sort strings and numbers separately.
  strings.sort();
  numbers.sort(function(a, b) { return a - b; });
  // Merge the sorted arrays by type from the input array.
  var sorted=[], nextNumber=0, nextString=0;
  arr.forEach(function(x) {
    if (isNumber(x)) {
      sorted.push(String(numbers[nextNumber++]));
    } else {
      sorted.push(strings[nextString++]);
    }
  });
  return sorted;
}

// XXX: lots of pitfalls but good enough for this exercise.
function isNumber(x) {
  return Number(x).toString() === x;
}

Big-O 性能受底层排序算法的限制，因此很可能是 O(n log n)。