相关疑难解决方法(0)

我知道问题不是太具体.

我想要的只是告诉我如何将普通合并排序转换为就地合并排序(或具有恒定额外空间开销的合并排序).

我所能找到的(网上)是"太复杂"或"超出本文范围"的网页.

唯一已知的就地合并方式(没有任何额外空间)太复杂,无法简化为实际程序.(取自这里)

即使它太复杂,如何使合并排序到位的基本概念是什么？

我正在实现几个数据结构和一个我要使用的原语如下:我有一个内存块A [N](它有一个可变长度,但我的示例需要100)并且在这个块中,有一个较小的部分C长度为K(比方说30),我想移动而不使用任何额外的内存.

另外的困难是,A"包裹",即C可以从A [80]开始,然后C的前20个元素是元素A [80..100],最后10个元素是元素A [ 0..10].此外,目标范围还可以以任何可能的方式"包裹"并与C重叠.另外,我不想使用超过一定数量的额外内存,一切都应该到位.此外,既不在目标范围内也不在源范围内的A部分可能包含重要的内容,因此也不能使用.所以一个案例如下:

A看起来像这样:

| 456789ABCDEF0123456789AB | ----- | 0123 |

应该转变为:

| 89AB | ----- | 0123456789ABCDEF01234567 |

只是将它委托给一个库或者使用库中的另一个数据结构不是一个选项,我想自己理解这个问题.在第一眼看来,我认为它可能不是微不足道的,但是一旦你区分了一些案例,它就会变得清晰,但现在我遇到了严重的麻烦.当然,如果它们不重叠或不包装,则存在微不足道的情况,但至少如果两者同时发生,则会变得混乱.您可以从一个空闲位置开始移动属于那里的部件,然后在其他地方创建另一个自由部件,并且很难跟踪您可以使用哪些部件.

也许我完全错过了一些东西,但即使是我的特殊情况,如果目标范围没有换行也有近100行(虽然它的一半是断言和注释)我可以更新它以便它也处理一般情况下一些额外的索引计算,但如果有人有一个优雅而简短的解决方案,我将不胜感激.直觉上我认为这应该是微不足道的,但我还没有看到最好的解决方案.

注意:有趣的情况当然是,如果C几乎和A一样大.如果| C | <N/2,这是微不足道的.

编辑:使用超过一定数量的额外标志/索引计数作为额外的内存,我想尽可能避免这种情况.

编辑:有些人想看我的代码.我的问题相当抽象,所以我不想发布它,但也许有人会看到如何改进它.这很糟糕,它只适用于目标从头开始(但是,可以很容易地改变)并且非常长的情况,但是它在O(n)中没有额外的存储器的情况下完成工作.

#include <stddef.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>

void move_part(int* A, size_t N, size_t target, size_t source, size_t size, int show_steps)
{
  assert(source + size <= N);
  assert(target + size <= N);
  if (show_steps) {
    printf("Moving size %d from %d to %d.\n", size, source, target);
  }
  memmove(A + target, …

给定一个具有正整数和负整数的数组,将所有奇数索引元素移动到左侧,甚至将索引元素移动到右侧.

问题的难点在于在维持秩序的同时就地完成.

例如

7, 5, 6, 3, 8, 4, 2, 1

输出应该是:

5, 3, 4, 1, 7, 6, 8, 2

如果顺序无关紧要,我们可以使用快速排序的partition()算法.

如何在O(N)中完成？