插入排序

插入排序回顾

我们先回顾一下对数组的插入排序，其步骤大致为:
先将第一个数据元素看作是一个有序序列，后面的 n-1 个数据元素看作是未排序序列。对后面未排序序列中的第一个数据元素在这个有序序列中进行从后往前扫描，找到合适的插入位置并插入到其中，每次有序序列的长度 +1。

重复这样的操作，将每个未排序序列中的元素插入到当前有序序列中合适的位置。直到未排序序列长度为 0，最后得到一个完整的有序序列，即为排序的结果。

之前写过插入排序的随笔，更多详情点这里 插入排序

单向链表的插入排序

单向链表插入排序原理

对于链表的插入排序，原理和普通的插入排序是差不多的。不过要注意的是，在单向链表中，由于链表只能正向遍历，所以在寻找某个节点的合适插入位置时，只能从前向后扫描。

在单向链表插入排序的过程中，我们将前面看成有序链表，将有序链表和无序链表分离，将后面无序链表中的节点不断插入到有序链表中。
我们用 node 来标记当前待排序的节点，由于插入排序过程中将有序链表和无序链表进行了分离，所以还需要一个 nex 来标记下一个待排序节点。同时还需要 pre 用于在有序链表中扫描寻找合适插入位置。

单向链表插入排序步骤

单向链表插入排序的大致步骤为：

（1）先将单个节点 node 的 next 置NULL，形成初始有序链表；
（2）pre 在有序链表中扫描，nex 标记下一个待排序节点，当 pre 的 next 指向的节点大于等于 node->data 时停止；
（3）在有序链表中插入节点 node；
（4）将 node 指向之前暂存的下一个待排序节点 nex，重复步骤（2）（3）。

单向链表插入排序图解

待排序的单向链表

单向链表插入排序核心代码

//插入排序
void InsertSort(Linklist *head){
    if(!head->next) return;
    Linklist *node = head->next, *nex = node->next, *pre;
    node->next = NULL;    //单个节点形成初始有序链表
    node = nex;

    while(node){
	pre = head;       //pre在有序链表中找到何时插入位置
	nex = node->next; //暂存下一个待排序节点
	//找到何时插入位置，pre指向有序链表中最后一个小于node的节点
	while(pre->next && pre->next->data < node->data)
		pre = pre->next;
	//表中插入
	node->next = pre->next;
	pre->next = node;
	node = nex;       //node指向下一个待排序节点
    }
}

完整程序

完整程序源代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int Elemtype;        //数据类型
typedef struct Node {

	Elemtype data;           //结构体数据域
	struct Node *next;       //结构体指针域

} Linklist;

//链表的初始化
Linklist* Initial_linklist(){
	//向系统申请内存
	Linklist *head = (Linklist *)malloc(sizeof(Linklist));
	head->next = NULL;
	return head;
}

//创建初始链表  采用尾插法
void Create_linklist(Linklist *head, int n) {    //头节点(不带数据)
	Linklist *node, *end;                        //普通节点 尾节点
	end = head;                                  //当链表为空时 头尾指向同一个节点
	printf("创建链表输入 %d 个元素:", n);
	for (int i = 0; i < n; i++) {                //n为插入普通节点的个数
		node = (Linklist *)malloc(sizeof(Linklist));
		scanf("%d", &node->data);
		end->next = node;                        //当前end的next指向了新节点node
		end = node;                              //end往后移，此时新的节点变成尾节点
	}
	end->next = NULL;                            //end最后置NULL
}

//打印链表
void Show_linklist(Linklist *head) {
	Linklist *t = head->next;					 //t为遍历指针 访问每个节点数据
	if (t == NULL)
		puts("链表为空");

	while (t != NULL) {
		printf("%d ", t->data);
		t = t->next;
	}
	printf("\n\n");
}

//插入排序
void InsertSort(Linklist *head){
	if(!head->next) return;
	Linklist *node = head->next, *nex = node->next, *pre;
	node->next = NULL;    //单个节点形成初始有序链表
	node = nex;

	while(node){
		pre = head;       //pre在有序链表中找到何时插入位置
		nex = node->next; //暂存下一个待排序节点
		//找到何时插入位置，pre指向有序链表中最后一个小于node的节点
		while(pre->next && pre->next->data < node->data)
			pre = pre->next;
		//表中插入
		node->next = pre->next;
		pre->next = node;
		node = nex;       //node指向下一个待排序节点
	}
}

int main(){
	Linklist *mylist;
	mylist = Initial_linklist();

	Create_linklist(mylist, 10);
	printf("初始状态链表:\n");
	Show_linklist(mylist);

	InsertSort(mylist);
	printf("插入排序后的链表:\n");
	Show_linklist(mylist);
}

程序测试结果