将已排序数组快速就地分区为两个已排序的子数组

Question

编辑 - 我删除了所有不必要的上下文解释 - 太罗嗦,最终与问题无关.总而言之,我在构建平衡KD树的过程中对坐标数组进行了划分(请参阅维基百科文章,构造部分了解更多.我实际上有n个项目的k个并行数组,每个项目都必须通过相同的比较进行分区)

这不是家庭作业 - 我写的问题就是确保传达所有的细微差别.

给定排序数组:

 int[] ints =  { 0, 1, 2, 3, 4, 5, 6 };
 //this one is important - my current solution fails on this
 int[] ints2 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

请注意,由于同事要求澄清,所有关于这些阵列的保证element[n]都将小于或等于element[n+1].

在这些成功的操作将它们分离为两个子阵列L和R(如下所示):

/*ints == */  { 1, 3, 5, 0, 2, 4, 6 }
              /*|> L <|  |>   R  <|*/

/*ints2 == */ { 1, 3, 5, 7, 9, 0, 2, 4, 6, 8 }
              /*|>    L    <|  |>    R    <|*/

L包含奇数的整数并R包含那些偶数的整数,同时保留这些子数组中这些元素的原始排序顺序.

该功能将非常不诉诸重新排序的元素(一个漫长的排序操作已经被提前执行),也不会使用临时数组.我相信这意味着我正在寻找O(N)复杂度和O(1)内存.

该函数可以提供每个子阵列的开始和结束元素 - 即,调用者可以预先知道有多少项将落在左/右侧(可能通过预先扫描阵列以获得奇数/偶数). 在现实中编辑它就像一个数组一样开始; 因此,没有这些值可以工作的解决方案是好的,因为否则如果需要初始传递,完整的解决方案在现实中最多只能是O(2n)复杂度.

这是我目前的尝试 - 我已经更新了它,并根据原始帖子中的内容对其进行了评论.

public void DivideSubArray(int[] array, int leftStart, int leftCount, 
  int rightStart, int rightCount)
{
  int currentLeft = leftStart, currentRight = rightStart;
  int leftCounter = leftCount;
  int temp;
  int readahead;
  while (leftCounter != 0) {
    if ((array[currentLeft] % 2) == 0)
    {
      //remember the element we swap out
      temp = array[currentRight];
      //Set as next item on the right. We know this is the next lowest-sorted 
      //right-hand item because we are iterating through an already-sorted array
      array[currentRight++] = array[currentLeft];
      // * read ahead to see if there are any further elements to be placed
      // * on the left - move them back one by one till there are no more.
      readahead = currentLeft + 1;
      while ((array[readahead] % 2) != 0)
      {
        array[currentLeft++] = array[readahead++];
        leftCounter--;
      }
      //Now write the swapped-out item in, but don't increment our currentLeft.  
      //The next loop will check if the item is in the correct place.
      array[currentLeft] = temp;
    }
    else //this item is already in the correct place
    {
      currentLeft++;
      leftCounter--;
    }
  }
}

如下调用:

int numOdd = ints.Count(i => (i % 2) == 1);
DivideSubArray(ints, 0, numOdd, numOdd, ints.Length - numOdd);

它为ints(和许多其他数组)生成预期的数组,但不是ints2:

{ 1, 5, 3, 7, 9, 0, 2, 6, 4, 8 }

所以它正确分区 - 但交换3,5和6,4.我理解为什么:因为在第一个循环5被交换到左边,然后2传播,因为算法说这5是奇数并应该保持.我写了一个决策树,它会修复它,但是跟着它几个循环,它推断出解决方案是递归的.

我很难看到如何在子阵列中运行更多排序操作或创建临时列表/数组作为工作空间来解决这个问题.当然,但是,一种类型可能会增加复杂性但保持内存要求; 如果它是最快的解决方案,那么使用它是有意义的.

您可以在我的回答中看到我当前最快(在运行时间)和最佳内存解决方案.作为衡量标准 - 上述尝试不仅会产生不正确的结果,而且还需要3倍于我答案中的代码.

我觉得必须有一个简单的方法来利用一个"备用"变量来交换项目 - 我只是看不到它 - 我希望SO集体大脑会:)

当然,如果答案是'不'那么就是这样吧.

Answer 1

我设法找到了一个不使用临时数组的解决方案 - 对于大 N 来说速度非常慢；我什至不打算发布它的代码，这太糟糕了！

编辑-这是对我原来的解决方案的改进。从技术上讲，复杂度为 O(2n)（因为 List.CopyTo 方法使用 Array.Copy，根据框架文档，复杂度为 O(n)），内存为 O(n)。

是的，该解决方案只是简单地获取数组并即时进行分割，而不是依赖于提前了解奇数/偶数分割。这意味着（当回归到我的实际代码时）不需要初始传递 - 所以这是更好的选择。

这个解决方案很简单：它扫描数组，将赔率移回到数组的开头（或者如果它们已经位于正确的位置，则将它们保留在原处）并将偶数添加到列表中。循环完成后，列表将复制到数组的其余部分。它以牺牲内存为代价满足了我的复杂性要求 - 最坏的情况是 O(n) - 并且对我已经使用的代码来说是一个很大的改进（它比两个列表解决方案快两倍）。它也不需要初始传递来获得奇数/偶数分割。

public void DivideSubArray(int[] array)
{       
    int currentOdd=0;
    List<int> even = new List<int>(array.Length / 2);
    for (int i = 0; i < array.Length; i++)
    {
        if ((array[i] % 2) != 0)
        {
            even.Add(array[i]);
        }
        else
        {
            if (currentOdd != i)
                array[currentOdd++] = array[i];
            else
                currentOdd++;
        }
    }
    even.CopyTo(array, currentOdd);
}

请注意列表的初始容量 - 正如 Mooing Duck 在下面的评论中提到的那样，我可以通过利用一些概率并选择稍高的值（假设平均观察到大致均匀的分割）来进一步改进。

也就是说，该算法在偶数分割时执行速度最慢 - 如果有更多奇数项，那么它只是一堆交换。如果有更多的事件，是的，Add需要更多的操作，但这只是列表的大小调整，这会降低性能。

我的最后一次尝试是看看我是否能够实现 izomorphius 所建议的目标 - 以正确的顺序构建赔率，并以相反的顺序或任何顺序构建赔率，而无需额外的数组。如果可能的话，那么该解决方案将是 O(1) 内存，但 O(n + (排序复杂性)) - 如果它的性能在实践中甚至是上述解决方案速度的一半，我可能会选择它。