9

考虑一个数组列表，如下所示

unsortedList = {6,"ball",3,1,"apple","cat",4}

这需要排序为

sortedList = {1,"apple",3,4,"ball","cat",6}

按字母顺序对字符串进行排序。按升序对数字进行排序。但请注意以下条件：

  • 无论未排序列表中的哪里有整数，它都必须是排序列表中的整数。
  • 无论未排序列表中的字符串在哪里，它都必须是已排序列表中的字符串。

请注意，在上面的示例中，所有整数都按升序排序，所有字符串均按升序排序，但整数和字符串的相对位置与之前没有变化。

4

2 回答 2

8

这里的一种选择是执行以下操作：

  • 创建一个包含原始列表中所有整数的新列表。
  • 创建原始列表中所有字符串的新列表。
  • 对每个列表进行排序。
  • 遍历原始列表，执行以下操作：
    • 如果元素存在整数，则从排序的整数列表中写回下一个未写入的整数。
    • 如果元素存在字符串，则从已排序的字符串列表中写回下一个未写入的字符串。

这是非常有效的——你只需要做两种。这是它的一些代码：

public void relativeOrderSort(List<Object> list) {
    /* Create a list of just the integers and just the strings
     * from the original list.
     */
    List<Integer> intList = new ArrayList<Integer>();
    List<String> strList = new ArrayList<String>();
    for (Object obj: list) {
        if (obj instanceof Integer) {
            intList.add((Integer) obj);
        } else if (obj instanceof String) {
            strList.add((String) obj);
        } else {
            throw new IllegalArgumentException("List has a non-int, non-string member.");
        }
    }

    /* Sort the lists. */
    Collections.sort(intList);
    Collections.sort(strList);

    /* Merge the lists back together. */
    int intIndex = 0, strIndex = 0;
    for (int i = 0; i < list.size(); i++) {
        if (list.get(i) instanceof Integer) {
           list.set(i, intList.get(intIndex++));
        } else {
           list.set(i, strList.get(strIndex++));
        }
    }
}

希望这可以帮助！

于 2013-06-13T22:53:02.697 回答
3

伪代码：

Create a list of the indices pointing to integers ({0,2,3,6} in your case - indxInt )
Sort the integers  ({6,3,1,4} turns into {1,3,4,6})
Put them back at the locations given by the pointers:
  sorted(indxInt(0)) = 1;
  sorted(indxInt(1)) = 3;
  sorted(3) = 4; // indxInt(2) == 3
  sorted(6) = 6; // indxInt(3) == 6
Repeat for the strings
于 2013-06-13T22:54:22.160 回答