成绩排序（练习链表）

（图片别看错了，右边的是输出样例）

前几天学了学链表，也把一些ADT格式敲了敲，但是还是没有实际用过

然后就选了一道排序题，顺便试了试插入排序

以前只知道有插入排序这个东西，但是用数组实现的话感觉效率会偏低，现在知道链表之后就知道该怎么玩了（乐）

代码如下：

#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef struct LNode{
	ElemType data;
    ElemType ID;
	struct LNode * next;
}LinkList;

LinkList * creat(int n)
{
	LinkList * head, * node, * end;//定义头节点，普通节点，尾部节点
	head = (LinkList *)malloc(sizeof(LinkList));//分配地址
	end = head;
	for(int i = 0; i < n; i++)
	{
		node = (LinkList *)malloc(sizeof(LinkList));//分配地址
		scanf("%d%d", &node->ID, &node->data);
		end->next = node;
		end = node;
	}
	end->next = NULL;//结束创建
	return head;
}//创建长度为n的链表
void DestroyList(LinkList * head)
{
	LinkList * end = head;
	do
	{
		end = end->next;
		free(head);
		head = end;
	}while(end != NULL);
	return;
}//销毁链表

int main(void)
{
    int N;
    scanf("%d", &N);
    LinkList * head = creat(1);
    //插入排序
    for(int i = 1; i < N; i++)
    {
        int t_ID, t_data;
        scanf("%d%d", &t_ID, &t_data);
        for(LinkList * node = head->next, * f_node = head; 1; node = node->next, f_node = f_node->next)
        {
            if(node == NULL || t_data > node->data || (t_data == node->data && t_ID < node->ID))
            {
                LinkList * tmp = (LinkList *)malloc(sizeof(LinkList));
                f_node->next = tmp, tmp->next = node;
                tmp->data = t_data, tmp->ID = t_ID;
                break;
            }
        }
    }
    //输出
    int tmp = 1, count = 1;
    for(LinkList * node = head->next, * f_node = head; 1; )
    {
        printf("%d %d %d\n", tmp, node->ID, node->data);
        node = node->next, f_node = f_node->next;
        if(node == NULL)  break;
        else
        {
            count++;
            if(f_node->data > node->data)  tmp = count;
        }
    }
    DestroyList(head);

    return 0;
}

效率还是比较高的（不知道是不是我的错觉），对1000个数据进行排序的时间不超过8ms

一些废话：

昨天晚上上思政课，差点给我干昏过去，整什么课上辩论赛，还要提问，太抽象了，我一个理科生看着马院等等院的大佬在那边讲什么因然，什么实然。能不能对我这种不对哲学有一点点兴趣的绯雾温柔点，md我看算法书都惊心胆颤

辩题是有没有普适（世）性的价值观，在那边咬文嚼字

简单来说不就是证明存在性的问题嘛，那坚持存在的一方举出例子，反方争辩不存在不就行了（doge）

所以说这种东西就是不如高数让我感觉脚踏实地，果然我不是学文科的料