java linkedlist字符串排序算法

Question

所以，我有几个单词对列表，我需要按升序或降序对它们进行排序。我现在使用的方法是插入排序算法。对于较小的列表，这似乎很有效。但每次我尝试对一个大列表排序时，它都会冻结，没有错误。我试着通过打印“a被换成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

除了插入排序已经是O（N^2）算法之外，项索引对链表中的项的访问（get和set）也是O（N）操作，这使得代码O（N^3），换句话说非常慢

基本上，你有两个选择：

• 将链表复制到临时数组中，使用算法对数组进行排序（按索引的数组访问为O（1），整体算法将保持O（N^2）（除非选择更好的），从数组中创建一个新的排序链表
• 使用其他一些不需要索引访问的算法（例如，实际上可以实现插入排序，而不需要索引操作，因为可以交换链表中的两个相邻项，因为必须使用链表实现，其中可以直接访问“上一个”和“下一个”链接）