本文旨在澄清双向链表插入排序的严格定义和实现细节，特别是关于其空间复杂度的考量。我们将分析一种常见的误区——通过复制节点而非移动节点来构建排序列表的方法，并阐述如何通过“重连”现有节点实现真正的O(1)额外空间复杂度插入排序，同时提供专业的代码实现指导。
插入排序概述
插入排序是一种简单直观的排序算法。其基本思想是，通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。对于数组，这通常涉及元素的移动。对于链表，由于其动态特性，插入操作相对高效，但其实现方式对算法的严格定义和资源消耗有着重要影响。
常见的链表插入排序实现误区
在尝试为双向链表实现插入排序时，一个常见的做法是创建一个新的空链表作为结果，然后遍历原始链表，将每个节点的键和数据复制到新创建的节点中，并插入到结果链表的正确位置。以下是一个示例代码片段，展示了这种实现思路：
public static List sort(List list) { List sortedList = new List(); // 新建一个空链表用于存放排序结果 List.Iter curIndex = List.Iter.last(sortedList); // 用于在sortedList中寻找插入位置的迭代器 for(List.Iter iter = List.Iter.first(list); !iter.end(); iter.next()) { curIndex = List.Iter.last(sortedList); List.Node node = iter.key_data(); // 获取原始链表中的节点 // ... 省略寻找插入位置的逻辑 ... // 关键点：这里通过node.key和node.data创建了一个新的节点并插入 sortedList.insAfter(curIndex, node.key, node.data); } return sortedList;}
尽管上述代码能够生成一个键值有序的新链表，但它并非严格意义上的链表插入排序。其主要问题在于：
节点复制而非移动：该实现通过 sortedList.insAfter(curIndex, node.key, node.data) 创建了新的 List.Node 对象，并将原始节点的键和数据复制过去。这违背了插入排序“移除一个元素并插入到正确位置”的核心原则。真正的插入排序应该操作并重新组织现有的元素（或节点）。空间复杂度问题：由于为每个原始节点都创建了一个新的节点，这种实现的空间复杂度为 O(N)，其中 N 是链表中的元素数量。而对于链表的插入排序，其设计目标之一是利用链表的特性，实现 O(1) 的额外空间复杂度（不包括存储链表本身所需的空间）。
根据维基百科对插入排序的定义：“插入排序迭代地消耗一个输入元素，每次重复都增长一个已排序的输出列表。在每次迭代中，插入排序移除输入数据中的一个元素，找到它在已排序列表中的位置，然后将其插入。”特别地，对于链表，“如果项存储在链表中，则列表可以使用 O(1) 额外空间进行排序。算法从一个最初为空（因此是微不足道的已排序）列表开始。输入项被从列表取出，然后插入到已排序列表的适当位置。当输入列表为空时，已排序列表就是所需的结果。”
链表插入排序的正确实现：O(1) 额外空间复杂度
为了实现符合严格定义的链表插入排序，并达到 O(1) 的额外空间复杂度，我们必须遵循“移动”而非“复制”节点的原则。这意味着我们需要直接操作原始链表中的节点，将它们从原始链表中“取出”，然后“插入”到构建中的已排序链表中。
钉钉 AI 助理
钉钉AI助理汇集了钉钉AI产品能力，帮助企业迈入智能新时代。
21 查看详情
假设我们的 List 类具有以下基本操作：
isEmpty(): 判断链表是否为空。removeFirst(): 移除并返回链表的第一个节点。insertAfter(Iter iterator, Node node): 在指定迭代器指向的节点之后插入一个现有节点。insertBefore(Iter iterator, Node node): 在指定迭代器指向的节点之前插入一个现有节点。first(): 获取指向链表第一个元素的迭代器。last(): 获取指向链表最后一个元素的迭代器。next() / prev(): 迭代器前进/后退。end(): 判断迭代器是否到达末尾。
以下是基于这些操作的 O(1) 额外空间复杂度双向链表插入排序的实现思路：
public static List sort(List originalList) { // 1. 初始化一个空的sortedList。这个sortedList将由originalList中的节点构成。 List sortedList = new List(); // 2. 循环，直到originalList中的所有节点都被移动到sortedList while (!originalList.isEmpty()) { // 3. 从originalList中移除第一个节点 List.Node currentNode = originalList.removeFirst(); // 假设removeFirst返回被移除的节点 // 4. 在sortedList中找到currentNode的正确插入位置 // 如果sortedList为空，直接插入currentNode if (sortedList.isEmpty()) { sortedList.insertAfter(List.Iter.last(sortedList), currentNode); // 假设last()在空链表时返回一个可插入的“虚拟”迭代器 } else { List.Iter insertPosIter = sortedList.first(); // 从sortedList的开头开始查找 boolean inserted = false; // 遍历sortedList，找到第一个键值大于或等于currentNode.key的位置 while (!insertPosIter.end()) { if (currentNode.key < insertPosIter.key_data().key) { // 找到位置，在当前迭代器指向的节点之前插入 sortedList.insertBefore(insertPosIter, currentNode); inserted = true; break; } insertPosIter.next(); } // 如果遍历完sortedList都没有找到比currentNode.key大的节点， // 说明currentNode应该插入到sortedList的末尾 if (!inserted) { sortedList.insertAfter(List.Iter.last(sortedList), currentNode); } } } return sortedList;}
代码解析与注意事项：
originalList.removeFirst(): 这是实现 O(1) 额外空间的关键。它将原始链表中的节点取出，而不是复制其内容。这意味着 originalList 在排序过程中会逐渐变空。sortedList.insertAfter(Iter, Node) / sortedList.insertBefore(Iter, Node): 这些方法直接将 currentNode (即从 originalList 中取出的那个节点对象) 插入到 sortedList 中，而不创建新的节点。迭代器管理: 在双向链表中，insertAfter 和 insertBefore 操作相对直接。寻找插入位置时，可以从 sortedList 的头部或尾部开始遍历，取决于 currentNode.key 与已排序部分的比较结果，以优化查找效率。空链表处理: 当 sortedList 为空时，需要特殊处理，确保第一个节点能正确插入。O(1) 额外空间: 除了用于存储 sortedList 结构本身（其节点是 originalList 的节点）所需的空间外，算法没有额外创建新的节点对象，因此满足 O(1) 额外空间复杂度的要求。原链表状态: 此实现会清空 originalList。如果需要保留 originalList 的内容，则必须在排序前对其进行深拷贝，但这会引入 O(N) 的额外空间。
总结
链表插入排序的正确实现，特别是对于追求 O(1) 额外空间复杂度的场景，关键在于理解并执行“移动”而非“复制”节点的原则。通过将原始链表中的节点逐一取出，并重新连接到构建中的已排序链表中，我们能够遵循算法的严格定义，同时优化资源使用。在实现时，需要确保链表操作（如移除、插入）能够高效且正确地处理节点引用，避免创建不必要的对象。
以上就是深入理解双向链表插入排序：O(1) 空间复杂度的实现的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/300497.html
微信扫一扫 
支付宝扫一扫 
