在单个链接列表上使用插入排序

Question

所以我有一个任务,我给出一个随机的数字列表,我需要使用插入排序对它们进行排序.我必须使用单链表.我环顾四周其他帖子但似乎没有任何帮助.我得到什么插入排序但我只是不知道如何在代码中写它.

Node* insertion_sort(Node* head) {
  Node* temp = head_ptr;
  while((head->n < temp->n) && (temp != NULL))
    temp = temp->next;
  head->next = temp->next;
  temp->next  = head;
  head->prev = temp;
}

我不知道这是对的还是现在要做什么

Answer 1

让我们考虑一下插入排序是如何工作的：它（理论上）将列表“拆分”为三组：已排序子集（可能为空）、当前项和未排序子集（可能为空）。当前项目之前的所有内容都已排序。当前项目之后的所有内容可能会或可能不会被排序。该算法检查当前项目，将其与下一个项目进行比较。请记住，当前项之后的第一项属于未排序的子集。

让我们假设您按递增顺序对整数进行排序（因此给定“3,1,5,2,4”，您希望得到“1,2,3,4,5”）。您将当前项目设置为列表中的第一项。现在开始排序：

如果下一项大于当前项，则不需要对该项进行排序。只需将其设为“当前项目”并继续。

如果下一个项目小于当前项目，那么您有一些工作要做。首先，将下一项保存在某处——假设在一个名为 temp 的指针中——然后通过使 current->next = current->next->next 从列表中“删除”下一项。现在，您需要为已删除的项目找到正确的位置。您可以通过两种方式执行此操作：

1. 要么从列表的开头开始，一直向前，直到找到正确的位置。完成后，您在那里插入项目并继续您的插入排序。如果您有一个单链表，这是最简单的解决方案。
2. 您向后走，直到找到该项目的正确位置。完成后，您在那里插入项目并继续您的插入排序。这有点复杂，但如果你有一个双向链表，它可以很好地工作。

您继续此过程，直到到达列表的末尾。一旦到达它，您就知道您已经完成了插入排序，并且列表的排序顺序正确。

我希望这有帮助。

Answer 2

struct node {
    int data;
    struct node *next;
};


void insertion(struct node **head) {
    if((*head)== NULL || (*head)->next == NULL) {
       return;
    }
    struct node *t1 = (*head)->next;
    while(t1 != NULL) {
        int sec_data = t1->data;
        int found = 0;
        struct node *t2 = *head;
        while(t2 != t1) {
            if(t2->data > t1->data && found == 0) {
                sec_data = t2->data;
                t2->data = t1->data;
                found = 1;
                t2 = t2->next;
            } else {
                if(found == 1) {
                    int temp = sec_data;
                    sec_data = t2->data;
                    t2->data = temp;
                }
                t2 = t2->next;
            }
       }
       t2->data = sec_data;
       t1 = t1->next;
    }
}

Answer 3

考虑一下 - 如果列表为空，则temp最初将为空NULL，因此当您这样做时，您会得到未定义的行为temp->next = head;。

尝试一些调试，肯定会有帮助。您可能还想保留前一个节点，以便可以在后面插入，或者向前查找 2 个节点。