0

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

  1. 数组的开头将出现所有除以 4 的数字，没有余数。
  2. 后面是除以 4 余数为 1 的所有数字
  3. 后面是除以 4 余数为 2 的所有数字
  4. 在数组的末尾将是所有其他数字（那些除以 4 和其余 3 的数字）。

我试过这组 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--;
        }
    }
4

4 回答 4

2

为您的家庭作业提供提示。

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

  2. 如果您不允许使用Array.sort(...)（或类似），请确定这是排序问题还是整理问题。换句话说，如果有任何要求对 4 个类别中的数字进行重新排序（或保留顺序）。

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

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

...排序方法应该尽可能高效。

这是作业要求，还是您的要求？

如果这是您自己添加的内容 -请注意- 您的标记可能会为简单的解决方案提供更高的分数，而不是（据称）更有效但过于复杂的解决方案。

一个好的软件工程师不会在每个程序中都追求极致的效率。相反，他平衡了各种事情：

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

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

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

另一方面，如果性能是这个家庭作业的要求，那么你的讲师应该已经解释了如何用 Java 衡量小程序的性能。（相信我……这不是一件简单的事情。）你需要把它应用到你的作业问题上，以决定哪种替代解决方案最快。

于 2012-05-26T16:03:54.783 回答
0

我认为更好的方法是使用 4 个数组，每种情况一个。将每个数组视为一个队列。遍历数组并推送到相应的数组上。完成后，只需将数组彼此附加。一个非常干净的解决方案。

于 2012-05-26T16:03:28.337 回答
0

为什么不创建一个包含两个值的自定义类，即数字和余数。创建这个迷你类的数组，传递值并预先计算余数。这将帮助您不必在每次通过列表元素时重新计算余数。您必须根据剩余属性移动和排序元素。

然后你会遇到一个经典问题，即对只有少数独特元素的列表进行排序。您选择的排序算法的性能取决于初始条件。我可能会说最好的选择是 Shell 排序算法或 Quick3。

http://www.sorting-algorithms.com/few-unique-keys

于 2012-05-26T16:15:24.107 回答
0

我认为您想要类似于快速排序中使用的分区算法的东西。

4 个指针是一个好的开始，但让我改变它们的功能：
1) 指向余数的结尾 = 0
2) 指向余数的结尾 = 1
3) 指向余数的结尾 = 2
4) 指向开始未分类的

该数组分为 5 个部分：余数 = 0、1、2、3 和未分类。

If remainder = 3, just increment the pointer 4. The number if included in remainder = 3 group.
If remainder = 2, increment the pointer 3 and swap the current value with the value at pointer 3. Increment pointer 4.
If remainder = 1, increment the pointer 2, swap with current value; increment the pointer 3, swap with current value. Increment pointer 4.
If remainder = 0, well, do the swapping 3 times.

于 2012-05-26T16:20:04.117 回答