Java 中的数组排序

Question

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

我如何修复或重写我的代码以便它能正常工作？

Answer 1

我将在伪代码中为您执行此操作，但在代码中执行此操作将为您提供答案，这是家庭作业，因此您可以完成自己的工作。 =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)
    }
}

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

Answer 2

您可以这样解决这个问题：

1. 选择您想要使用的排序算法。看起来您正在尝试编程 Quicksort，但您也可以使用 冒泡排序。
2. 识别算法中比较输入数组中的两个值的点。例如，在维基百科文章中的冒泡排序伪代码中，唯一的比较是行 if A[i] > A[i+1] 然后...。
3. 找出一种比较两个数字的方法，以便除以 4 时余数为 0 的数字 s 被认为小于除以 4 时余数为 1 的数字 t。替换算法与比较器 计算（例如 if myIsGreater(A[i], A[i+1]) then...）。

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

Answer 3

我会重申丹尼尔所说的话：你可以选择排序算法。如果需要的话，请使用迄今为止在课程中介绍过的最有效的方法。但是，当您在算法中比较两个项目时，请比较它们的值 mod 4。所以类似于 if A[i] >如果 A[i] % 4 > 则 A[j] 变为 如果 A[j] % 4 。然后，您继续执行算法指定的对该数组元素执行的操作。交换、冒泡、退货，无论需要什么。

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

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

Answer 4

线性时间解决方案

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

• 您有 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]"
    }
}

一旦您完全理解了该算法，将其转换为使用数组（如果必须的话）就很简单了。

另请参见

• java.util.List; API - “有序集合”
  • add(E e) - “将指定元素附加到此列表的末尾”
  • addAll(...) - “将指定集合中的所有元素追加到此列表的末尾”
• Java 语言指南/for-each循环（1.5.0引入）

---

关于%的特别说明

数字非负的规定很重要，因为%不是数学定义的取模运算符；它是余数运算符。

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

参考文献

• JLS 15.17.3 余数运算符 %
• 维基百科/Modulo 操作

Answer 5

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

这应该有帮助从长远来看你是最好的。也挺好玩的！

Answer 6

这是一种 Java 式的方式......

    Arrays.sort(arr,new Comparator<Integer>(){
      public int compare(Integer a,Integer b)
      {
        return (a % 4) - (b % 4);
      }
    });