使用flag-sort在Java中对数组进行排序
用Java编写静态方法：
public static void sortByFour (int[] arr) 作为参数接收一个充满非负数（零或正数）的数组，并按以下方式对数组进行排序：
- 在数组的开头，将显示四个没有余数的所有数字。
- 在它们之后，将出现数组中所有以4为余数的数字。
- 在它们之后，将出现数组中所有以4为余数的数字。
- 在数组的末尾，将显示所有其余数字（除以4而其余为3的数字）。
（每组中数字的顺序无关紧要）
使用flag-sort，该方法必须尽可能高效。 空间复杂度必须为O（1） ，时间复杂度必须为O（N）或更小。
注意：请勿使用额外的arrays。
我读到了关于标志排序但我不知道如何用Java编写它的代码。 有人可以帮帮我吗？
根据我读到的内容，有必要在每个桶的数组中找到起始索引和结束索引。 那是对的吗？ 为此，有必要计算数组中有多少数除以4，余数为0,1,2和3。
嗯…
public static void sortByFour(int[] arr) { int count1 = 0, count2 = 0, count3 = 0, count4 = 0; int startB1, startB2, startB3, startB4; for (int i = 0; i < arr.length; i++) { if (arr[i] % 4 == 0) count1++; if (arr[i] % 4 == 1) count2++; if (arr[i] % 4 == 2) count3++; if (arr[i] % 4 == 3) count4++; } startB1 = 0; startB2 = startB1 + count1; startB3 = startB2 + count2; startB4 = startB3 + count3; for (int i = startB1; i < arr.length; i++) { if (arr[i] % 4 == 0) { swap(arr[i], arr[startB1]); startB1++; } } for (int i = startB2; i < arr.length; i++) { if (arr[i] % 4 == 1) { swap(arr[i], arr[startB2]); startB2++; } } for (int i = startB3; i < arr.length; i++) { if (arr[i] % 4 == 2) { swap(arr[i], arr[startB3]); startB3++; } } } public static void swap(int a, int b) { int temp = a; a = b; b = temp; }
我不确定它是否正确……
算法
您需要实现的排序算法（一个相当模糊的）称为“标记排序”。 以下是维基百科对此的评价：
基数排序的高效，就地变体，可将项目分配到
数百个桶中。 第一步计算每个桶中的项目数，第二步计算每个桶在arrays中的起始位置。 最后一步循环将项目置换到适当的桶。 由于存储桶在arrays中是有序的，因此没有收集步骤。
在你的情况下：
- 有4个桶
- 将有3个步骤（所以不，它不会是一个单循环解决方案）
- 你需要
O(1)辅助空间，最好作为数组，用于count[]等。 - 循环置换是棘手的部分，但前两个步骤是微不足道的
- （在这里你可以做你的部分并通过前两个步骤展示一些工作）
参考
- 维基百科/美国国旗排序
Java实现
这是我能做的最直接的算法实现; 它还有一些日志声明，因此您可以遵循该算法。 您可能实际上想暂时跳过此部分并检查下面的输出。
static void sort(int... arr) { final int M = 4; final int N = arr.length; int[] count = new int[M]; for (int num : arr) { count[num % M]++; } int[] start = new int[M]; for (int i = 1; i < M; i++) { start[i] = start[i-1] + count[i-1]; } for (int b = 0; b < M; b++) { while (count[b] > 0) { dump(arr); int origin = start[b]; int from = origin; int num = arr[from]; arr[from] = -1; do { System.out.printf("Picked up %d from [%d]%n", num, from); int to = start[num % M]++; count[num % M]--; System.out.printf("%d moves from [%d] to [%d]%n", num, from, to); int temp = arr[to]; arr[to] = num; num = temp; dump(arr); from = to; } while (from != origin); } } }
然后我们可以测试它如下：
static void dump(int[] arr) { System.out.println("Array is " + java.util.Arrays.toString(arr)); } public static void main(String[] args) { sort(3, 2, 5, 0, 6, 4, 8, 7, 1, 6); }
这打印：
Array is [3, 2, 5, 0, 6, 4, 8, 7, 1, 6] Picked up 3 from [0] 3 moves from [0] to [8] Array is [-1, 2, 5, 0, 6, 4, 8, 7, 3, 6] Picked up 1 from [8] 1 moves from [8] to [3] Array is [-1, 2, 5, 1, 6, 4, 8, 7, 3, 6] Picked up 0 from [3] 0 moves from [3] to [0] Array is [0, 2, 5, 1, 6, 4, 8, 7, 3, 6] Array is [0, 2, 5, 1, 6, 4, 8, 7, 3, 6] Picked up 2 from [1] 2 moves from [1] to [5] Array is [0, -1, 5, 1, 6, 2, 8, 7, 3, 6] Picked up 4 from [5] 4 moves from [5] to [1] Array is [0, 4, 5, 1, 6, 2, 8, 7, 3, 6] Array is [0, 4, 5, 1, 6, 2, 8, 7, 3, 6] Picked up 5 from [2] 5 moves from [2] to [4] Array is [0, 4, -1, 1, 5, 2, 8, 7, 3, 6] Picked up 6 from [4] 6 moves from [4] to [6] Array is [0, 4, -1, 1, 5, 2, 6, 7, 3, 6] Picked up 8 from [6] 8 moves from [6] to [2] Array is [0, 4, 8, 1, 5, 2, 6, 7, 3, 6] Array is [0, 4, 8, 1, 5, 2, 6, 7, 3, 6] Picked up 7 from [7] 7 moves from [7] to [9] Array is [0, 4, 8, 1, 5, 2, 6, -1, 3, 7] Picked up 6 from [9] 6 moves from [9] to [7] Array is [0, 4, 8, 1, 5, 2, 6, 6, 3, 7]
如果你从了解输出（看看算法应该做什么），然后查看代码（看看它是如何完成的），它可以帮助你理解算法。
附件
- ideone.com上的源代码和输出