[数据结构与算法]算法（插入排序顺序、单双链表实现）

（此算法通过C语言实现）

今天我们尝试用顺序结构和链式结构来实现我们的插入排序算法。

首先，什么是插入排序，可以理解成为需要在一块数组中划分为有序序列和无序序列，我们将无序序列中的一个个数拿出来，不断通过插入的方法把一个个数放到有序序列的合适位置中去，使得有序序列不断扩大，无序数列不断减小，最后使得整个数组成为一个有序序列。

算法图解

?这便是我们一开始插入排序的默认状态，接下来我们来看执行一次会出现怎么样的效果：

?我们能够直接了当的发现，之前排在 ‘3’ 后面的 ‘1’ 成功从无序区间进入了有序区间，实现了有序区间不断扩大，无序区间不断缩小的一小步，至于下一步无疑也是实现 ‘2’ 从无序到有序的小飞越。

我们一遍又一遍的执行，直到：

这也是最终我们想要的结果，整个数组变为有序区间，即整个数组排序完毕。

接下来便是代码实现环节：?

?顺序数组实现

?顺序数组实现的基本思想首先便是找到有序数组的最后一个元素，以及这个元素的后一个元素即待排元素。

int end = i;//已排好数组中最后的一个元素位置，处于开始状态时默认第一个元素已排好
int tem = arr[end + 1];//end元素的后一个元素即我们的待排元素

?然后我们所需要进行的操作，将待排元素找好位置进行插入。

具体实现流程便是待排元素向前比较，且元素后移为插入腾出位置，找到确切位置进行插入。

