开发自己的排序算法。
它不能使用任何其他类来寻求帮助。
它需要能够对数百万个整数数组进行排序。
它需要尽可能快。
例如：
int[] old = {5434, 3454, 2, 0, 356, 896, 7324, 888, 99, 78365, 111};
int highestNumber = 78365;
be
int[] new = {0, 2, 99, 111, 356, 888, 896, 3454, 5434, 7324, 78365};
我整夜都在努力想出自己的方法来做到这一点。这就是我想出的。
public class Main {
public static void main(String[] args) {
int[] twentyMillion = new int [20000000];
for (int i = 0; i < a.length; i++) {
twentyMillion [i] = new Random().nextInt(20000000);
}
sortByAccendPro(twentyMillion , 20000000);
}
/**
* Jasz sort algorithim.
*
* @param {int[]} twentyMillion - array of twenty million random ints.
* @param {int} highestNumber - Highest number to sort to.
*/
public void sortByAccendPro(int[] twentyMillion, int highestNumber ) {
int[] rangePosition = new int[twentyMillion.length];
int[] newArray = new int[twentyMillion.length];
int[] range = new int[highestNumber];
long time = System.nanoTime();
for (int i = 0; i < twentyMillion.length; i++) {
rangePosition[i] = twentyMillion[i];
range[twentyMillion[i]]++;
}
for (int i = range.length - 1, past = twentyMillion.length; i >= 0; i--) {
range[i] = past - range[i];
past = range[i];
}
for (int i = 0; i < twentyMillion.length; i++) {
newArray[range[rangePosition[i]]] = twentyMillion[i];
range[rangePosition[i]]++;
}
System.out.println("time = " + (System.nanoTime() - time));
}
}
步骤：例如，如果
rangeArray从0变为3,000,000，则它将在该数组中找到的每个数字的每种情况递增。因此，每次找到2,750,000时，它都会递增rangeArray中的该位置。第二个循环从
rangeArray中的最大位置向后工作。因此，如果大小为3,000,000，并且有100,000个案例，即3,000,000，则表示3,000,000将以2,900,000开始并达到最大值。第3个循环循环遍历主数组，从而在范围数组中获取相同的索引并进行插入
newArray中正确位置的数字。它可以处理重复项，并且只需稍作修改，就可以使它处理许多其他事情。它使用了比我想要的更多的内存来进行排序，但是哇，它的速度更快。在进行此操作之前，我从未想过要研究这些排序算法的工作原理，但却找不到与之比较的东西。 >
#1 楼
您实现的算法称为计数排序。它的运行时成本在输入的大小上是线性的–比任何基于比较的排序算法都可能更快。 （以输入中最大元素和最小元素之差也呈线性关系为代价。）祝贺您自己提出了这个想法。由于他们已经为您提供了数组中最大的数字作为附加输入，因此他们很可能希望看到此算法。 （当然，如果需要，您可以在线性时间内找到最大值。）关于代码的说明：
rangePosition数组使用twentyMillion的确切副本，然后只读取一次。为什么创建它而不是直接使用twentyMillion？如果
twentyMillion包含负数，则实现会爆炸。也许您只是忘记提及所有输入均保证为非负值？否则，您还需要知道最小值并将其标准化。 （如果最小值远大于零，这也可以帮助您节省一些东西。）如果
highestNumber太大，则会出现问题。例如，您可能没有收到new int[Integer.MAX_VALUE]便无法分配OutOfMemoryError。 （如果在输入中允许使用负数，则甚至可能需要大于Integer.MAX_VALUE的数组！）即使可以分配它，对其进行迭代也将永远花费。如果您想使代码更健壮，则可以通过某种启发式方法来确定twentyMillion.length和highestNumber的组合是否需要保证计数排序的开销，还是最好使用基于比较的O（nlog（n））回退-algorithm。twentyMillion是变量的较差名称，它不一定命名长度为20M的数组。评论
\ $ \ begingroup \ $
谢谢，当我以为我做了自己的算法:(那正是我的方法的工作方式。最大值是一个问题。真正的问题是按mod值排序，但我注意到您可以通过其他多种方式使用我将其转换为此。您对rangePosition是正确的，我也认为不需要
\ $ \ endgroup \ $
– Xjasz
15年5月18日在21:19
#2 楼
这是一次采访，您将有机会炫耀您所知道的东西。如果我正在“评估”您的提交内容，我的印象是什么？不要不好用。您的代码太可怕了：
for (int i = 0; i < a.length; i++) {
twentyMillion [i] = new Random().nextInt(20000000);
}
在循环内部创建新的Random是对此类的不良使用。创建一个随机实例，然后重新使用它：
Random rand = new Random();
for (int i = 0; i < a.length; i++) {
twentyMillion [i] = rand.nextInt(20000000);
}
将常数用于幻数...。20,000,000是一个常数，应这样声明：
private static final int dataSize = 20_000_000;
请注意，我在其中使用
_来表明我知道它作为语言功能存在的事实（至少从Java 7开始）。 br />接下来，我没有看到任何Java-8功能。对于面试，我希望您能“赞叹”我……但是在您的代码中没有什么令人兴奋的技术。例如，创建输入数组很容易实现： Random rand = new Random();
int[] toSort = IntStream.generate(() -> rand.nextInt(dataSize))
.limit(dataSize)
.toArray();
我可能也将其放在一种方法中，以显示一些功能提取：
private static final int[] generateData(int size) {
Random rand = new Random();
return IntStream.generate(() -> rand.nextInt(size))
.limit(size)
.toArray();
}
对，这表明对Java 8已有一定的了解，一些语言结构，代码纪律等等。 ？
尽可能快地
这是一个加载的问题。最快的排序取决于您的需求中未提供的约束。对于有限的数据集，计数排序会很快，但是可能需要很大的空间。其他类型的内存不仅足够快，而且对内存的要求也要小得多。我认为这是一个“技巧性问题”。
顺便说一句，您的变量名已经被其他答案覆盖，但我想重申一下，他们需要更多的工作。
评论
\ $ \ begingroup \ $
+1随机捕获。为了使Random类正常工作，您需要为循环内的所有项目保留相同的随机种子。否则，您将得到大量的非随机数。您可以通过创建具有2个功能的控制台应用程序自行尝试。有一个函数在循环内部声明Random，另一个在外部声明。然后让循环运行1000次迭代，每次打印输出。很明显，哪种方法是使用Random的正确方法。
\ $ \ endgroup \ $
–杰森·哈钦森（Jason Hutchinson）
15年5月19日在12:24
\ $ \ begingroup \ $
Random实际上有一个Random :: ints（long，int，int）方法。因此，您可以使用新的Random（）。ints（dataSize，0，dataSize）.toArray（）。哇，够了吗？ ：p
\ $ \ endgroup \ $
–奥利维尔·格雷戈尔（OlivierGrégoire）
15年5月19日在17:34
\ $ \ begingroup \ $
@OlivierGrégoire-实际上，这已经足够了。 ;-)
\ $ \ endgroup \ $
–rolfl
2015年5月19日17:36
\ $ \ begingroup \ $
“……炫耀我知道它存在的事实……”-哈哈，哼了一声，不错的一个:-)
\ $ \ endgroup \ $
–user7649
2015年5月20日下午5:38
#3 楼
您所做的工作看起来像Bucket Sort，但是您的确切算法对我来说还是个谜。存储桶排序的问题是，在对任意整数进行排序时，您可能需要多达4Gi存储桶。这有点太多了。使用16GiB内存，您可以将它们打包到4个new int[1<<30]阵列中，但是该算法会变得非常慢（由于内存位置差，并且簿记数据比要排序的项目多）。所以我想d使用无限排序的快速排序。在有限范围内，您的算法很好。
* @param {int} highestNumber - Highest number to sort to.
如果不需要此参数，则该方法将更通用。这是多余的，您可以自己计算。这将花费一些时间，因此在极端情况下，您可能希望同时提供这两个版本。当然，它并不是真正的中间，但仍然是中间。可能不是你的错。因此，我将展示我的版本（未经测试但不重要的版本），而不是进行审查：
它也不返回。如果JVM足够聪明和邪恶，那么可以将整个方法减少到两条nanoTime行。在更简单的情况下，确实会发生类似的事情，因此不要让您的基准忽略要计算的值。
评论
\ $ \ begingroup \ $
这是我所说的最快的方式
\ $ \ endgroup \ $
– Abr001am
15年5月18日在20:20
\ $ \ begingroup \ $
@ Agawa001我知道了！但这仅在要保留某些内容的情况下才需要（您要根据鞋子的大小对鞋子进行分类，而鞋子的大小并不是唯一的属性）。对于int而言，值无非是什么，因此仅根据计数覆盖整个数组就足够了。
\ $ \ endgroup \ $
– maaartinus
15年5月18日在23:27
\ $ \ begingroup \ $
他实际上只使用计数排序。如果是存储桶排序，他将在每个存储桶中放置多个值。桶分类和基数分类是计数分类的高级类型。我也听说过'Tim Sort'看起来比quicksort更快，即使它只是合并排序和插入排序的混合。
\ $ \ endgroup \ $
– klaar
16年8月18日在9:11
评论
欢迎使用代码审查！我已回滚上一次编辑。收到答案后，请查看您可能会做什么和可能不会做什么。如果您不做一些大胆的假设，则所有代码将变得不可用：祝您好运，在普通计算机上使用默认设置制作一个大小为Integer.MAX_VALUE + 2的数组。为什么所有人都只期望具有方便上限的正值？
@Jasz在面试中被要求...开发一种新的整数排序算法？你留下来了吗？
@BradWerth他在实际的排序算法中没有使用任何类，我不认为他们期望他编写自己的Random实现器
请不要更新您问题中的代码以合并答案的反馈，因为这样做有悖于“代码审阅”的“问题+答案”风格。这不是一个论坛，您应该在其中保留问题的最新版本。收到答案后，请查看您可能会做什么和可能不会做什么。