英文:
Optimized and efficient way to sort int[] primitive array in Java
问题
我对将int[]原始数组按降序排序进行了大量研究，但大多数方法建议创建一个ArrayList，然后使用Collections.sort()。
目前，我已经尝试过：
int arr[] = new int[] {1,5,6,3,2};
Arrays.sort(arr);
for(int i = 0; i <= arr.length / 2; i++) {
int temp = arr[i];
arr[i] = arr[arr.length - i - 1];
arr[arr.length - i - 1] = temp;
}
这具有O(nlogn)的时间复杂度和O(1)的空间复杂度。
是否可以用更少的代码并且同样高效地使用自定义compare()函数来实现呢？如果可以，应该如何做？我之所以要求更少的代码，是因为我希望在编程竞赛/面试中能够快速编写它！谢谢！
更新：我明白时间和空间复杂度已经达到最佳，但是否可能用更少的代码对数组进行排序？例如，通过使用自定义的compare/ lambda函数/等等？
英文:
I did a lot of research into sorting int[] primitive array in descending order, but most methods suggest creating an ArrayList and then using Collections.sort().
Currently, I have tried:
int arr[] = new int[] {1,5,6,3,2};
Arrays.sort(arr);
for(int i = 0; i <= arr.length / 2; i++) {
int temp = arr[i];
arr[i] = arr[arr.length - i - 1];
arr[arr.length - i - 1] = temp;
}
This is O(nlogn) time complexity and O(1) space.
Can I do this in less code and as efficiently using a custom compare() function? If so, how? I ask for less code, because I'd like to be able to write it quickly in coding competitions / interviews! Thanks!
UPDATE: I understand that the time and space complexities are the best they can get, but is it possible to sort the array in less lines of code. For example, by using a custom compare/ lambda function/ etc?
答案1
得分: 2
O(nlogn)时间复杂度和O(1)空间复杂度是排序的理论最佳结果。不，你无法通过算法来实现更快的排序。通常情况下，你可以在没有算法改进的情况下稍微加快速度，但这种提升通常很小，短暂，并且取决于你运行它的架构和月亮的相位。
除非复制Arrays.sort中的代码以反转方向，否则你无法优化掉O(n)的反转数组运行时间，尽管你可以像Sweeper在评论中建议的那样，更新其余的代码以反转用于查找事物的索引。
英文:
O(nlogn) time and O(1) space is the theoretical best result for sorting things. No, you can't algorithmically sort faster. You can, as usual, speed things up a bit without algorithmic improvement, but such gains are generally tiny, fleeting, and dependent on the architecture you run it on and the phase of the moon.
Short of copying the code from Arrays.sort just to reverse the direction, you can't optimize away the O(n) run to reverse the array, though you can, as Sweeper suggested in a comment, update the rest of the code to reverse the index used to look things up.
答案2
得分: 1
首先，你的代码在for循环的第二行和第三行存在一些问题，因为它尝试访问的第一个索引是"6"，但实际上它是不存在的。for循环的最后一行有一个多余的]。
所以，我认为这是你的意思，如果我理解错了，请随意纠正！
for(int i = 0; i <= arr.length / 2; i++) {
int temp = arr[i];
arr[i] = arr[arr.length - i - 1];
arr[arr.length - i - 1] = temp;
}
但是，如果你想要维护较低的空间复杂度，我认为你已经接近最小化了就地修改的方式。即使使用流也不会更短（但可能会显得有些混乱）。
另外，不想让事情变得更复杂，但如果你的数组使用了足够小的范围（编辑：更重要的是，你事先知道这个范围），你可以使用计数排序，它的时间复杂度为O(n+k)，而不是Arrays.sort()。
英文:
First off, you code has a few issues with the 2nd and 3rd line of the for loop, since the first index it tries to access is "6", which doesn't exist. The last line of the for loop has an extra ]
So, I think this is what you meant, feel free to correct me if I've got this wrong!
for(int i = 0; i <= arr.length / 2; i++) {
int temp = arr[i];
arr[i] = arr[arr.length - i - 1];
arr[arr.length - i - 1] = temp;
}
But if you want to maintain lower space complexity, I think the in-place modification you have is pretty close to as small as you're going to get. Even with streams, it's not going to get much shorter (but will get somewhat subjectively messier).
Also, not to complicate things further, but if your array uses a sufficiently small range (edit: and more importantly, you know that range beforehand), you can use counting sort, which is O(n+k) time complexity vs. Arrays.sort()
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论