在链表上实现希尔排序算法

Question

我正在为我的数据结构类做一个项目，我必须在链接列表上实现希尔排序算法。我们之前使用数组列表来完成此操作，当输入 10,000 个随机整数时，我的程序平均需要 0.012 秒来对列表进行排序。现在我已经使用 Linked List DS 实现了相同的算法，平均时间约为 20.1 秒（哎呀）。我想知道这是否正常，或者是否与实现本身有关？这是算法的主要部分，使用 Knuth 序列作为间隙值：

while(k >= 1) {
            for (int i = k; i < theList.size(); i++) {
                int j = i;
                while (j >= k && theList.get(j - k).compareTo(theList.get(j)) > 0) {  
                    T smaller = theList.delete(j);
                    theList.add(j - k, smaller);

                    T larger = theList.delete(j - k + 1);
                    theList.add(j, larger);

                    j -= k;
                }
            }

我尝试使用交换方法来交换正在比较的两个值，但这似乎没有多大作用。我还尝试重构 LinkedList 的 get()、add() 和 delete() 方法，但这也没有真正做任何事情。

Answer 1

这通常与数据在列表中的存储方式有关。如果它是一个由 10000 个整数组成的向量，每个整数存储在四个字节中，您（应该并且编译器将）知道您想要访问的任何整数（编号从 0 到 9999），该机制将是：

• 将索引乘以四（整数的字节大小），
• 将结果添加到列表的起始地址，
• 获取该位置的四字节整数

非常简单、高效、快速。缺点是在现实世界中数据不会很好地组织，但有一些方法可以处理这个问题。

这就是为什么数据组织至少与编写高效代码一样重要。如果其中一个很出色，但另一个考虑得不够充分，那么你的申请的那部分就不会那么热门。

转到链表，您将使用相同的索引范围，但编译器知道（或者更确切地说，它调用知道的链表库函数），因为它是链表，所以只能通过迭代来确定整数的位置列表中其前面的整数。该机制将是：

• 从头开始迭代 x 个链接的整数，直到整数 x，读取值
• 从头开始迭代 y 个链接的整数，直到整数 y 为止，读取值
• 比较这些值来决定是否必须交换它们（假设是这种情况）
• 从头开始迭代 x 个链接的整数，最终到达整数 x，将其替换为之前从 y 获取的值
• 从头开始迭代 y 链接的整数，最终到达整数 y，将其替换为之前从 y 获取的值

使用链表，一旦获取的值就相当于黄金的重量：只要您需要使用它们，就将它们保留为中间值。诚然，在排序算法中，这不会花费很长时间，但如果您可以保存一两次列表迭代，这将是一个改进。

在您的示例中，您删除并添加链接的整数值以执行交换。保持链接不变，只交换它们的值不是更容易吗？