在将重复项移动到末尾的同时对数组进行排序？

Question

这是我朋友的编程课上的一个问题。

问如何对 int 数组进行排序，然后排列它们以使所有重复元素出现在数组末尾？

例如，给定输入 输出

{5, 2, 7, 6, 1, 1, 5, 6, 2}

将是

{1, 2, 5, 6, 7, 1, 2, 5, 6}

请注意，数字已排序并且重复的数字在 7 之后，这是数组中的最大值。

这必须不使用任何 Java 库包/utils 来实现。

我建议首先使用插入或冒泡排序对数组进行排序，然后遍历数组，执行类似以下操作：

for (int i = 0; i < nums.length - 2; i++) {
    for (int j = i + 1; j < nums.length; j++) {
        //current and next are same, move elements up
        //and place the next number at the end.
        if (nums[i] == nums[j]) {
            int temp = nums[j];
            for (int k = j; k < nums.length - 1; k++) {
                nums[k] = nums[k + 1];
            }
            nums[nums.length - 1] = temp;
            break;
        }
    }
}

我稍后自己尝试了这个（这就是上面的代码）-当我尝试这个时，我认为这个可以通过使用更少的代码来实现，效率更高。也许我给出了错误的建议。

有什么想法吗？

Answer 1

根据问题的参数，有多种方法可以解决这个问题。

如果不允许使用 O(n) 外部存储器，那么一种选择是使用标准排序算法在 O(n log n) 时间内对数组进行就地排序，然后对它运行第二遍以将重复项移动到末尾（正如您所建议的那样）。您上面发布的代码需要 O(n²) 时间，但我认为使用稍微复杂的算法可以在 O(n log n) 时间内完成此步骤。这个想法分两步进行。第一步，在 O(n log n) 时间内将所有非重复元素按排序顺序放在前面，并将所有重复元素按非排序顺序放在后面。完成此操作后，您可以使用第一步中的排序算法在 O(n log n) 时间内对数组的后半部分进行排序。

我不会进入代码来对数组进行排序。我真的很喜欢排序，但是有很多其他关于如何就地对数组进行排序的好资源，所以我不能很好地利用我在这里的时间/空间来研究它们。如果有帮助，这里是 堆排序，quicksort 和 smoothsort，所有这些都运行在 O(n log n) 时间内。堆排序和平滑排序仅使用 O(1) 外部存储器，而快速排序在最坏的情况下可以使用 O(n)（尽管好的实现可以使用可爱的技巧将其限制为 O(log n)）。

有趣的代码是将所有非重复元素带到范围前面的逻辑。直观地说，该代码通过存储两个指针来工作——一个读指针和一个写指针。读指针指向下一个要读取的元素，而写指针指向下一个唯一元素应放置的位置。例如，给定这个数组：

1 1 1 1 2 2 3 4 5 5

我们从最初指向 1 的读指针和写指针开始：

write  v
       1 1 1 1 2 2 3 4 5 5
read   ^

接下来，我们将读指针向前跳过到下一个不是 1 的元素。这会找到 2：

write  v
       1 1 1 1 2 2 3 4 5 5
read           ^

然后，我们将写指针指向下一个位置：

write    v
       1 1 1 1 2 2 3 4 5 5
read           ^

现在，我们将 2 交换到写指针所保存的位置：

write    v
       1 2 1 1 1 2 3 4 5 5
read           ^

将读指针前进到下一个不是 2 的值：

write    v
       1 2 1 1 1 2 3 4 5 5
read               ^

然后前进写指针：

write      v
       1 2 1 1 1 2 3 4 5 5
read               ^

再次，我们交换 'read 指向的值' 和 '写' 并移动向前写指针，然后将读指针移动到下一个唯一值：

write        v
       1 2 3 1 1 2 1 4 5 5
read                 ^

再次产生

write          v
       1 2 3 4 1 2 1 1 5 5
read                   ^

并且最终迭代给出

write            v
       1 2 3 4 5 2 1 1 1 5
read                      ^

如果我们现在从写指针排序到读指针，我们得到

write            v
       1 2 3 4 5 1 1 1 2 5
read                      ^

宾果！我们已经找到了我们正在寻找的答案。

在（未经测试的，抱歉...）Java 代码中，此修复步骤可能如下所示：

int read = 0;
int write = 0;

while (read < array.length) {
     /* Swap the values pointed at by read and write. */
     int temp = array[write];
     array[write] = array[read];
     array[read] = temp;

     /* Advance the read pointer forward to the next unique value.  Since we
      * moved the unique value to the write location, we compare values
      * against array[write] instead of array[read].
      */
     while (read < array.length && array[write] == array[read])
         ++ read;

     /* Advance the write pointer. */
     ++ write;
}

该算法运行时间为 O(n)，这导致该问题的整体算法为 O(n log n)。由于重新排序步骤使用 O(1) 内存，因此总体内存使用量将为 O(1)（对于平滑排序或堆排序等）或 O(log n)（对于快速排序等）。

