java - 数组排序有效

Question

对于一个作业，我需要编写一个可以对数组进行排序的方法，排序方法应该尽可能高效。

1. 数组的开头将出现所有除以 4 且没有余数的数字。
2. 后面是所有除以 4 余数为 1 的数字
3. 后面是所有除以 4 余数为 2 的数字
4. 所有其他数字(除以四而剩下的三)将位于数组的末尾。

我尝试了这组 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--;
        }
    }

Answer 1

家庭作业提示。

1. 如果允许您使用现有的库方法，请查看 Array.sort(...) 和 Comparator 接口(interface)。 (请注意，要在对基本类型的数组进行排序时使用自定义比较器，您必须首先转换为包装类型；例如，将 int[] 转换为 Integer[] 、排序并转换回来。)

2. 如果不允许使用Array.sort(...)(或类似的)，请弄清楚这是排序问题还是整理问题。换句话说，是否需要对 4 个类别中的数字进行重新排序(或保留顺序)。

3. 您可以使用 4 个临时数组来简化问题，但还有其他(更棘手的)解决方案，涉及多次遍历数组并交换元素对。

4. 需要解决的问题之一是您事先不知道 4 个类别中的每一个类别中有多少个数字。因此您事先并不知道将号码转移到目的地。但有解决方案......

<小时/>

... the sort method should be efficient as possible.

这是家庭作业的要求，还是你的要求？

如果这是您自己添加的内容 - 注意 - 您的标记可能为简单的解决方案给出比(据称)更高效但过于复杂的解决方案更高的分数解决方案。

优秀的软件工程师不会在每个程序中都力求极致的效率。相反，他平衡了各种事情:

• 功能要求，
• 性能要求，
• 软件可维护性要求，以及
• 项目截止日期，

注意到其中一些要求可能是隐含的，和/或管理层没有正确理解。

(或者换句话说，一个程序速度很快......但不能可靠地工作，或者不可维护，或者没有及时准备好......是一个失败。)

另一方面，如果性能是本作业练习的要求，那么您的讲师应该已经解释了如何衡量 Java 小程序的性能。 (相信我……这不是一件简单的事情。)您需要将其应用于您的家庭作业问题，以决定哪种替代解决方案最快。