java链表字符串排序算法

Question

所以，我有几个单词对列表，我需要按升序或降序对它们进行排序。我现在使用的方法是插入排序算法。这似乎适用于较小的列表。但是每次我尝试对一个大列表进行排序时，它都会卡住，没有错误。我试图通过打印出“a was swapped for b”来调试看看发生了什么你可以看到它开始工作，然后变慢并最终停止，就像计算机刚刚说的那样，“太多了，我放弃了”。我的问题是，我的代码是否有问题，或者我是否只需要使用一种更有效的方法，如果是这样，是哪一种方法，它会是什么样子？

for (int j=0; j < wordpair_list.size()-1; j++){
    for (int i=0; i < wordpair_list.size()-1; i++){
        String wordA_1 = wordpair_list.get(i).getWordA();
        String wordA_2 = wordpair_list.get(i+1).getWordA();

        if (wordA_1.compareToIgnoreCase(wordA_2) < 0){
            WordPair temp = wordpair_list.get(i);
            wordpair_list.set(i,wordpair_list.get(i+1));
            wordpair_list.set(i+1, temp);           
        }
    }
}

那是下降。我为升序所做的就是将 if 语句中的 '>' 交换为 '<'

Answer 1

我认为您正在执行冒泡排序。正如其他人所指出的那样，使用链表执行 get() 和 set() 操作非常昂贵。

我不熟悉 Java，但看来您可以使用 ListIterators 在 O(N^2) 中执行冒泡排序

ListIterator listIterator(int index) Returns a list-iterator of the elements in this list (in proper sequence), starting at the specified position in the list. Throws IndexOutOfBoundsException if the specified index is is out of range (index < 0 || index >= size()).

对于冒泡排序，您只需要交换相邻的元素，因此您可以像数组一样遍历列表并在需要时继续交换。

此外，您可以跳过列表中已排序的部分。看看一个好的冒泡排序算法。 http://en.wikipedia.org/wiki/Bubble_sort