编辑：在与朋友讨论后，我认为基于快速排序的修改，有一个更优雅的解决方案。通常，当您运行快速排序时，最终会将数组划分为三个区域：

 +----------------+----------------+----------------+
 | values < pivot | values = pivot | values > pivot |
 +----------------+----------------+----------------+

然后递归对第一个和最后一个区域进行排序，以将它们按排序顺序排列。但是，我们可以针对我们的问题版本进行修改。我们需要旋转算法作为原语，该算法获取数组中两个相邻的值块并在 O(n) 时间内交换它们。它不会更改这些块中元素的相对顺序。例如，我们可以使用旋转将数组转换

1 2 3 4 5 6 7 8

为

3 4 5 6 7 8 1 2

O(n) 时间。

快速排序的修改版本可以使用 Bentley-McIlroy 三路分区算法（描述为 此处）使用 O(1) 额外空间，将数组元素重新排列为如上所示的配置。接下来，我们应用旋转来重新排序元素，使它们看起来像这样：

 +----------------+----------------+----------------+
 | values < pivot | values > pivot | values = pivot |
 +----------------+----------------+----------------+

接下来，我们执行交换，以便将主元元素的一个副本移动到至少与主元一样大的元素集中。这可能有额外的枢轴副本。然后我们递归地将排序算法应用于 <<和>范围。当我们这样做时，生成的数组将如下所示：

 +---------+-------------+---------+-------------+---------+
 | < pivot | dup < pivot | > pivot | dup > pivot | = pivot |
 +---------+-------------+---------+-------------+---------+

然后我们对范围应用两次旋转以将其放入最终顺序。首先，将小于主元的重复值与大于主元的值进行旋转。此时

 +---------+---------+-------------+-------------+---------+
 | < pivot | > pivot | dup < pivot | dup > pivot | = pivot |
 +---------+---------+-------------+-------------+---------+

，第一个范围是按升序排列的唯一元素：

 +---------------------+-------------+-------------+---------+
 | sorted unique elems | dup < pivot | dup > pivot | = pivot |
 +---------------------+-------------+-------------+---------+

最后，对大于枢轴的重复元素和等于枢轴的元素进行最后一次旋转，以产生以下结果：

 +---------------------+-------------+---------+-------------+
 | sorted unique elems | dup < pivot | = pivot | dup > pivot |
 +---------------------+-------------+---------+-------------+

请注意，最后三个块只是排序后的重复值：

 +---------------------+-------------------------------------+
 | sorted unique elems |      sorted duplicate elements      |
 +---------------------+-------------------------------------+

瞧！我们已经按照我们想要的顺序得到了一切。使用与普通快速排序相同的分析，加上我们只在每个级别执行 O(n) 工作（三个额外旋转），在最好的情况下，这会达到 O(n log n)内存使用量为 O(log n)。在 O(log n) 内存的最坏情况下，它仍然是 O(n²)，但发生这种情况的概率极低。

如果允许使用 O(n) 内存，一种选择是从存储键/值对的所有元素中构建平衡二叉搜索树，其中每个键都是数组和值是它出现的次数。然后，您可以按如下格式对数组进行排序：

1. 对于数组中的每个元素：
   • 如果该元素已存在于 BST 中，则增加其计数。
   • 否则，向 BST 添加一个新节点，其中该元素的计数为 1。
2. 对 BST 进行中序遍历。当遇到一个节点时，输出它的key。
3. 对 BST 进行第二次有序遍历。当遇到一个节点时，如果它的count大于1，则输出该节点的n-1个副本，其中n是它出现的次数。

该算法的运行时间为 O(n log n)，但从头开始编写 BST 是相当棘手的。它还需要外部空间，我不确定你是否可以这样做。

但是，如果允许外部空间并且要排序的数组很小并且包含小整数，则可以使用修改后的 计数排序。只需将 BST 替换为一个足够大的数组，使原始数组中的每个整数都可以作为键。这将运行时间减少到 O(n + k)，内存使用量为 O(k)，其中 k 是数组中最大的元素。

希望这有帮助！

Answer 2

修改后的合并排序可以解决这个问题：在最后一次合并过程中，跟踪您在结果数组前面推送的最后一个数字，如果下一个数字的最低值相等，则添加到末尾而不是前面

Answer 3

欢迎来到数据结构和算法的世界。你说得对，你可以更快地排序。您还可以通过十几种不同的方式来做到这一点。 PHD 都花在了这些东西上:)

这是一个链接，您可以在其中看到优化的 冒泡排序

您可能还想查看大 O 表示法

玩得开心，祝你好运！

Answer 4

使用快速排序对数组进行排序。实现排序时，您可以通过将所有重复项添加到单独的重复数组中来稍微修改它。完成后，只需将重复数组附加到已排序数组的末尾即可。