按字典顺序对整数数组进行排序

Question

我遇到了这样一个问题：

编写程序，对小于给定数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.
            }
        }
    }

- Himanshu Yadav

Answer 1

Java String#compareTo 已经实现了这个功能，您可以通过将您的 Integer 对象转换为 String 对象并调用 compareTo 方法来轻松访问它。

Arrays.sort(input, new Comparator<Integer>() {
   @Override
   int compareTo( Integer x, Integer y ) {
      return x.toString().compareTo( y.toString() );
   }
};

我可以告诉你这种方法的内存效率有多高，你需要为数组中的每个原始int创建1个整数对象，然后为您拥有的每个整数对象创建1个字符串对象。因此，在创建对象方面可能会存在相当大的开销。

- Hunter McMillen

---

我的Eclipse出现了The method sort(int[]) in the type Arrays is not applicable for the arguments (int[], new Comparator<Integer>(){})错误。 - Himanshu Yadav

Answer 2

唯一可能的方法是实现你自己的Comparator，在其中将可比较的两个Integer转换为String对象，并对它们进行比较。 更新：下面是一个实现的例子：

    Integer[] input = {2,3,5,7,11,13,17,19};

    Arrays.sort(input, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1.toString().compareTo(o2.toString());
        }
    });

- Andremoniy

---

-1 表示“唯一可能的方法”，但我可以想到许多，许多种方法，其中有些更有效率。 - rolfl

@rolfl 只是想让我站起来吗？你可以想任何你想要的。我说了我说的话。如果你知道“更有效率”的方法，就介绍并呈现出来。 - Andremoniy

在Eclipse中出现错误The method sort(int[]) in the type Arrays is not applicable for the arguments (int[], new Comparator<Integer>(){})。 - Himanshu Yadav

@HimanshuYadav 确定，你需要将 int 改为 Integer。请更仔细地查看我的代码，它使用了 Integer 数组。 - Andremoniy

引入了一种更高效的方式...并进行了演示。 - rolfl

Answer 3

考虑到问题的限制条件，解决此问题的更有效方法是根本不使用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));
}

- rolfl

Answer 4

只是为了补充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();

- Mureinik

Answer 5

如果您不想将整数值转换为字符串（可能会浪费内存），可以尝试以下方法。

您可以基于最高位数字对数字进行排序。参见本文：在Objective C中获取值的最高位数字（这应该很容易移植到Java中）。

实际上，您可以将该函数用作比较器的一部分。您需要找到一个解决平局的办法（例如，具有相同最高位数字的数字）。如果两个数字具有相同的最高位数字，则可以将它们拆开，并反复调用此函数多次（直到判断出一个数字大于另一个数字，或者直到使用完所有数字，表示它们相等为止）。

- mattnedrich