使用一组有限的操作对2个50000个数字的链表进行排序
所以我有这个项目用于学校：我有一个包含5万个数字和第二个空列表的链表。 我只有一个非常有限的指示小组。 他们是 ：
-
“sa”交换了列表1的前两个元素
-
“sb”交换了清单2的前两个元素
-
“ss”同时是“sa”和“sb”
-
“pa”：在列表1的顶部推送列表2的顶部元素
-
“pb”：在列表2的顶部推送列表1的顶部元素
-
“ra”：旋转列表1（第一个元素成为最后一个）
-
“rb”：旋转列表2（第一个成为最后一个）
-
“rr”：“ra”和“rb”立刻
-
“rra”：旋转列表1（最后成为第一个）
-
“rrb”：旋转列表2（最后成为第一个）
-
“rrr”：“rra”和“rrb”立刻
我必须在c中实现排序算法，目标是使用最少量的指令。 我尝试了一个非常简单的算法，旋转列表一直到最大值位于顶部，然后反复将其推入列表2，直到所有内容都在列表2中，然后将所有内容推回到列表1中，但我无法对列表进行排序在合理的时间内超过5k的数字
我想我已经想出如何使用快速排序来做到这一点。 这是一些伪代码。
编辑：更新的伪代码，专注于它正在做的事情，而不是不必要的语法
quicksort(int n) if n == 1 return int top_half_len = 0 choose a median //it's up to you to determine the best way to do this for 0 to n { //filter all values above the median into list 2 if (value > median) { push list 1 top to list 2 //list 2 stores the larger half top_half_len++ } rotate list 1 forward } //reverse the list back to original position rotate list 1 backward (n - top_half_len) times //push larger half onto smaller half push list 2 top to list 1 top_half_len times //recursively call this on the larger half quicksort(top_half_len) //rotate smaller half to front rotate list 1 forward top_half_len times //recursively call this on smaller half quicksort(n - top_half_len) //reverse list back to original position rotate list 1 backward top_half_len times
基本上，它将列表分成小于或等于中值（较小的一半）的部分和大于中值的部分（较大的一半）。 然后它会在这两半中调用自己。 一旦它们的长度为1，算法就完成了，因为对1长度列表进行了排序。 谷歌快速排序实际解释。
我认为这应该有用，但我可能错过了一些边缘案例。 不要盲目跟随这一点。 另外，如果你正在处理数组，我建议你在某个递归深度停止快速排序并使用堆排序（或者防止最坏情况O（n ^ 2）复杂度的东西），但我不确定这会有什么效率。 更新：根据Peter Cordes的说法，当你达到某个数组大小时，你应该使用插入排序（IMO你应该在某个递归深度）。
显然，链接列表上的合并排序更快。 修改它以实现合并排序可能不会太难。 合并排序与快速排序非常相似。 为什么合并排序优先于快速排序以排序链接列表
问题陈述缺少比较函数，因此我将定义compare（lista，listb）以将lista的第一个节点与listb的第一个节点进行比较，并返回-1表示<，0表示=，1表示更大，或者所有合并排序真的需要0为<=和1为>。
还缺少一个返回值，表示在执行pa或pb时列表为空。 如果源列表不为空，我将定义pa或pb返回1，如果源列表为空（无要复制的节点），则定义为0。
目前尚不清楚目标是否是最小量的指令是指源代码中的指令数量或排序期间执行的指令数量。
-
代码中最小数量的指令将基于与list1的比较来旋转list2，以将节点插入到正确位置的list2中。 从pb开始，并将list2大小设置为1.然后执行rb或rrb将list2旋转到下一个pb应该完成的位置。 代码将跟踪list2“偏移”到最小节点，以避免旋转list2中的无限循环。 复杂度是O（n ^ 2）。
-
我认为最快的排序，也许最少的指令执行是自下而上的合并排序。
在旋转列表时执行自下而上的合并排序，使用它们像循环缓冲区/列表。 使用序列|将list1复制到list2以生成节点计数 count = 0 | 而（pb）{rb | count + = 1}。
使用计数，使用{pa，rr}，n / 2次将每个其他节点从list2移动到list1。 始终跟踪每个列表上的实际节点数，以便知道何时到达列表的逻辑结尾。 还要跟踪每个列表的运行计数器，以了解何时达到运行的逻辑结束。 此时，您有两个列表，其中偶数节点位于list1上，奇数节点位于list2上。
运行大小从1开始，每次传递加倍。 对于运行大小为1的第一次传递，将偶数节点与奇数节点合并，创建大小为2的已排序运行，交替将已排序的节点对添加到list1和list2。 例如，如果追加到list1和list1节点<= list2节点，请使用{ra，run1count - = 1}，否则使用{pa，ra，run2count - = 1}。 到达运行结束时，将剩余的剩余运行追加到列表的末尾。 在下一次传递中，合并从列表中排序的2个节点的运行，交替地将4个节点的排序运行附加到每个列表。 继续运行8,16，...直到所有节点都在一个列表上结束。
因此，这是计算节点的一次传递，一次传递以分割偶数和奇数节点，并且ceil（log2（n））传递以进行合并排序。 链表操作的开销很小（旋转删除并附加节点），因此整体合并应该相当快。
计数传递的指令数可以用while（pb）{count + = 1}来减少，这会将list1复制到list2。 然后使用rrr将list2吐出到list1中以解除它们。
复杂度为O（n log（n））。