使用flag-sort在Java中对数组进行排序

Question

用Java编写静态方法:

public static void sortByFour (int[] arr)

作为参数接收一个充满非负数(零或正数)的数组,并按以下方式对数组进行排序:

• 在数组的开头,将显示四个没有余数的所有数字.
• 在它们之后,将出现数组中所有以4为余数的数字.
• 在它们之后,将出现数组中所有以4为余数的数字.
• 在数组的末尾,将显示所有其余数字(除以4而其余为3的数字).

(每组中数字的顺序无关紧要)

使用flag-sort,该方法必须尽可能高效.空间复杂度必须为O(1),时间复杂度必须为O(N)或更小.

注意:请勿使用额外的阵列.

我读到了标志排序,但我不知道如何用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;
}

我不确定它是否正确......

Answer 1

算法

您需要实现的排序算法(一个相当模糊的)称为"标记排序".以下是维基百科对此所说的话:

基数排序的高效,就地变体,可将项目分配到数百个桶中.第一步计算每个桶中的项目数,第二步计算每个桶在阵列中的起始位置.最后一步循环将项目置换为适当的桶.由于存储桶在阵列中是有序的,因此没有收集步骤.

在你的情况下:

• 有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上的源代码和输出