java - 使用 4 个选项对数组进行排序的算法

Question

我的任务是对填充有(非负)整数的数组进行排序。

应该对它们进行排序，以便输出按以下顺序排列:

• 余数除以4为0的数
• 除以 4 的余数为 1 的数
• 除以 4 的余数为 2 的数
• 余数除以 4 为 3

我尝试编写一个应该在 O(n) 下运行的简单算法(任务是高效地编写代码)。

但我认为这是一团糟，一些情况不起作用(例如，当我尝试一个数组时，前几个数字的余数为 3)。

关于如何修复它或更好的方法有什么建议吗？

public static void sortByFour(int[] arr)
{
    int zeroR = -1, oneR = 0, twoR = arr.length-1, threeR = arr.length;

    do
    {
        if (arr[oneR]%4==1)
         oneR++;
        else if (arr[oneR]%4==0)
        {
            zeroR++;
            int temp = arr[oneR];
            arr[oneR] = arr[zeroR];
            arr[zeroR] = temp;
            oneR++;
        }
        else if (arr[oneR]%4==2)
        {
            twoR--;
            int temp = arr[oneR];
            arr[oneR] = arr[twoR];
            arr[twoR] = temp;
        }
        else if (arr[oneR]%4==3)
        {
            threeR--;
            int temp = arr[oneR];
            arr[oneR] = arr[threeR];
            arr[threeR] = temp;
        }
    } while (oneR < threeR && oneR < twoR);
}

Answer 1

A bucket sort可以为你做的伎俩。请注意，您可以通过循环 4 次(每次提醒一次)来克服桶排序的 O(n) 额外空间因子，类似于(类似 java 的伪代码):

final int REMINDER = 4; //4 because you use %4
int curr = -1;
for (int r = 0; r < REMINDER ; r++) { 
   for (int i = curr + 1; i < arr.length; i++) { 
       if (arr[i] % REMINDER  == r) { 
          //swap elements:
          int temp = arr[i];;
          arr[i] = arr[++curr];
          arr[curr] = temp;
       }
   }
}

这个想法是“记住”你最后一次设置元素的位置，并迭代数组 4 次，并将具有匹配提醒的元素交换到所需位置(你记住的位置)。

复杂度仍然是 O(n)，额外的空间是 O(1)。

另一种方法是 O(n)(但更好的常数)时间和 O(n) 空间是使用经典的桶排序，单次存储根据所需的提醒，4 个不同列表中的所有元素，并在第 2 遍中 - 在这 4 个列表中，根据所需的顺序用元素填充原始数组。