1

我正在尝试使用插入排序算法对数组进行排序。该数组填充了WordNode包括word字段（从文本文件输入）和frequency字段（用于测量特定单词在文本文件中出现的次数）的元素。我已经实现了排序，以便单词按频率排序（从最低到最高），但如果频率相等，我也想按字母顺序排序。如何同时使用两个不同的标准进行排序？下面是我的排序代码。

public static void sort(ArrayUnorderedList<WordNode> array) {
    //create stacks for insertion sort
    LinkedStack<WordNode> sorted = new LinkedStack<WordNode>();
    LinkedStack<WordNode> temp = new LinkedStack<WordNode>();

    //while the array has elements to be sorted
    while(!array.isEmpty()) {
        //remove current element from array
        WordNode currentNode = array.removeFirst();

        //while the sorted stack meets sorting criteria
        while((!sorted.isEmpty()) && (sorted.peek().getFrequency() < currentNode.getFrequency())) {
            //push elements to temp stack
            temp.push(sorted.pop());
        }

        //push current element to sorted stack
        sorted.push(currentNode);

        //while the temp stack has elements to be replaced
        while(!temp.isEmpty()) {
            //push elements to sorted stack
            sorted.push(temp.pop());
        }
    }

    //replace sorted elements in array
    while(!sorted.isEmpty()) {
        array.addToRear(sorted.pop());
    }
}
4

4 回答 4

1

AppClay 的回答是绝对正确的，但是如果您对“整理”感兴趣，请创建一个实现Comparator的助手。

class WordNodeComparator implements Comparator<WordNode> {
    @Override
    public int compare(WordNode lhs, WordNode rhs) {
        int result = lhs.getFrequency() - rhs.getFrequency();
        if (result == 0) {
            return lhs.getWord().compareTo(rhs.getWord());
        }
        else {
            return result;
        }
    }
}

然后你只需创建它的一个实例，并在你的循环中使用它：

while((!sorted.isEmpty()) && (nodeComparator.compare(sorted.peek(), currentNode) < 0)

这不仅使代码更易于阅读和测试，而且现在可以根据需要更换不同的 Comparator 实现。

于 2012-04-13T02:14:11.450 回答
0

将此添加到您的代码中：

int cmp = sorted.peek().getFrequency() - currentNode.getFrequency();
if (cmp == 0)
    cmp = sorted.peek().getWord().compareTo(currentNode.getWord());

while((!sorted.isEmpty()) && cmp < 0) {
    //push elements to temp stack
    temp.push(sorted.pop());
    cmp = sorted.peek().getFrequency() - currentNode.getFrequency();
    if (cmp == 0)
        cmp = sorted.peek().getWord().compareTo(currentNode.getWord());
}

我假设getFrequency()返回一个整数，并且 a 中的实际单词WordNode由该getWord()方法访问。使用上面我们首先按频率比较，如果两个频率相等，那么我们按字母顺序比较

编辑 ：

一个更好的解决方案，定义这个辅助方法：

private static boolean compare(LinkedStack<WordNode> sorted, WordNode current) {
    int cmp = sorted.peek().getFrequency() - current.getFrequency();
    if (cmp == 0)
        cmp = sorted.peek().getWord().compareTo(current.getWord());
    return cmp;
}

然后将代码中的第一个内部循环更改为：

while (!sorted.isEmpty() && compare(sorted, currentNode) < 0) {
    //push elements to temp stack
    temp.push(sorted.pop());
}
于 2012-04-13T01:56:42.207 回答
0

更新这一行：

while((!sorted.isEmpty()) && (sorted.peek().getFrequency() < currentNode.getFrequency())) {

到：

while((!sorted.isEmpty()) && (sorted.peek().getFrequency() < currentNode.getFrequency() || (sorted.peek().getFrequency() == currentNode.getFrequency() &&  sorted.peek().getWord().compareTo(currentNode.getWord()) < 0))) {
于 2012-04-13T01:59:18.727 回答
0

使用番石榴库：

    public static List<WordNode> sort(List<WordNode> src){
       List<WordNode> result = Lists.newArrayList(src);
       Collections.sort(result, new Comparator<WordNode>(){
           @Override public int compare(WordNode w1, WordNode w2) {
             return ComparisonChain.start()  
                     .compare(w1.frequency, w2.frequency)  
                     .compare(w1.word     , w2.word) 
                     .result(); 
        }});
       return result;
     }
于 2012-04-13T02:36:06.193 回答