排序，是数据结构中重要的一部分。今天做单链表的直接插入排序和简单选择排序。首先，先解决单链表的存储结构和创建单链表。单链表的结构：typedef struct list { int data; struct list * next; }list,*linklist; 单链表的创建（使用了引用，应为在创建链表的时候，头节点申请空间，头结点地址有变化，可以改为指针的指针）：void create(linklist &L,int n) { int i; linklist p; L = (linklist)malloc(sizeof(list)); L->next = NULL; for(i=0;i<n;i++) { p = (linklist)malloc(sizeof(list)); scanf("%d",&p->data); p->next = L->next; L->next = p; } }单链表的打印：void show(linklist L) { linklist p; p = L->next; while(p) { printf("%d ",p->data); p = p->next; } }--------------------------------俄是分界线------------------------------单链表的基本操作就已经完事了，接下来先看看直接插入排序。直接插入排序是一个稳定的排序，所谓稳定的排序就是假如待排数中有两个相同的数值，在排序后其先后关系保持不变。其时间复杂度平均为O（ ），空间复杂度为O（1）。直接插入法的思想是：默认首个数据是排序好的，在待排序表中拿出首个数据与 排序表进行比较，改变指针的指向进而进行排序，直到全部有序（由于是单链表，所以不能从后往前比较，只能从前往后比较，这点与存储结构是数组的直接插入法不一样）具体排序简析图void insertsort(linklist L) { linklist p,q,pre; p = L->next->next; L->next->next = NULL; while(p) { q = p->next; pre = L; while(pre->next != NULL && pre->next->data < p->data) pre = pre->next; p->next = pre->next; pre->next = p; p = q; } }----------------------------------俄也是分界线--------------------------------看完直接插入排序，那简单选择排序就更简单了。简单选择排序也是稳定的排序，其时间复杂度和空间复杂度和直接插入排序一样。简单选择排序思想：从头到尾进行扫描，找到最小的放在第一个位置，在从第二个位置进行第二次扫描，找到最小的，放在第二个位置，依次扫描，直到全部有序。简单选择排序简析图简单选择排序代码：linklist min(linklist p) { int da; linklist temp=p; da = p->data; p = p->next; while(p) { if(p->data < da) { temp = p; da = p->data; } p = p->next; } return temp; } void selectsort(linklist L) { linklist p,q; q = p = L->next; while(q) { p = min(p); int temp = p->data; p->data = q->data; q->data = temp; q = q->next; p = q; } }----------------------------俄还是分界线-----------------------实验结果：默认为输入五个数，显示两种排序的结果。实验结果-----------------------------俄真的是分界线---------------------------当然了，这两种排序算法时间复杂度还是挺高的，还有更快的排序算法，比如著名的快排，堆排，基排（多关键字排序），在今后的学习中会更新。至于存储结构是数组的，这两个排序算法写着就更简单了，本次就不写了。快考试了，哈哈，紧张紧张。
