algorithm - 将 0's & 1' 排列成数组

Question

这是我最近遇到的面试问题之一。我想知道其他人对解决这个问题的方法的看法。

问题:

你得到一个结构，它包含两个元素的员工详细信息，int 部门和 string 名称。

struct Employee
{ 
    string Name;
    int Dept;
}

给定N名员工的详细信息，其中N/2名员工有Dept == 0，N/2名员工有Dept == 1，按一些排列任意顺序。您需要根据员工的 Dept 值对员工详细信息进行排序，它应该是 stable即保持原始记录中1和0的顺序。

例如，给定以下样本数据:

Name         Dept

X1           0
X2           1
X3           0
X4           1
X5           0

排序后的结果应该是:

Name         Dept

X2           1
X4           1
X1           0
X3           0
X5           0

算法应该是稳定的，时间复杂度应该是 O(N)，额外变量的空间是恒定的(这意味着排序应该就地完成)。

Answer 1

分配第二个数组 (O(N))。遍历第一个数组并按照它们在第二个数组中出现的顺序移动所有 1。再次迭代并将以相同顺序留下的 0 移动到第二个数组。所有操作 O(N)。这不是原位(就地)解决方案。运行一次Quicksort划分算法得到一个不稳定的原位解。

经过一些研究，似乎没有任何额外内存的已知 O(N) 解是不稳定的。有关于原位(就地)高效 0-1 稳定排序的学术研究，但解决方案需要一些额外的内存。我想知道原始问题陈述是否没有以精确的方式复制。没有稳定性要求很容易出问题；没有现场要求也很容易。对于这两种要求(就地、稳定)，解决方案似乎难以捉摸。

在此处的答案中，有一种算法可以在 O(N) 中运行并且就地运行，但前提是关键字段 (1) 可变并且 (2) 可以包含整数而不是单个位。这可行，但不是原位 0-1 稳定排序，因为假定每个数组元素有 O(log N) 可写内存可用。