logo标签列表

在Java中对数组进行排序

javaarrayssortingmodulo
4

编写一个Java静态方法：

public static void sortByFour (int[] arr)

该方法接收一个由非负数（零或正数）组成的数组作为参数，并按照以下方式对数组进行排序：
- 所有能被四整除的数字将出现在数组的开头。 - 随后，所有余数为 1 的被 4 整除的数字将出现在它们后面。 - 然后，所有余数为 2 的被 4 整除的数字将出现在它们后面。 - 最后，剩下的所有数字（即余数为 3 的被 4 整除的数字）将出现在数组的末尾。
（每个分组内数字的顺序不重要。）
该方法必须尽可能高效。
以下是我写的代码，但很不幸它并没有很好地工作... :(
public static void swap( int[] arr, int left, int right )
{
    int temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
}

public static void sortByFour( int[] arr )
{
    int left = 0;
    int right = ( arr.length - 1 );
    int mid = ( arr.length / 2 );
    while ( left < right )
    {
        if ( ( arr[left] % 4 ) > ( arr[right] % 4 ) )
        {
            swap( arr, left, right );
            right--;
        }
        if ( ( arr[left] % 4 ) == ( arr[right] % 4 ) )
            left++;
        else
            left++;
    }
}

如何修复或重写我的代码，以便它可以良好地工作？

我的意思是，他应该使用“作业”标签进行标记。 - VeeArr
1
你为什么要使用那段代码？我的意思是，你想要实现什么逻辑呢？ - OscarRyz
2
-1 表示要求别人帮你完成作业。Polygenlubricants 和 GEShafer 已经给了你很好的推动。 - OscarRyz
2
“帮我找出问题在哪里”和“替我修复它”（即使加上“请”）是非常不同的事情。 - Stephen P
结尾的代码 if(condition) left++; else left++; 和 left++; 是等价的，不是吗？ - Bill the Lizard
显示剩余4条评论
6个回答
2

我会为你提供伪代码，但编写实际代码将直接告诉你答案，而这是作业，所以你应该自己完成。 =P

以下是没有使用列表的方法。这个示例根据要求进行了限制，但一旦你编写它，它就能够工作。

int bucketSize = (arr.length() / 4) + 1;

int bucket1[bucketSize];
int bucket2[bucketSize];
int bucket3[bucketSize];
int bucket4[bucketSize];

for (int i=0; i<arr.length; i++) {
    if ((arr[i] % 4) == 0)
        put arr[i] in bucket 1
    else if ((arr[i] % 4) == 1)
        put arr[i] in bucket 2
    else if ((arr[i] % 4) == 2)
        put arr[i] in bucket 3
    else
        put arr[i] in bucket 4
}

for (int i=0; i<4; i++) {
    this will go for each bucket
    for (int j=0; j<bucketSize; j++) {
        do sort of your choice here to sort the given bucket
        the sort you used in your code will do fine (the swapping)
    }
}

然后按照它们各自的顺序连接四个桶，以获得最终结果。
我还问了我的老师是否可以使用辅助数组，她说这不是想法...必须有比这更简单和高效的方法。 - user372003
1
首先，效率取决于你的编码方式，这只是伪代码。其次，要比这更高效的唯一方法是使用真正的桶排序，就像polygenelubricants上面发布的那样，但你不能使用列表。因此，我的建议是，如果你可以编写自己的列表类（相当简单），但仍然使用列表类，或者用数组替换列表（就像我向你展示的那样）。 - geshafer
不要使用数组，而是使用整数系统来索引数组中的位置，并执行相同的操作... - geshafer
你能否写下来让我理解一下？ - user372003
2

线性时间解决方案

最渐进式有效的方法是使用桶排序。

  • 你有4个桶，分别对应于模4同余类的每个数字。
  • 扫描数组中的数字一次
    • 将每个数字放入正确的桶中
  • 然后构造输出数组
    • 先将所有来自桶0的数字放在前面，然后是所有来自桶1的数字，然后是桶2，最后是桶3

因此，这样可以在O(N)的时间内对数字进行排序，这是最优的。关键在于通过对模4的数字进行排序，实际上只有四个数字需要排序：0、1、2、3。

使用List的说明性解决方案

这是一个实现上述算法（适用于一般模数M）的示例，使用List和for-each语句以增强清晰度。忽略未经检查的转换警告，专注于理解算法。

import java.util.*;

public class BucketModulo {
    public static void main(String[] args) {
        final int M = 4;
        List<Integer> nums = Arrays.asList(13,7,42,1,6,8,1,4,9,12,11,5);
        List<Integer>[] buckets = (List<Integer>[]) new List[M];
        for (int i = 0; i < M; i++) {
            buckets[i] = new ArrayList<Integer>();
        }
        for (int num : nums) {
            buckets[num % M].add(num);
        }
        nums = new ArrayList<Integer>();
        for (List<Integer> bucket : buckets) {
            nums.addAll(bucket);
        }
        System.out.println(nums);
        // prints "[8, 4, 12, 13, 1, 1, 9, 5, 42, 6, 7, 11]"
    }
}

一旦您完全理解了算法，将其转换为使用数组（如果必要）就非常简单。

另请参阅

关于%的特别说明

规定数字为非负数非常重要，因为%并不是按照数学定义中的模运算符，而是余数运算符。

System.out.println(-1 % 2); // prints "-1"

参考文献

2
您可以这样解决这个问题：
  1. 选择您想要使用的排序算法。看起来您正在尝试编写快速排序，但您也可以使用冒泡排序。
  2. 确定算法中比较输入数组中两个值的点。例如，在维基百科上冒泡排序的伪代码中，唯一的比较是该行：if A[i] > A[i+1] then...。
  3. 找出一种比较两个数字的方法，使得当一个数被4整除时余数为0的数字小于一个被4除后余数为1的数字。用您的比较器计算（例如，if myIsGreater(A[i], A[i+1]) then...）替换算法的比较操作。
第三步，您考虑模运算绝对是正确的方向。
1
+1 余数排序的要求绝对不是这个问题的重点，比较器会为您很好地处理它。 - nevets1219
2
我将重申Daniel所说的：您可以选择排序算法。如果要求如此，使用到目前为止课程中最有效的算法。但是当您的算法到达比较两个项的点时，请将它们的值模4进行比较。因此类似于if A[i] > A[j]的内容变成了if A[i] % 4 > if A[j] % 4。然后继续按照算法规定执行数组元素的操作。交换它，冒泡上去，返回它，无论需要什么。
关于您发布的代码，我认为它不适合快速修复。它应该使用哪种算法？mid是用来干什么的？我认为一旦您知道要使用哪种算法，并找出包含比较的代码行，您将能够快速看到并编写解决方案。
通常，在这些情况下，先专注于获得一个可行的解决方案，然后再考虑效率会有所帮助。第一次遇到这样的问题时，我使用了选择排序。我建议首先尝试它，然后利用所获得的经验做一个归并排序，它的时间复杂度是O(n log n)。
1
这是一种类似Java的方式...
    Arrays.sort(arr,new Comparator<Integer>(){
      public int compare(Integer a,Integer b)
      {
        return (a % 4) - (b % 4);
      }
    });
这甚至不应该是那么低效的，如果整数存在于整数池中。http://www.devx.com/tips/Tip/42276 - Chris Dennett
1
我读过了，但实际上并没有帮助我。如果有人能帮我修复代码使其正常运行，我会非常感激。我已经卡在这个问题上好几个小时了。 - user372003
如果我们只是帮你修复代码，而你并不理解为什么它不能工作，那对你并没有帮助。 - VeeArr
我知道，但是当我有了修复后的代码，我会仔细检查为什么之前它不能工作。同时，解释一下为什么它不能工作会更有帮助。 - user372003
@user：你的代码不起作用是因为它是错误的。就这么简单。没有简单的解决办法。 - polygenelubricants
我需要一个解决方案来引导我。 - user372003
1
嘿，我有一个打印报告系统，目前的代码是这样的：System.out.println("Hell world")。请帮我修复它，以便我可以继续完成剩下的工作。 - OscarRyz
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接