insertion - 单链表上的插入排序

Question

我是否认为不可能对单链表执行插入排序？

我的推理：假设insertion sort根据定义，当我们在外循环中向右移动时，我们在内循环中向左移动并根据需要向上（向右）移动值，并在完成后插入我们的当前值内循环。因此，SLL 无法适应这样的算法。正确的？

Answer 1

这是可行的，并且是一个值得探索的有趣问题。

插入排序算法的核心是用第一个元素创建一个排序序列，并通过添加新元素来扩展它，并保持序列仍然是排序的，直到它包含所有输入数据。

单链表是不能回溯的，但是你可以随时从它的头部开始寻找新元素的位置。

棘手的部分是在节点 j 之前插入节点 i 时，您必须处理好它们的邻居关系（我的意思是节点 i 和 j 的邻居都需要照顾）。

Answer 2

这是我的代码。我希望它对你有用。

int insertSort(Node **pHead)
{
Node *current1 = (*pHead)->next;
Node *pre1 =*pHead;
Node *current2= *pHead;
Node *pre2=*pHead;
while(NULL!=current1)
    {
    pre2=*pHead;
    current2=*pHead;

    while((current2->data < current1->data))
    {
        pre2 = current2;
        current2 = current2->next;
    }
    if(current2 != current1)
    {
        pre1->next=current1->next;
        if(current2==*pHead)
        {
            current1->next=*pHead;
            *pHead = current1;
        }
        else
        {
            pre2->next = current1;
            current1->next = current2;
        }
        current1 = pre1->next;
    }
    else
    {
        pre1 = pre1->next;
        current1 = current1->next;
    }
}
return 0;

}

Answer 3

好吧，我听起来像是明显的船长，但答案主要取决于您是否可以保持所有迭代的方向与元素链接的方式相同，并且仍然根据您的定义实施正确的排序算法。我真的不想弄乱您对插入排序的定义，所以恐怕您真的必须自己考虑。至少有一段时间。无论如何，这是一个家庭作业...... ;)

好的，这是我在关闭页面之前得到的。您可以反向迭代 SLL，但这需要 n*n/2 次遍历才能访问所有 n 个元素。所以理论上你对排序循环的任何遍历方向都没有问题。猜猜它几乎解决了你的问题。