深入理解双向链表插入排序：O(1) 空间复杂度的实现

本文旨在澄清双向链表插入排序的严格定义和实现细节，特别是关于其空间复杂度的考量。我们将分析一种常见的误区——通过复制节点而非移动节点来构建排序列表的方法，并阐述如何通过“重连”现有节点实现真正的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;
}

尽管上述代码能够生成一个键值有序的新链表，但它并非严格意义上的链表插入排序。其主要问题在于：

1. 节点复制而非移动：该实现通过 sortedList.insAfter(curIndex, node.key, node.data) 创建了新的 List.Node 对象，并将原始节点的键和数据复制过去。这违背了插入排序“移除一个元素并插入到正确位置”的核心原则。真正的插入排序应该操作并重新组织现有的元素（或节点）。
2. 空间复杂度问题：由于为每个原始节点都创建了一个新的节点，这种实现的空间复杂度为 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) 空间复杂度的实现的详细内容，更多请关注php中文网其它相关文章！