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

Answer 2

您可以使用更多的内存。这是不正确的，但我还是会说。

int modulusLength = 4;
List<Integer> array[] = new List<Integer>[modulusLength];
for(int i = 0; i < modulusLength; i++)
    array[i] = new ArrayList<Integer>;

for(int i = 0 ; i < a.length; i++)
    array[a[i]%modulusLength].put(a[i]);

int counter = 0;
for(int i = 0 ; i < array.length; i++)
    for(int j = 0; j < array[i].size; j++)
    {
        a[counter] = array[i].get(j);
        counter++;
    }

可怕又可怕，但写起来很有趣。它有效:)

Answer 3

只需使用比较器并使用非常有效的内部排序算法。

Arrays.sort(a, new Comparator() {
 public int compare(int a, int b) {
  if(a%4 == b%4) {
   if(a < b) return -1;
   if(a > b) return 1;
   return 0;
  } else {
   if(a%4 < b%4) return -1;
   if(a%4 > b%4) return 1;
   return 0;
  }
 }
});