c - 如何在 C 中使用此代码使用插入排序对列表进行排序？

Question

我在排序给定值时遇到了一些问题。现在，输入文件是:

347 490 950 779 911 825 215 584 355 266 301 458 381 13 577 835

但我得到:

835 577 13 381 458 301 266 355 584 215 825 911 779 950 490 347

我如何使用我在 Insert() 中的代码按升序对这些进行排序？

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Node for building our linked list.
struct NodeTag {
  int value;
  struct NodeTag *next;
};

typedef struct NodeTag Node;

Node *insert( Node *head, int val )
{
  Node *n = (Node *)malloc(sizeof(Node)); 
  n->value = val;
    n->next = head;
      return n;
}

int main()
{
  Node *head = NULL;

  int x;
  while ( scanf( "%d", &x ) == 1 ){
    head = insert( head, x );
  }

  for(Node *n = head; n; n = n->next) {
     printf("%d ", n->value);
  }

  printf("\n");

  while(head) {

   Node *next = head->next;
     free(head);
        head = next;
   }
   return 0;
}

如有任何帮助，我们将不胜感激。谢谢!

Answer 1

您在列表的头部插入每个元素，因此它们的顺序与您阅读它们的顺序相反。这不是插入排序。

当你插入到列表中时，你需要将新元素按正确的顺序放入。当您找到一个节点，使得新值大于当前节点的值但小于下一个节点的值时，您将新节点插入当前节点和下一个节点之间。

如果小于头节点，则将其设为新的头节点。如果大于结束节点，则放在最后。