logo标签列表

将重复项移动到数组末尾的排序方法？

javaalgorithmsortingduplicates
7
这是我朋友编程课上的一个问题。 问:如何对int数组进行排序，使得所有重复元素出现在数组的末尾？
例如，给定输入：
{5, 2, 7, 6, 1, 1, 5, 6, 2}

输出结果将是：
{1, 2, 5, 6, 7, 1, 2, 5, 6}

请注意，数字已排序，重复的数字在数组中的最大值7之后。
这必须在不使用任何Java库包/工具的情况下实现。
我建议首先使用插入或冒泡排序对数组进行排序，然后遍历数组，执行以下操作：
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;
        }
    }
}

我后来自己尝试了一下（这也是上面代码的来源）- 当我尝试时，我认为可以用更少的代码实现，更加高效。可能我给出了错误的建议。
有什么想法吗？
1
@Nick Johnson：记住，他正在学习编程。 - ring bearer
那么我的问题是和教他的人有关 - 把冒泡排序教授为“不仅仅是一种天真的算法，实际上并不工作”的例子之外的任何东西都是不负责任的。 :) - Nick Johnson
4个回答
8
根据您问题的参数，有很多解决方法。如果不允许使用O(n)的外部存储器，则一种选择是使用标准排序算法在O(n log n)时间内对数组进行原地排序，然后再运行第二遍将重复项移动到末尾（如您所建议的）。您上面发布的代码需要O(n^2)的时间，但我认为可以使用稍微复杂的算法在O(n log n)时间内完成此步骤。这个想法分为两个步骤。第一步，在O(n log n)时间内，您将所有非重复元素按排序顺序放在前面，并将所有重复元素按非排序顺序放在后面。完成后，您再使用第一步中的排序算法在O(n log n)时间内对数组后半部分进行排序。
我不打算深入讲解如何对数组进行排序的代码。虽然我非常喜欢排序，但是有很多其他好的资源可以教你如何原地排序数组，所以在这里深入讲解并不是一个好的时间/空间利用方式。如果有帮助的话，这里提供了Java实现 heapsort，quicksort 和 smoothsort 的链接，它们都能在 O(n log n) 时间内运行。Heapsort 和 Smoothsort 仅使用 O(1) 外部内存，而 Quicksort 在最坏情况下可以使用 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”指向的值，并将写指针向前移动，然后将读指针移动到下一个唯一值：

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）（例如smoothsort或heapsort）或O（log n）（例如quicksort）。

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

 +----------------+----------------+----------------+
 | 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(n2)，但概率极低。

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

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

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

然而，如果你被允许使用外部空间，并且要排序的数组很小并且包含小整数，你可以通过使用修改后的计数排序来修改上面的方法。只需用足够大的数组替换BST，使原始数组中的每个整数都成为一个键即可。这将将运行时间降至O(n + k)，内存使用量为O(k)，其中k是数组中的最大元素。

希望这能有所帮助！

2
一种修改后的归并排序可以解决这个问题：在最后一次合并时，跟踪您推送到结果数组前面的最后一个数字，如果下一个数字中最低的数字相同，则将其添加到末尾而不是前面。
我不确定这会怎么样运行。这不会破坏归并排序中必需的递归假设，即两个子数组返回已排序吗？ - templatetypedef
我是指在最后合并排序时，在递归调用中，当原始调用者获得2个已排序的子数组时，它会将重复项添加到末尾而不是前面。因此，这是普通的归并排序。 - ratchet freak
1
欢迎来到数据结构和算法的世界。你说得没错，你可以更快地排序。你也可以用十几种不同的方法来做。博士学位就是为了研究这些东西的 :)
这里有一个链接，你可以看到一个优化过的冒泡排序。
你可能还想查看大O符号。
祝你好运，玩得开心！
1
使用快速排序算法对数组进行排序。在实现排序时，您可以通过将所有重复元素添加到单独的重复元素数组中稍微修改它。完成后，只需将重复元素数组附加到已排序数组的末尾即可。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接