java - 按 4 的余数对数组进行排序

Question

我有一个练习，我必须按以下方式对数组进行排序:

1. 将 4 除以无余数的数字排在数组的第一个(例如 4,8,12,16)。
2. 4 除以 1 的余数将是数组中的第二个数 (1,5,9)。
3. 4 除以 2 的余数将是数组中的第三个数 (2,6,10)。
4. 将 4 除以 3 的余数的数字将排在数组的最后。

例如下面的数组:

int []a={1,7,3,2,4,1,8,14}

将是:

4   8   1   1   2   14  3   7   

组内的顺序无关紧要。

我找到了一个解决方案，它的时间复杂度为 O(n)，空间复杂度为 O(1)。

然而，它很丑，在数组上移动了3次。我想要一个更优雅的解决方案。

这是我的代码:

    int ptr=a.length-1; int temp=0, i=0;
    while (i<ptr){
        //move 3 remained to the end
        if (a[i] % 4==3){
            temp=a[ptr];
            a[ptr]=a[i];
            a[i]=temp;
            ptr--;
        }
        else
            i++;
    }
    i=0;
    while (i<ptr){
        if (a[i]%4==2)
        {
            temp=a[ptr];
            a[ptr]=a[i];
            a[i]=temp;
            ptr--;
        }
        else
            i++;
    }
    i=0;
    while (i<ptr){
        if (a[i]%4==1)
        {
            temp=a[ptr];
            a[ptr]=a[i];
            a[i]=temp;
            ptr--;
        }
        else
            i++;
    }

重要须知:

• 我不希望时间复杂度比 O(n) 差，空间复杂度比 O(1) 差。

Answer 1

因为 O(3 * N) 是 O(N)，你只需要遍历数组 3 次:

1. 将元素 e % 4 == 0 移到前面，沿途交换元素；
2. 将元素 e % 4 == 1 移到前面，沿途交换元素；
3. 将元素 e % 4 == 2 移到前面，沿途交换元素；

e % 4 == 3 的元素将在这之后结束。

例子:

public static void main(String args[]) {
    int[] a = { 1, 7, 3, 2, 4, 1, 8, 14 , 9};
    int current = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = current; j < a.length; j++) {
            if (a[j] % 4 == i) {
                int b = a[j];
                a[j] = a[current];
                a[current] = b;
                current++;
            }
        }
    }
    System.out.println(Arrays.toString(a));
}