按字典顺序对int数组进行排序
我遇到了一个问题：
WAP按数字排序小于给定N的素数。 如果N为40，则输出应为11,13,17,19,2,23,29,3,31,37,39,5,7。注意：限制内存使用。
获得主要号码很容易。 但我无法找出一种有效的整数数组排序方法。
public static void getPrimeNumbers(int limit) { for (int i=2; i<=limit; i++) { if(isPrime(i)) { System.out.println(i); } } } public static boolean isPrime(int number) { for(int j=2; j<number; j++) { if(number%j==0) { return false; } } return true; } public static void lexographicSorting() { int[] input = {2,3,5,7,11,13,17,19}; int[] output = {}; for (int i=0; i<input.length; i++) { for(int j=0; j<input.length; j++) { ////Stuck at this part. } } } 考虑到问题的限制，解决此问题的更有效方法是根本不使用String和Integer实例。 该问题的一个指令是限制内存使用。 到目前为止，在每个答案中，都会对内存产生重大影响（转换为Integer和String ）。
这是一个可能更快的解决方案，并且根本不分配堆内存（尽管它具有递归，因此它可能具有一些堆栈效果 – 与Arrays.sort()大致相同）。 这解决了第一原理的问题，它没有为结果分配单独的数组，因此，与其他解决方案相比，它相对较长，但是，那些其他解决方案隐藏了该解决方案所没有的大量复杂性。 。
// this compare works by converting both values to be in the same 'power of 10', // for example, comparing 5 and 20, it will convert 5 to 50, then compare 50 and 20 // numerically. public static final int compareLexographicallyToLimit(final int limit, int a, int b) { if (a == b) { return 0; } if (a > limit || b > limit || a < 0 || b < 0) { return a > b ? 1 : -1; } int max = Math.max(a, b); int nextp10 = 1; while (max > 10) { max /= 10; nextp10 *= 10; } while (a < nextp10) { a *= 10; } while (b < nextp10) { b *= 10; } return a > b ? 1 : -1; } private static void sortByRules(final int[] input, final int limit, final int from, final int to) { if (from >= to) { return; } int pivot = from; int left = from + 1; int right = to; while (left <= right) { while (left <= right && compareLexographicallyToLimit(limit, input[left], input[pivot]) <= 0) { left++; } while (left <= right && compareLexographicallyToLimit(limit, input[pivot], input[right]) <= 0) { right--; } if (left < right) { int tmp = input[left]; input[left] = input[right]; input[right] = tmp; left++; right--; } } int tmp = input[pivot]; input[pivot] = input[right]; input[right] = tmp; sortByRules(input, limit, from, right-1); sortByRules(input, limit, right+1, to); } public static void main(String[] args) { int[] input = {2,3,5,7,11,13,17,19,31,37,41, 43, 100}; sortByRules(input, 40, 0, input.length - 1); System.out.println(Arrays.toString(input)); sortByRules(input, 15, 0, input.length - 1); System.out.println(Arrays.toString(input)); }
Java String#compareTo已经实现了这个function，您可以通过将Integer对象转换为String对象并调用compareTo来轻松访问它
Arrays.sort(input, new Comparator() { @Override int compareTo( Integer x, Integer y ) { return x.toString().compareTo( y.toString() ); } };
我可以确切地说这是多么节省内存，你必须为数组中的每个原始int创建1个Integer对象，然后你必须为你拥有的每个Integer对象创建1个String对象。 因此，对象创建可能会产生大量开销。
唯一可能的方法是实现您自己的Comparator ，您可以将两个可比较的Integer -s中的每一个转换为String对象并对它们进行比较。
UPD：这是一个例子，如何实现它：
Integer[] input = {2,3,5,7,11,13,17,19}; Arrays.sort(input, new Comparator() { @Override public int compare(Integer o1, Integer o2) { return o1.toString().compareTo(o2.toString()); } });
如果您不想将整数值转换为字符串（这可能会浪费），您可以执行类似的操作。
您可以根据最高有效数字对数字进行排序。 请参阅此文章以计算数字中最重要的数字：在Objective C中获取值最重要的数字 （应该很容易移植到Java）。
基本上，您可以将该function用作比较器的一部分。 你需要一种方法来打破关系（例如，具有相同最高位数的数字）。 如果两个数字具有相同的最高有效数字，您可以将它们摘下并根据需要反复重复调用此函数（直到您可以认为一个数字大于另一个数字，或直到您的数字用完为止，表明他们是平等的。
为了补充Hunter McMillen的答案，Java 8的语法允许以更清洁，更精简的方式定义Comnparator 。 由于Arrays.sort(int[])没有带有Comparator的重载变量，因此为了使用Comparator ，必须装箱数组。 例如：
int[] output = Arrays.stream(input) .boxed() .sorted(Comparator.comparing(String::valueOf)) .mapToInt(Integer::intValue) .toArray();