Javascript的双排序算法 [英] Javascript Double sorting algorithm

问题描述

最近我通过面试哪里去了，他们要我拿出一个排序算法，真正thew我。有谁知道解决这个如果它要在JavaScript做？

  

问题1：双排序

     

请写它接受一个字符串数组的方法。每个元素   可以是一个数字（165）或一个字（狗）。你的方法应该   排序并打印，使得（1）的字被印在阵列   字母顺序和数字顺序的号码，和（2）的   为了在阵列中文字和数字的是相同的。

     

实例（输入=>输出）：

 排序（['5'，'4'，'狗'，'1'，'猫']）
=＆GT; ['1'，'4'，'猫'，'5'，'狗']

排序（['狗'，'猫']）
=＆GT; ['猫狗']

排序（'5'，'3'）
=＆GT; ['3'，'5']
 

您可以使用标准库的排序功能，而应该认为   所有投入将是有效的。如果你做任何其他假设，请   记录那些为好。你可以使用任何编程语言   你想。

     

此外，你可以假设你会得到一个实用方法   返回给定字符串是否是一个有效的数字（例如    ISNUMBER（），其中 ISNUMBER（狗）返回假和 ISNUMBER（'15'）   返回真）。

解决方案

下面是一个简单的方法 - 过滤输入数组只有字符串和唯一编号的独立数组。然后根据他们的自然排序的均匀类型数组排序。然后产生一个最终排序阵列填充的索引的原始数组中的类型。

例如：

 函数doubleSort（ARR）{
  //按类型分隔值。
  VAR数= []，字符串= [];
  arr.forEach（函数（X）{
    如果（ISNUMBER（X））{
      numbers.push（数（X））;
    } 其他 {
      strings.push（X）;
    }
  }）;
  //排序字符串和数字分开。
  strings.sort（）;
  numbers.sort（功能（A，B）{返回一个 -  B;}）;
  //从输入数组类型合并排序的数组。
  变种排序= []，nextNumber = 0，nextString = 0;
  arr.forEach（函数（X）{
    如果（ISNUMBER（X））{
      sorted.push（字符串（数字[nextNumber ++]））;
    } 其他 {
      sorted.push（字符串[nextString ++]）;
    }
  }）;
  返回排序;
}

// XXX：很多陷阱，但对这项工作不够好。
功能ISNUMBER（X）{
  返回数（X）的ToString（）=== X;
}
 

在BIG-O性能受底层的排序算法，所以可能为O（n log n）的。

I recently went through an interview where they asked me to come up with a sorting algorithm that really thew me off. Does anyone know the solution to this if it were to be done in 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).

解决方案

Here's a simple approach - filter the input array into separate arrays of only strings and only numbers. Then sort the homogeneously typed arrays per their natural ordering. Then produce a final sorted array populated by the type of the indices in the original array.

For example:

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;
}

The Big-O performance is bound by the underlying sort algorithm, so likely O(n log n).

这篇关于Javascript的双排序算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！