使用链表进行插入排序

-1

（1）您将只实现插入排序，（2）您将使用链表来存储长整数，而不是使用数组进行存储。因此，您的排序必须在链接列表上执行。使用链表进行插入排序

我的代码如下。

Node *Insertion_Sort(Node *sublist) { 
//Initialize`enter code here` 
Node *dummy_node = malloc(sizeof(Node)); 
dummy_node->next = NULL; 

Node *prev_node = sublist; 
Node *curr_node = sublist->next; 

Node *head = prev_node; 

Node *temp_node = malloc(sizeof(Node)); 
while(curr_node->next != NULL){ 
    if (prev_node->value < curr_node->value) { 
     //advance the pointers 
     prev_node = curr_node; 
     if (curr_node != NULL) { 
      curr_node = curr_node->next; 
      printf("Advancing prev=%ld curr=%ld\n", prev_node->value, curr_node->value); 
     } 
     else 
     { 
      break; 
     } 
    } 
    else 
    { 
     //swap 
     temp_node = curr_node; 
     prev_node->next = curr_node->next; 
     curr_node->next = prev_node; 
     // Advance 
     prev_node = curr_node; 
     curr_node = curr_node->next; 
     head = prev_node; 
    } 
} 
//curr_node->next = NULL; 

return head; 
}

但它只是部分工作。有谁能够帮助我？

来源

2014-02-28 user3295123

定义“它只是部分工作”。 – dornhege

就像@dornhege说的那样，你当前的输出是什么？你认为问题领域是什么？一些额外的信息使得回答您的问题变得更容易。 –

你在这个排序例程中分配*任何*是值得怀疑的。你使用'malloc（）'在C++程序中执行它是非常有问题的。我没有记得插入任何东西 - 除了交换以外，要求对临时存储进行排序，并且由于您使用的是链接列表，因此您应该交换的唯一东西是指针值，而不是节点。 – WhozCraig

您不应该为节点分配任何空间。 Wiki链接为Insertion sort。你可能应该使用第二伪代码示例（其中一部分我进行排序之前，而你通过删除和插入节点插入排序部分）：

for i ← 1 to length(A) 
    x ← A[i] 
    j ← i 
    while j > 0 and A[j-1] > x 
     A[j] ← A[j-1] 
     j ← j - 1 
    A[j] ← x

更换内部while循环只需扫描A [i]需要插入的位置。注意，如果A [i]大于所有排序列表，那么内部循环不会迭代，j == i，并且A [i]不需要移动（所以只需继续外部循环）。

来源

2014-02-28 21:19:54 rcgldr

使用链表进行插入排序

回答

相关问题