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

我认为你可以通过以下方式让你的任务更容易：首先修改数组，首先奇数按升序写在数组的开头，然后最后以降序写偶数。对于示例 {0,1,...6} 这看起来像 {1,3,5,6,4,2,0}。完成此操作后，执行另一个线性传递以反转数组的第二部分（这非常简单明了）。

为什么我认为这应该更容易？好吧，因为第一步你应该做的事情就是常规的qsort算法会做的事情（使用一个有点奇怪的比较运算符）。你可以搜索互联网，看看qsort分区是如何完成的（例如，这里有一个例子）。我真的相信，如果您在这两个步骤中将问题分开，实施解决方案对您来说会更容易。另请注意，整体复杂性不会改变。

希望这对您有所帮助。

编辑：以下是我相信您可以完成我建议的第一部分的方式：

public void DivideSubArray(int[] array, int leftStart, 
              int leftCount, int rightStart, int rightCount)
{
    int currentRight = rightStart + rightCount - 1;
    int current = leftStart;
    while (current < currentRight) {
        if ((array[current] % 2) == 0)
        {
            int temp = array[current];
            array[current] = array[currentRight];
            array[currentRight] = temp;
            currentRight--;
        } else {
            current++;
        }
    } 
}

我没有提供代码来反转偶数部分，因为我相信这很简单，我还想强调这种方法简化了代码

我认为没有任何"直接"的方法可以在没有一端或另一端被打乱的情况下对列表进行分区，但仍然可以有一个线性时间常空间解决方案。 izomorphius提供的分割方法将导致末端的右侧以相反的顺序排列（在线性时间内易于纠正），而另一端以某种可预测的方式被打乱，来自右侧的元素以相反的顺序与来自左侧的元素混合在一起。 人们可以很容易地在恒定时间内识别给定的元素是否来自右侧（只需将其与左侧的最后一个项目进行比较），然后可以轻松地在线性时间中反转从右侧移动到左侧的元素的顺序。

一旦这样做了，就会留下一个分区问题，它与原始的非常相似，但只有大小的一半;唯一的区别是拆分标准是基于节点的值是大于还是小于"原始"最后一个元素，而不是它是偶数还是奇数。 因此，人们基本上可以将原始算法应用于较小的数据集。 由于可以提前确定拆分的哪一侧将有更多项目，因此可以放置拆分，以便剩余的一侧不超过原始大小的一半。 实际效果是，对大小为 2N 的数组进行分区所需的时间是分区大小为 N 的数组的 O（1） 倍。 由于单元素数组可以在恒定时间内完成（显然可以），这意味着可以使用恒定空间在线性时间内将由两个任意混合的排序数据运行组成的任意大小的数组分区为两个不相交的排序数据运行。

顺便说一下，虽然整数无关紧要，但重要的是要注意，上述算法依赖于比较两个元素的能力，并知道第一个元素属于第二个元素的左侧还是右侧。 因此，它不能用作稳定排序算法的基础。

我可以在这个线程上尝试一下吗？我可以看到你说的是C#。我不懂语言，但我认为这对任务并不重要。

问题描述中缺少一些内容 - 排序后的数组来自哪里。也许我应该发表评论要求澄清，但我决定去写一个涵盖我能想到的所有可能性的答案。希望这样答案将来能为更多的人服务。

基本上，任务原样将我们放在一个框中："您有一个数组，现在将其拆分到位"。但是，我想对这个数组的起源进行一些推理：

• 情况 1：数组从某处读取并在代码中排序（在内存中）。如果是这种情况，将偶数与赔率分开有一个优雅的解决方案，这不会产生任何开销：
  1. 确定赔率和偶数的数量（通过单次通过数组O(n)）。
  2. 确定数组中的最大和最小数字。让我们称它们为MAXM和MINM.这可以在第一遍完成，以确定偶数和奇数。
  3. 再次通过数组传递，将MAXM - MINM + 1添加到每个奇数。目标是确保所有奇数都大于偶数。这在时间上是线性的O(n)
  4. 使用kth_element算法拆分数组（基本上是快速排序关键分离的单次传递）。将偶数与奇数分开，利用您已经知道每个偶数的数量以及所有赔率都大于所有偶数的事实。该算法以线性时间O(n)运行，但遗憾的是我只有C++库实现（没有 C#）的参考。
  5. 遍历与奇数对应的所有数组插槽，并从每个数字中减去MAXM - MINM + 1，得到原始奇数。这在时间上也是线性的O(n)
  6. 最后分别对偶数和赔率的部分进行排序。这不会增加整体排序的复杂性，但您将 to 部分彼此分开。
• 情况 2：您读取已经从某个持久存储中排序的数组，例如硬盘上的文件，并提前知道赔率和偶数的数量。
  在这种情况下，您
  1. 只需要在数组中放置您输入的数字：一个是下一个跟随偶数，另一个是下一个跟随奇数。此解决方案应该是显而易见的，并且完全不会影响性能。
