java - 使用标志排序在 Java 中对数组进行排序

Question

用Java写一个静态方法:

public static void sortByFour (int[] arr)

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

• 在数组的开头会出现除以四而无余数的所有数字。
• 在它们之后将出现数组中除以 4 余数为 1 的所有数字。
• 在它们之后会出现数组中除以 4 余数为 2 的所有数字。
• 在数组的最后会出现所有剩余的数(除以4余3的数)。

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

使用标志排序的方法必须尽可能高效。空间复杂度必须为 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

算法

您需要实现的排序算法(一个相当晦涩的算法)称为“标志排序”。以下是维基百科对此的描述:

An efficient, in-place variant of radix sort that distributes items into hundreds of buckets. 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[] 等。
• 循环排列是棘手的部分，但前两步很简单
  • (在这里您可以发挥自己的作用并通过执行前 2 个步骤来展示一些工作)

引用资料

• Wikipedia/American Flag Sort

---

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]

如果您先了解输出(了解算法应该做什么)，然后查看代码(了解它是如何完成的)，这可能有助于您理解算法。

附件

• source code and output on ideone.com