最佳排序算法——部分排序链表
Best sorting algorithm - Partially sorted linked list
Problem- Given a sorted doubly link list and two numbers C and K. You need to decrease the info of node with data K by C and insert the new node formed at its correct position such that the list remains sorted.
对于这样的问题，我会想到插入排序，因为，插入排序在任何情况下看起来都像，显示一堆卡片，
部分排序。对于插入排序，交换次数等于反转次数。比较次数等于交换次数+（N-1）。
因此，在给定的问题（上面）中，如果具有数据 K 的节点减少 C，则排序链表变为部分排序。 插入排序最适合。
还有一点，在排序算法的选择中，如果应用于数据的数组表示的排序逻辑最适合，那么相同的排序逻辑应该最适合相同数据的链表表示。
对于这个问题，我选择插入排序的思路是否正确？
也许你的意思是别的，但插入排序并不是最好的算法，因为你实际上不需要对任何东西进行排序。如果只有一个元素的值为 K，那么它不会产生很大的差异，否则就会产生影响。
所以我建议使用以下算法 O(n)，为简单起见忽略边缘情况：
- 在链表中往前走，直到当前节点的值为 > K - C。
- 保存该节点，所有缩减的节点将插入到该节点之前。
- 当当前节点的值为
- 当当前节点的值为K时，移除节点，设置值为K-C插入到保存的节点之前。这可以进一步优化，以便您只对具有值 K 的整个节点子列表执行一次删除和插入操作。
如果这些减少操作可以在排序列表必须可用之前进行批处理，那么您可以简单地从列表中删除所有减少的节点。然后，对它们进行排序，并进行双向合并到列表中。
如果在每个节点递减后必须保持列表的顺序，那么别无选择，只能删除递减的节点并按顺序重新插入。
对一副纸牌进行线性搜索可能是可以接受的，除非您运行一些涉及纸牌的可怕Monte Carlo模拟，运行数小时或一天，以便优化计数。
否则我们处理维护顺序需要的方法将是使用有序序列数据结构：平衡二叉树（红黑，splay）或跳跃列表。将节点取出结构，调整值，重新插入：O(log N).
Problem- Given a sorted doubly link list and two numbers C and K. You need to decrease the info of node with data
KbyCand insert the new node formed at its correct position such that the list remains sorted.
对于这样的问题，我会想到插入排序，因为，插入排序在任何情况下看起来都像，显示一堆卡片，
部分排序。对于插入排序，交换次数等于反转次数。比较次数等于交换次数+（N-1）。
因此，在给定的问题（上面）中，如果具有数据 K 的节点减少 C，则排序链表变为部分排序。 插入排序最适合。
还有一点，在排序算法的选择中，如果应用于数据的数组表示的排序逻辑最适合，那么相同的排序逻辑应该最适合相同数据的链表表示。
对于这个问题，我选择插入排序的思路是否正确？
也许你的意思是别的，但插入排序并不是最好的算法，因为你实际上不需要对任何东西进行排序。如果只有一个元素的值为 K，那么它不会产生很大的差异，否则就会产生影响。
所以我建议使用以下算法 O(n)，为简单起见忽略边缘情况：
- 在链表中往前走，直到当前节点的值为 > K - C。
- 保存该节点，所有缩减的节点将插入到该节点之前。
- 当当前节点的值为
- 当当前节点的值为K时，移除节点，设置值为K-C插入到保存的节点之前。这可以进一步优化，以便您只对具有值 K 的整个节点子列表执行一次删除和插入操作。
如果这些减少操作可以在排序列表必须可用之前进行批处理，那么您可以简单地从列表中删除所有减少的节点。然后，对它们进行排序，并进行双向合并到列表中。
如果在每个节点递减后必须保持列表的顺序，那么别无选择，只能删除递减的节点并按顺序重新插入。
对一副纸牌进行线性搜索可能是可以接受的，除非您运行一些涉及纸牌的可怕Monte Carlo模拟，运行数小时或一天，以便优化计数。
否则我们处理维护顺序需要的方法将是使用有序序列数据结构：平衡二叉树（红黑，splay）或跳跃列表。将节点取出结构，调整值，重新插入：O(log N).