插入排序函数不会在排序后列出所有元素

Question

这是我的插入排序函数：

Student *sort(Student* node) 
{ 
    if (node == NULL || !node->next)
        return node;
    Student *sorted = NULL; 
    while (node != NULL) 
    { 
        Student  *head = node; 
        Student **tail = &sorted; 

        node = node->next;

        while (!(*tail == NULL || head->id < (*tail)->id))
        { 
            tail = &(*tail)->next; 
        }
        head->next = *tail;
        *tail      = head;
    }
    return sorted;
}

因此，如果这应该对 3.3、3.1 和 3.8 进行排序，它会将它们排序为：

3.3 3.8

我不知道第一个元素发生了什么。如果我给它更大的一组文本进行排序，它会漏掉几乎一半的文本。

一直在试图弄清楚为什么会这样。我很确定这是我的排序功能的问题。

写函数。此函数应该只是将排序后的结果写入文件：

 void write(Student* node) { 

  Student * curr = NULL; 
  curr = node;
  FILE *ptr = fopen("student_out.txt", "w");
  if (curr == NULL) 
    { 
      printf("Nothing to list. \n");
      exit(1);
    } 
  int i=0;
  while(curr !=NULL) { 
     fprintf(ptr,"%d, %s, %s, %s, %.2f\n", curr->id, curr->firstname,     curr->lastname, curr->major, curr->gpa);
      curr = curr -> next;   
 } 
return;
}

Answer 1

似乎可以，问题可能出在打印输出上。测试上述案例的示例代码，已转换为 C89 兼容（因为我使用的是 Visual Studio）。我会交换名称 head 和 node，但我将它们保留原样以匹配原始示例。我还更改了比较以在 (*tail)->id > head->id 时停止（在比较中使用 <= 而不是 <），以便保留 "equal" 节点的原始顺序。

#include <stdio.h>

typedef struct Student_{
struct Student_ *next;
double id;
}Student;

Student *sort(Student* node) 
{ 
Student *sorted = NULL; 
Student **tail;
Student *head;
    if (node == NULL || !node->next)
        return node;
    while (node != NULL) 
    { 
        head = node; 
        node = node->next;
        tail = &sorted; 
        while (*tail != NULL && (*tail)->id <= head->id)
            tail = &(*tail)->next; 
        head->next = *tail;
        *tail      = head;
    }
    return sorted;
}

int main()
{
Student a[3] = {{&a[1],3.3},{&a[2],3.1},{NULL,3.8}};
Student *b;

    b = sort(a);
    while(b){
        printf("%3.1lf ", b->id);
        b = b->next;
    }
    printf("\n");
    return 0;
}

插入排序函数不会在排序后列出所有元素

Insertion Sort functions doesn't list all the elements after sorting

c

sorting

linked-list

insertion-sort