• 情况3：您从某些持久存储中读取已经排序的数组，例如硬盘上的文件，但事先不知道赔率和偶数的数量。
  从
  1. 数组的开头开始填充偶数，从数组的末尾开始填充赔率。这样，最后两个序列将在中间相遇。
  2. 因此，您将从赔率中拆分偶数，但奇数将按递减顺序排列，而不是增加。您只需对奇数部分（也是线性的）进行就地反转，即可获得所需的数组。

希望所描述的场景中至少有一个适合您，并且您将能够使用它的想法来解决您的问题。

，可能存在O（n）时间和O（1）空间算法。但对于我们来说，这可能太复杂了，我们无法理解。

我将通过以下方式说服您：

1. 向您展示原始问题的一个特例，我们称之为 A。
2. 考虑问题A的反面，我们称之为问题B。并表明，如果我们得到其中任何一个的 O（n） 时间和 O（1） 空间解，那么我们可以修改它来解决另一个问题。
3. 我将向您展示问题B可以在O（n）时间和O（1）空间内解决，但是解决方案非常复杂，需要大量的数学运算。

所以这意味着，它不太可能得到一个简单的问题解决方案，否则我们可以很容易地解决问题B。

1.考虑一个特殊情况：

在本例中，设 A[] = {1,2,3,4,5,6,7,8}，从 1 到 2n，n = 4。所以你想把它改成{1,3,5,7,2,4,6,8}，对吧？我们称之为问题A。一般来说，这意味着你有一个大小为 2n 的数组 A，从 A[1] 到 A[2n]，你想把它重新调整到 A[1]，A[3]，A[5]...，A[2n-1]，A[2]，A[4]，A[6]，A[2n]。这是您问题的一个特例。如果你得到了问题的解决方案，那么解决问题A就很容易了。

2.问题A的反面。

让我们考虑一个相关的问题。设 B = {1,2,3,4,5,6,7,8}，我们想将其更改为 {1,5,2,6,3,7,4,8}。这就像你有一副牌，你想做一个完美的洗牌，将它们分成 2 个相等的部分并交替合并它们。所以一般来说，你有一个大小为 2n 的数组 B，从 B[1] 到 B[2n]。您想将其重新调整为 B[1]，B[n+1]，B[2]，B[n+2],....B[n]，B[2n].

然后你会意识到问题A和问题B是反向操作。也就是说，对于大小为 2n 的数组，如果您使用操作 B 执行此操作，然后使用操作 A 执行此操作，那么它将成为原始数组，如果我们先执行 B 然后执行 A，则它将相同。

如果你对排列有一些了解，你就会知道，如果我们得到一个 A 的算法，那么我们可以改变它以使其适用于 B。如果你不熟悉这一点，我稍后可以详细说明。

3.问题B不易解决。

问题 B 是否存在 O（n） 时间和 O（1） 空间算法？确实如此，你可以看看在完美随机排列中计算周期。这是一篇 12 页的论文，这意味着您不太可能在面试中提出这个解决方案。我读过它，它真的需要很多数论的数学。这更像是一个理论解决方案。

结论：

似乎没有一个简单的（这意味着不需要 10 页的论文）O（n） 时间 O（1） 空间解决方案来解决您的问题，即使对于问题 A 中的特殊情况也是如此。否则，我们可以修改它以解决问题 B。我不确定您的广义问题是否有 O（n） 时间 O（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 +（排序复杂性）） - 如果它的性能，在实践中，速度甚至只是上述解决方案的一半，我可能会选择它。

// stable_partition.cpp
// example general inplace stable partition.
#include <algorithm>
#include <functional>
#include <iterator>
#include <iostream>
#include <vector>
template<typename Fwd, typename Pred>
  Fwd
  inplace_stable_partition(Fwd first, Fwd last, Pred pred)
  {
    ptrdiff_t nmemb = std::distance(first, last);
    if (nmemb == 1)
      return pred(*first) ? last : first;
    if (nmemb != 0)
      {
        Fwd split = first;
        std::advance(split, nmemb/2);
        first = inplace_stable_partition(first, split, pred);
        last = inplace_stable_partition(split, last, pred);
        std::rotate(first, split, last);
        std::advance(first, std::distance(split, last));
      }
    return first;
  }
int
main(int argc, char* argv[])
{
  using namespace std;
  vector<int> iv;
  for ( int i = 0; i < 10; i++ )
    iv.push_back(i);
  copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, " "));
  cout << endl;
  inplace_stable_partition(iv.begin(), iv.end(), bind2nd(modulus<int>(), 2));
  copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, " "));
  cout << endl;
  return 0;
}

看起来您正在寻找一种稳定的就地排序算法，该算法具有特殊的元素关系顺序（任何奇数都小于任何偶数）。

鉴于此，我认为您不可能比O（n ln n）更好。

我会选择就地合并排序。

如果您不需要保留具有相同值的元素的顺序，请进行快速排序，这对于就地处理要简单得多（但是，对于数十亿个元素，这可能不太适合）。