使用flag-sort在Java中对数组进行排序 [英] Sorting arrays in Java using the flag-sort
问题描述
用Java编写静态方法：
Write a static method in Java :
public static void sortByFour (int[] arr)
作为参数接收一个充满非负数（零或正数）的数组，并按以下方式对数组进行排序：
That receives as a paramater an array full of non-negative numbers (zero or positive) and sorts the array in the following way :
- 在数组的开头，将显示四个没有余数的所有数字。
- 在它们之后，将显示数组中所有以4为余数为1的数字。
- 在它们之后所有数字中的数字除以4而余数为2将出现。
- 在数组的末尾，所有剩余的数字（除以4除以3）将会出现。
- In the beginning of the array all the numbers that devide by four without a remainder will appear.
- After them all the numbers in the array that devide by 4 with a remainder of 1 will appear.
- After them all the numbers in the array that devide by 4 with a remainder of 2 will appear.
- In the end of the array all the rest numbers (those who divide by 4 with the remainder 3) will appear.
（每组中数字的顺序无关紧要）
(The order of the numbers in each group doesn't matter)
该方法必须尽可能高效使用旗帜排序。空间复杂度必须 O（1）且时间复杂度必须 O（N）或更低。
The method must be the most efficient as possible using the flag-sort. The space complexity must be O(1) and the time complexity must be O(N) or less.
注意：不要使用额外的数组。
NOTE: Do NOT use an extra array.
我读过有关标志排序但我不知道如何编写代码它在Java中。有人可以帮助我吗？
I read about the flag-sort but I don't know how to write the code of it in Java. Can someone please help me?
根据我的阅读，有必要在每个桶的数组中找到起始索引和结束索引。那是对的吗？为此，有必要计算数组中有多少数除以4，余数为0,1,2和3.
According to what I read, it is necessary to find the start index and end index in the array of each of the buckets. Is that correct? For this it's necessary to count how many numbers in the array divide by four with a remainder of 0, 1, 2, and 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;
}
我不确定它是否正确...
I am not sure it's correct though...
推荐答案
算法
你需要实现的排序算法是一个相当模糊的算法）称为旗帜排序。以下是维基百科对此所说的内容：
The algorithm
The sorting algorithm that you need to implement is (a rather obscure one) called the "flag sort". Here's what Wikipedia has to say about it:
基数排序的高效，就地变体，将项目分配到
数百个水桶。第一步计算每个桶中的项目数，第二步计算每个桶在阵列中的起始位置。最后一步循环将项目置换到适当的桶。由于数组中的存储桶是有序的，因此没有收集步骤。
An efficient, in-place variant of radix sort that distributes items into
hundreds ofbuckets. The first step counts the number of items in each bucket, and the second step computes where each bucket will start in the array. The last step cyclically permutes items to their proper bucket. Since the buckets are in order in the array, there is no collection step.
在您的情况下：
- 有4个桶
- 将有3个步骤（所以不，它不会是单个循环解决方案）
- 你需要
O（1）辅助空间，最好是数组，count []等等。 - 循环排列是棘手的部分，但前两步是微不足道的
- （这里是你可以做的事情，通过前两个步骤展示一些工作）
- There are 4 buckets
- There will be 3 steps (so no, it won't be a single loop solution)
- You need
O(1)auxiliary space, best as an array, forcount[], etc. - The cyclic permutation is the tricky part, but the first 2 steps is trivial
- (here's where you can do your part and show some work by doing the first 2 steps)
- Wikipedia/American Flag Sort
这是我能做的最直接的算法实现;它还有一些日志声明，因此您可以遵循该算法。您可能实际上想暂时跳过此部分并检查下面的输出。
Here's the most straightforward implementation of the algorithm that I could do; it also has some logging statement so you can follow the algorithm. You may actually want to skip this part for now and examine the ouput below.
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); } } }然后我们可以测试它为如下：
Then we can test it as follows:
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]如果你从理解输出（看看算法应该做什么），然后看，它可以帮助你理解算法在代码（看看它是如何完成的）。
It may help you understand the algorithm if you go from understanding the output (to see what the algorithm is supposed to do), and then looking at the code (to see how it's done).
- < aref =http://ideone.com/068AA =nofollow noreferrer> ideone.com上的源代码和输出
- source code and output on ideone.com
这篇关于使用flag-sort在Java中对数组进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
