Java:按完整或不完整对一维对象数组进行排序

Question

我正在尝试压缩一个对象数组，这些对象将包含空项目和完整项目。我想将所有完整元素按照开始时的顺序放在开头，将空元素放在末尾。

相关对象使用 String 字段“name”和 int 字段“weight”。空版本分别为“无名称”和 0。因此，该方法需要处理的类型的数组将包含如下内容:

• 弗雷德 | 4
• 鲍勃 | 3
• 没有名字 | 0
• 吉娜 | 9
• 没有名字 | 0
• 由纪 | 7

通过该方法后，数组应该是 Fred、Bob、Gina、Yuki、no name、no name。

我的第一步想法是弄清楚哪些已满，哪些未满，所以我想出了这个:

public void consolidate() {
    boolean[] fullSlots = new boolean[spaces.length];

    // pass 1: find empties
    for (int i = 0; i < spaces.length; i++) {
        fullSlots[i] = spaces[i].getName().equals("no name");
    }
}

spaces 是对象数组，getName() 从对象中检索名称字段。

我不知道从这里该去哪里。有建议吗？

编辑:好的，这就是 Infested 的想法:

public void consolidate()
{
    int numberOfEmpties = 0, spacesLength = spaces.length;
    Chicken[] spaces2 = new Chicken[spacesLength];
    for(int i = 0; i < spaces.length; i++)
    {
        spaces2[i] = new Chicken(spaces[i].getName(),
                                        spaces[i].getWeight());
    }

    // pass 1: find empties
    for (int i = 0, j = 0; i < spacesLength; i++)
    {
        if (spaces2[i].getName().equals("no name") == false)
        {
            spaces[j] = new Chicken(spaces2[i].getName(),
                                        spaces2[i].getWeight());
            j++;
        }
        else
        {
            numberOfEmpties++;
        }
    }
    for (int i = spacesLength - 1; numberOfEmpties > 0 ; numberOfEmpties--, i--)
    {
       spaces[i] = new Chicken("no name", 0);
    }
}

已测试并正常工作。

Answer 1

Java 的 Arrays.sort 是稳定，这意味着相等元素的相对顺序不会改变。

This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

您可以使用排序算法的此属性通过简单的比较器对所有元素进行排序:

Arrays.sort(
    spaces
,   new Comparator() {
          public int compare(Object o1, Object o2) {
              MyClass a = (MyClass)o1;
              MyClass b = (MyClass)o2;
              boolean aIsEmpty = "no name".equals(a.getName());
              boolean bIsEmpty = "no name".equals(b.getName());
              if (aIsEmpty && !bIsEmpty) {
                  return 1;
              }
              if (!aIsEmpty && bIsEmpty) {
                  return -1;
              }
              return 0;
          }
    }
);

这会将所有具有非空名称的项目排在具有空名称的项目之前，使两组对象在各自组内的相对顺序保持不变。

如果您的空间限制允许您创建一个新的 MyClass 数组，您可以采用更简单的算法:遍历原始数组一次，并对非空项进行计数。然后创建一个新数组，并创建两个索引:idxNonEmpty = 0和idxEmpty = NonEmptyCount+1。然后再次遍历原始数组，将非空对象写入 idxNonEmpty++，将空对象写入 idxEmpty++。