一个单链表的排序算法(选择排序,交换指针,gcc)

写了一个单链表的排序算法(选择排序,交换指针)

交换指针很是麻烦,而且效率也不高,需要经常排序的东西最好不要用链表来实现

 

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
 
 
struct student {
        int score;
        struct student *next;
};
 
 
struct student* create_link() {
 
        struct student *head = NULL;
        struct student *tail = NULL;
        int score;
        while(1) {
                scanf("%d", &score);
                if(score <= 0)break;
                struct student *now = (struct student*)malloc(sizeof(struct student));
                now->score = score;
                now->next = NULL;
                if(head == NULL) {
                        head = tail = now;
                } else {
                        tail->next = now;
                        tail = now;
                }
        }
        printf("create link success\n");
        return head;
}
 
void display_link(const struct student *link) {
 
        const struct student *p = link;
        for(; NULL;p=p->next) {
                printf("%d\t", p->score);
        }
        printf("\n");
}
 
//select sort and switch point instead of switch data

void sort_link(struct student **head) {
 
        struct student *link = *head;
 
        struct student *pre_p1;
        struct student *pre_p2;
        struct student *min;
 
        struct student *p1;
        for(p1=link; p1->next!=NULL; pre_p1=min,p1=min->next) {
                min = p1;
                struct student *p2;
                for(p2=p1; p2->next!=NULL; p2=p2->next) {
                        if(p2->next->score < min->score) {
                                pre_p2 = p2;
                                min = p2->next;
                        }
                }
                if(min == p1) {
                        printf("no need sort\n", p1->score);
                        continue;
                }
                //head or not head

                if(p1 == *head) {
                        *head = min;
                } else {
                        pre_p1->next = min;
                }
                //switch point

                struct student *temp = min->next;
                if(p1->next == min) { //p1 and min link directly

                        min->next = p1;
                        p1->next = temp;
                } else { //p1 and min link indirectly

                        min->next = p1->next;
                        pre_p2->next = p1;
                        p1->next = temp;
                }
 
                printf("sort:\t", p1->score);
                display_link(*head);
        }
}
 
int main() {
        struct student *link = create_link();
        sort_link(&link);
        printf("\nafter sort link:\n");
        display_link(link);
        return 0;
}