4

用Java写一个静态方法：

public static void sortByFour (int[] arr)

它接收一个充满非负数（零或正数）的数组作为参数，并按以下方式对数组进行排序：

  • 在数组的开头，所有能被四整除的数字都会出现。

  • 在它们之后，将出现数组中除以 4 余数为 1 的所有数字。

  • 在它们之后，将出现数组中除以 4 余数为 2 的所有数字。

  • 在数组的末尾，将出现所有其余的数字（除以 4 余数为 3 的数字）。

（每组中数字的顺序无关紧要。）

该方法必须尽可能有效。

以下是我写的，但不幸的是它不能很好地工作...... :(

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++;
    }
}

如何修复或重写我的代码以使其正常运行？

4

6 回答 6

2

线性时间解决方案

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

  • 您有 4 个存储桶，每个存储桶用于模 4 的数字的一致性类。
  • 扫描数组中的数字一次
    • 将每个数字放入正确的桶中
  • 然后构造输出数组
    • 首先放入桶 0 中的所有数字，然后放入桶 1 中的所有数字，然后放入桶 2，然后放入桶 3

因此，这对 中的数字进行排序O(N)，这是最佳的。这里的关键是，通过对数字模 4 进行排序，基本上只有 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"

参考

于 2010-06-08T07:39:16.257 回答
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)
    }
}

然后按各自的顺序连接四个桶以获得最终结果

于 2010-06-07T18:53:42.817 回答
2

我将重申丹尼尔所说的：您可以选择排序算法。如果需要，请使用迄今为止您在课堂上学习过的最有效的一种。但是，当您在算法中比较两个项目时，请改为比较它们的值 mod 4。所以像if A[i] > A[j]变成if A[i] % 4 > if A[j] % 4. 然后，您继续执行算法指定您对该数组元素执行的任何操作。交换它，冒泡它，退回它，无论需要什么。

关于您发布的代码，我认为它不适合快速修复。它应该使用哪种算法？有什么mid用？我认为一旦你知道你打算使用哪种算法，并弄清楚哪一行代码包含比较，你将能够快速查看并编写解决方案。

一般来说，对于这些事情，如果您在担心效率之前专注于获得可行的解决方案，它会有所帮助。我第一次不得不做这样的问题时使用了选择排序。我建议先尝试一下，然后使用获得的经验进行合并排序，即 O(n log n)。

于 2010-06-08T07:20:39.413 回答
2

您可以这样解决问题：

  1. 选择您希望使用的排序算法。看起来您正在尝试编写 Quicksort，但您也可以使用Bubble Sort。
  2. 识别算法的点，其中输入数组中的两个值正在被比较。例如，在 Wikipedia 文章中冒泡排序的伪代码中，唯一的比较是if A[i] > A[i+1] then....
  3. 找出一种比较两个数字的方法，这样当除以 4 时余数为 0 的数字s被认为小于当除以 4 时余数为 1 的数字t 。用比较器计算替换算法的比较操作（例如if myIsGreater(A[i], A[i+1]) then...）。

对于第 3 步，通过考虑模运算符，您肯定走在正确的轨道上。

于 2010-06-07T22:11:36.593 回答
1

阅读本页。http://en.wikipedia.org/wiki/Sorting_algorithm#Summaries_of_popular_sorting_algorithms

从长远来看，这应该对您有最大的帮助。它也很有趣！

于 2010-06-07T18:26:42.317 回答
1

这是一种Java-ish方式...

    Arrays.sort(arr,new Comparator<Integer>(){
      public int compare(Integer a,Integer b)
      {
        return (a % 4) - (b % 4);
      }
    });
于 2010-06-19T16:54:18.197 回答