最近在写一个学生管理系统，还没有写完就已经遇到了很多困难，也学到了很多，本文谨记录本人对链表排序的一些理解。

冒泡排序与直接排序

• 就冒泡排序与直接排序而言，链表与数相似，先比较两个变量的大小，再交换两个变量的内容。
• 交换的仅是变量所存的内容，链表(数组)的每个节点(元素)的位置关系不变。

 交换number1和number2后：

 改变的只是变量a和b的内容（number），a和b的位置关系没有改变。

•  比大小与数组完全一致，只需取出节点内的number进行比较，难点在于交换number。
• 如果一个节点中只储存一个number，可以直接将number取出进行交换。

#include<stdio.h>
#include<stdlib.h>
#define N 5
typedef struct node{
int number;
struct node* next;
}NODE;
int main()
{
int i;
NODE* head = (NODE*)malloc(sizeof(NODE));
head->next = NULL;
NODE* last = head;
//尾插法创建含有5个节点的链表
for (i = 0; i < N; i++)
{
NODE* p = (NODE*)malloc(sizeof(NODE));
scanf("%d", &p->number);
last->next = p;
last = p;
p->next = NULL;
}
//直接排序法从大到小进行排序
for (NODE* p = head->next; p->next; p = p->next)
for (NODE* q = p->next; q; q = q->next)
if (q->number > p->number)
{
int t = p->number;
p->number = q->number;
q->number = t;
}
//输出链表
for (NODE* p = head->next; p != 0; p = p->next)
printf("%d\n", p->number);
}

• 当一个节点内有很多内容时，如学生信息管理系统，一个节点包含姓名、成绩、学号等多个内容，如果把节点内的全部内容取出，然后交换，将十分麻烦。

为什么我们不直接通过结构体的赋值来进行节点的交换？因为结构体赋值会把节点的next也进行交换，会打乱节点相对位置，破坏掉整条链表。所以我们在结构体赋值之前，提前记录下所交换节点的next，既他们的位置关系，交换结束后，将他们的位置关系还原。

#include<stdio.h>
#include<stdlib.h>
#define N 5
typedef struct node{
int number;
struct node* next;
}NODE;
int main()
{
int i;
NODE* head = (NODE*)malloc(sizeof(NODE));
head->next = NULL;
NODE* last = head;
//尾插法创建含有5个节点的链表
for (i = 0; i < N; i++)
{
NODE* p = (NODE*)malloc(sizeof(NODE));
scanf("%d", &p->number);
last->next = p;
last = p;
p->next = NULL;
}
//直接排序法从大到小进行排序
for (NODE* p = head->next; p->next; p = p->next)
for (NODE* q = p->next; q; q = q->next)
if (q->number > p->number)
{
//提前记录p和q的next
NODE* p_next = p->next;
NODE* q_next = q->next;
//整体交换p和q
NODE t = *p;
*p = *q;
*q = t;
//将p和q的位置关系还原
p->next = p_next;
q->next = q_next;
}
//输出链表
for (NODE* p = head->next; p != 0; p = p->next)
printf("%d\n", p->number);
}

插入排序

• 链表和数组的插入排序差异较大，本质在于两者插入新节点(元素)的方式不同，数组需要整体后移，而链表只需改变节点的next。
• 数组仍不改变每个元素间的相对位置关系，只改变元素所包含的内容，而链表是整体搬家，改变的是节点间的位置关系。

重新排序后： 

不要在意我按照什么规则进行的排序，主要突出一个乱，重点在于理解他们的位置关系发生了变化。

• 插入排序的思路主要是，将链表分为两条，一条主链表等待被插入，一条从链表逐个插入到主链表中。
• 具体操作需要对两条链表都进行遍历，如果从链表中的某个节点没有找到位置可以插入，需要补在主链表的末尾。
• 所以我们需要两次嵌套的for循环进行遍历，需要一个flag记录节点是否成功插入。

#include<stdio.h>
#include<stdlib.h>
#define N 5
typedef struct node{
int number;
struct node* next;
}NODE;
int main()
{
int i;
NODE* head = (NODE*)malloc(sizeof(NODE));
head->next = NULL;
NODE* last = head;
//尾插法创建含有5个节点的链表
for (i = 1; i <= N; i++)
{
NODE* p = (NODE*)malloc(sizeof(NODE));
scanf("%d", &p->number);
last->next = p;
last = p;
p->next = NULL;
}
//插入排序法从大到小进行排序
//将原链表拆分成两个链表
NODE* p = head->next;
NODE* q = p->next;
p->next = NULL;
int flag = 0;
//将链表q逐一插入链表p中
for (NODE* r = q->next; q; q = r)
{
//flag为0说明q的节点还未插入链表p中
flag = 0;
//记录q的下一个节点
r = q->next;
for (NODE* last = head; p; last = p, p = p->next)
if (q->number > p->number)
{
//找到插入位置flag变为1
flag = 1;
q->next = p;
last->next = q;
break;
}
//我这里的起点有两个，p和last
//for循环可以帮我们复原last
//我们还需手动将p的位置复原
p = head->next;
//flag为0即该节点应补在链表p的末尾
if (flag == 0)
{
NODE* last = head;
//找到链表p的最后一个节点
while (last->next)
last = last->next;
last->next = q;
q->next = NULL;
}
}
//输出链表
for (NODE* p = head->next; p != 0; p = p->next)
printf("%d\n", p->number);
}

这个插入排序的代码不管是可读性还是执行效率都有可优化的空间，仅作为学习记录，随着本人的后续学习，可能会有完善。