//顺序实现插入排序
void Insert_Sort2(int* arr, int len)
{
	for (int i = 0; i < len - 1; i++)
	{
		int end = i;//已排好数组中最后的一个元素位置，处于开始状态时默认第一个元素已排好
		int tem = arr[end + 1];//end元素的后一个元素即我们的待排元素
		while (end >= 0)
		{
			//待排元素与已拍数组内数组依次比较，向前迈步，若小于end处元素，伪指针end前移，
			//且将end处元素后置为待排元素腾出插入空间
			if (tem < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
				break;
		}
		//在这里一条语句实现了插入
		arr[end + 1] = tem;
	}
}

程序执行流程：

?一开始，我们便将待排元素拿出来，与前面元素进行比较

2比5小，仍然需要前移，将5向后赋值，腾出待插入位

2比3小继续前移，与1进行比较

2比1大，无需继续前进，将2插入原先预留的插入位中?

新的有序区间构成！

单链表实现

单链表定义一贯的手法

//单链表存储结构
typedef struct Node1 {
	int data;
	Node1* next;
}SLNode;

使用链表插入首先我们将数组传入，将每一个数组的待排元素依次给一个节点来进行插排。相当于我们将原数组看作无序序列，而将一次次插入元素的单链表作为有序序列。

//单链表插入排序
void Insert_Sort(int* arr, int len, SLNode* head)
{
	for (int i = 0; i < len; i++)
	{
		SLNode* p = head->next;
		SLNode* tem = head;
		SLNode* cur = (SLNode*)malloc(sizeof(SLNode));
		
        //出于安全目的加入判断
		if (cur)
		{
			cur->next = NULL;
			cur->data = arr[i];
		}
		else
		{
			printf("内存分配出错\n");
			return;
		}
		//若此链表中仅有头结点
		if (p == NULL)
		{
			head->next = cur;
			continue;
		}
		while (p != NULL)
		{
			//若p已到达尾结点,与尾结点进行比较
			if (p->next == NULL)
			{
				//若大于尾结点元素直接向后插入
				if (cur->data > p->data)
				{
					p->next = cur;
					break;
				}
				//若小于尾结点向前插入
				else
				{
					tem->next = cur;
					cur->next = p;
					break;
				}
			}
			//若未到达尾结点
			else
			{
				//若当前元素大于p所指元素，则p指针后移
				if (cur->data > p->data)
				{
					tem = p;
					p = p->next;
				}
				//若当前元素小于p所指元素，则向前插入
				else
				{
					tem->next = cur;
					cur->next = p;
					break;
				}
			}
		}
	}
}

双向链表实现

之前我们在交换过程中需要用到向前插入的手法，而这需要一个tem变量来记录前一结点的位置，倘若使用能够找到直接前驱的双向链表结构会产生什么样的效果呢？?

简简单单的双向链表标准手法?

//双向链表存储结构
typedef struct Node2 {
	int data;
	Node2* last;
	Node2* next;
}DouSLNode;

与单链表完全相同的思路

//双向链表插入排序
void Insert_Sort1(int* arr, int len, DouSLNode* Douhead)
{
	for (int i = 0; i < len; i++)
	{
		DouSLNode* p = Douhead->next;
		DouSLNode* cur = (DouSLNode*)malloc(sizeof(DouSLNode));
		if (cur != NULL)
		{
			cur->data = arr[i];
			cur->last = NULL;
			cur->next = NULL;
		}
		else
			return;

		//如果仅有头结点
		if (Douhead->next == NULL)
		{
			Douhead->next = cur;
			cur->last = Douhead;
			continue;
		}
		//插入排序具体操作
		while (p != NULL)
		{
			//若p已到达尾结点,与尾结点进行比较
			if (p->next == NULL)
			{
				//若大于尾结点元素直接向后插入
				if (cur->data > p->data)
				{
					p->next = cur;
					cur->last = p;
					break;
				}
				//若小于尾结点向前插入
				else
				{
					p->last->next = cur;//原先p所指的上一元素后继指针修改为待插入元素
					cur->last = p->last;//待插入元素前驱指针修改为p处的上一元素
					cur->next = p;//待插入元素后继修改为p处
					p->last = cur;//将p处前驱修改为cur
					break;
				}
			}
			//若待排元素大于当前元素
			if (cur->data > p->data)
				//移步下一位
				p = p->next;
			//小于当前元素，p前插入
			else
			{
				p->last->next = cur;//原先p所指的上一元素后继指针修改为待插入元素
				cur->last = p->last;//待插入元素前驱指针修改为p处的上一元素
				cur->next = p;//待插入元素后继修改为p处
				p->last = cur;//将p处前驱修改为cur
				break;
			}
		}
	}

?实验全部代码（供以调试）

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

//单链表存储结构
typedef struct Node1 {
	int data;
	Node1* next;
}SLNode;

//双向链表存储结构
typedef struct Node2 {
	int data;
	Node2* last;
	Node2* next;
}DouSLNode;


//单链表插入排序
void Insert_Sort(int* arr, int len, SLNode* head)
{
	for (int i = 0; i < len; i++)
	{
		SLNode* p = head->next;
		SLNode* tem = head;
		SLNode* cur = (SLNode*)malloc(sizeof(SLNode));
		
		if (cur)
		{
			cur->next = NULL;
			cur->data = arr[i];
		}
		else
		{
			printf("内存分配出错\n");
			return;
		}
		//若此链表中仅有头结点
		if (p == NULL)
		{
			head->next = cur;
			continue;
		}
		while (p != NULL)
		{
			//若p已到达尾结点,与尾结点进行比较
			if (p->next == NULL)
			{
				//若大于尾结点元素直接向后插入
				if (cur->data > p->data)
				{
					p->next = cur;
					break;
				}
				//若小于尾结点向前插入
				else
				{
					tem->next = cur;
					cur->next = p;
					break;
				}
			}
			//若未到达尾结点
			else
			{
				//若当前元素大于p所指元素，则p指针后移
				if (cur->data > p->data)
				{
					tem = p;
					p = p->next;
				}
				//若当前元素小于p所指元素，则向前插入
				else
				{
					tem->next = cur;
					cur->next = p;
					break;
				}
			}
		}
	}
}

//双向链表插入排序
void Insert_Sort1(int* arr, int len, DouSLNode* Douhead)
{
	for (int i = 0; i < len; i++)
	{
		DouSLNode* p = Douhead->next;
		DouSLNode* cur = (DouSLNode*)malloc(sizeof(DouSLNode));
		if (cur != NULL)
		{
			cur->data = arr[i];
			cur->last = NULL;
			cur->next = NULL;
		}
		else
			return;

		//如果仅有头结点
		if (Douhead->next == NULL)
		{
			Douhead->next = cur;
			cur->last = Douhead;
			continue;
		}
		//插入排序具体操作
		while (p != NULL)
		{
			//若p已到达尾结点,与尾结点进行比较
			if (p->next == NULL)
			{
				//若大于尾结点元素直接向后插入
				if (cur->data > p->data)
				{
					p->next = cur;
					cur->last = p;
					break;
				}
				//若小于尾结点向前插入
				else
				{
					p->last->next = cur;//原先p所指的上一元素后继指针修改为待插入元素
					cur->last = p->last;//待插入元素前驱指针修改为p处的上一元素
					cur->next = p;//待插入元素后继修改为p处
					p->last = cur;//将p处前驱修改为cur
					break;
				}
			}
			//若待排元素大于当前元素
			if (cur->data > p->data)
				//移步下一位
				p = p->next;
			//小于当前元素，p前插入
			else
			{
				p->last->next = cur;//原先p所指的上一元素后继指针修改为待插入元素
				cur->last = p->last;//待插入元素前驱指针修改为p处的上一元素
				cur->next = p;//待插入元素后继修改为p处
				p->last = cur;//将p处前驱修改为cur
				break;
			}
		}
	}
}

//顺序实现插入排序
void Insert_Sort2(int* arr, int len)
{
	for (int i = 0; i < len - 1; i++)
	{
		int end = i;//已排好数组中最后的一个元素位置，处于开始状态时默认第一个元素已排好
		int tem = arr[end + 1];//end元素的后一个元素即我们的待排元素
		while (end >= 0)
		{
			//待排元素与已拍数组内数组依次比较，向前迈步，若小于end处元素，伪指针end前移，
			//且将end处元素后置为待排元素腾出插入空间
			if (tem < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
				break;
		}
		//在这里一条语句实现了插入
		arr[end + 1] = tem;
	}
}

void Show_LinkList(SLNode* head)
{
	assert(head != NULL);
	if (head == NULL)
	{
		printf("传入结点为空\n");
		return;
	}

	SLNode* p = head->next;
	while (p != NULL)
	{
		printf("%d ", p->data);
		p = p->next;
	}
}
void Show_LinkList(DouSLNode* head)
{
	assert(head != NULL);
	if (head == NULL)
	{
		printf("传入结点为空\n");
		return;
	}
	DouSLNode* p = head->next;
	while (p != NULL)
	{
		printf("%d ", p->data);
		p = p->next;
	}
}

//释放单链表堆区内存
void FREE(SLNode* head)
{
	assert(head != NULL);
	if (head == NULL)
	{
		printf("传入结点为空\n");
		return;
	}

	SLNode* p = head->next->next;
	SLNode* tem = head->next;

	while (p != NULL)
	{
		free(tem);
		tem = p;
		p = p->next;
	}
	printf("\n内存已安全释放\n");
}

//释放双向链表堆区内存
void FREE(DouSLNode* head)
{
	assert(head != NULL);
	if (head == NULL)
	{
		printf("传入结点为空\n");
		return;
	}

	DouSLNode* p = head->next->next;

	while (p != NULL)
	{
		if (p->next == NULL)
		{
			free(p);
			break;
		}

		free(p->last);
		p = p->next;
	}
	printf("\n内存已安全释放\n");
}

void Show_Order(int* arr, int len)
{
	for (int i = 0; i < len; i++)
		printf("%d ", arr[i]);
	
}

int main()
{
	//构建单双向链表头结点、头指针
	SLNode headNode;
	DouSLNode DouheadNode;
	SLNode* head = &headNode;
	DouSLNode* Douhead = &DouheadNode;

	int arr[] = { 2,8,5,3,1,9,4,6,0,7 };
	//int arr[] = { 1,4,3,2 };
	head->next = NULL;
	Douhead->last = NULL;
	Douhead->next = NULL;

	printf("\n单链表插入排序\n");
	Insert_Sort(arr,sizeof(arr) / sizeof(arr[0]), head);
	Show_LinkList(head);
	FREE(head);

	printf("\n双向链表插入排序\n");
	Insert_Sort1(arr, sizeof(arr) / sizeof(arr[0]),Douhead);
	Show_LinkList(Douhead);
	FREE(Douhead);
	//free(Douhead);

	printf("\n顺序数组插入排序\n");
	Insert_Sort2(arr, sizeof(arr) / sizeof(arr[0]));
	Show_Order(arr, sizeof(arr) / sizeof(arr[0]));

	return 0;
}

（如有问题，欢迎指正）