c - 使用一组有限的操作对 2 个 50000 个数字的链表进行排序

Question

所以我有这个学校项目:我有一个包含 50 000 个数字的链表和第二个空列表。我只有非常有限的说明面板。他们是:

• “sa”交换列表 1 的前两个元素

• “sb”交换列表 2 的前两个元素

• “ss”同时是“sa”和“sb”

• "pa": 将列表 2 的顶部元素推到列表 1 的顶部

• “pb”:将列表 1 的顶部元素推到列表 2 的顶部

• “ra”:循环列表 1(第一个元素变成最后一个)

• "rb":循环列表2(先到后)

• “rr”:同时显示“ra”和“rb”

• “rra”:轮换列表 1(最后成为第一个)

• “rrb”:轮换列表 2(最后成为第一个)

• “rrr”:同时显示“rra”和“rrb”

我必须在 c 中实现一个排序算法，目标是用最少的指令来完成。 我尝试了一个非常简单的算法，该算法旋转列表 1，直到最大值位于顶部，然后将其反复插入列表 2，直到所有内容都在列表 2 中，然后将所有内容推回到列表 1 中，但我无法对更多列表进行排序在合理的时间内超过 5k 个数字

Answer 1

我想我已经想出了如何使用快速排序来做到这一点。这是一些伪代码。

编辑:更新伪代码以专注于它在做什么而不是不必要的语法

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，您也应该在某个递归深度下)。

显然合并排序在链表上更快。修改它以实现合并排序可能不会太难。合并排序与快速排序非常相似。 why is merge sort preferred over quick sort for sorting linked lists