对于一个作业,我需要编写一个可以对数组进行排序的方法,排序方法应该尽可能高效。
- 数组的开头将出现所有除以 4 且没有余数的数字。
- 后面是所有除以 4 余数为 1 的数字
- 后面是所有除以 4 余数为 2 的数字
- 所有其他数字(除以四而剩下的三)将位于数组的末尾。
我尝试了这组 4 指针:
2个指针 首先是0和1的余数
2 指针位于数组的最后,用于 2 和 3 的余数
这是我到目前为止所能找到的(当然有问题),感谢您的帮助!
public static void sortByFour (int[] arr)
{
int temp;
int noRemainderIndex = 0;
int remainder1Index = 1;
int remainder2Index = arr.length - 2;
int remainder3Index = arr.length - 1;
for (int i = 0; i < arr.length; i++)
{
if (arr[i] % 4 == 0)
{
temp = arr[noRemainderIndex];
arr[noRemainderIndex] = arr[i];
arr[i] = temp;
noRemainderIndex++;
remainder1Index++;
}
else if (arr[i] % 4 == 1)
{
temp = arr[remainder1Index];
arr[remainder1Index] = arr[i];
arr[i] = temp;
remainder1Index++;
}
else if (arr[i] % 4 == 2)
{
temp = arr[remainder2Index];
arr[remainder2Index] = arr[i];
arr[i] = temp;
remainder2Index--;
}
else if (arr[i] % 4 == 3)
{
temp = arr[remainder3Index];
arr[remainder3Index] = temp = arr[i];
arr[i] = temp;
remainder3Index--;
remainder2Index--;
}
}
最佳答案
家庭作业提示。
如果允许您使用现有的库方法,请查看
Array.sort(...)
和Comparator
接口(interface)。 (请注意,要在对基本类型的数组进行排序时使用自定义比较器,您必须首先转换为包装类型;例如,将int[]
转换为Integer[]
、排序并转换回来。)如果不允许使用
Array.sort(...)
(或类似的),请弄清楚这是排序问题还是整理问题。换句话说,是否需要对 4 个类别中的数字进行重新排序(或保留顺序)。您可以使用 4 个临时数组来简化问题,但还有其他(更棘手的)解决方案,涉及多次遍历数组并交换元素对。
需要解决的问题之一是您事先不知道 4 个类别中的每一个类别中有多少个数字。因此您事先并不知道将号码转移到目的地。但有解决方案......
... the sort method should be efficient as possible.
这是家庭作业的要求,还是你的要求?
如果这是您自己添加的内容 - 注意 - 您的标记可能为简单的解决方案给出比(据称)更高效但过于复杂的解决方案更高的分数解决方案。
优秀的软件工程师不会在每个程序中都力求极致的效率。相反,他平衡了各种事情:
- 功能要求,
- 性能要求,
- 软件可维护性要求,以及
- 项目截止日期,
注意到其中一些要求可能是隐含的,和/或管理层没有正确理解。
(或者换句话说,一个程序速度很快......但不能可靠地工作,或者不可维护,或者没有及时准备好......是一个失败。)
另一方面,如果性能是本作业练习的要求,那么您的讲师应该已经解释了如何衡量 Java 小程序的性能。 (相信我……这不是一件简单的事情。)您需要将其应用于您的家庭作业问题,以决定哪种替代解决方案最快。
关于java - 数组排序有效,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10767729/