问题:
给你一个结构体,其中包含两个元素,一个是整型部门,另一个是字符串姓名,用于保存员工详细信息。
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算法应该是稳定的,并且时间复杂度应该为O(N),对于其他变量来说空间应该是常数级别的(这意味着应该在原地进行排序)。
X2 1 X4 1 X1 0 X3 0 X5 0