java - 在 Java 中对数组进行排序

Question

用Java写一个静态方法:

public static void sortByFour (int[] arr)

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

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

• 在它们之后会出现数组中除以 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)
    }
}

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