单链表排序之直接插入排序

2021年1月15日 133点热度 0条评论 来源: John__xs

****单链表排序之直接插入排序****

/*前段时间刚学会几种排序方法,最近学习了单链表,就用来试试,本篇链表的排序方法<一>讲述的是单链表的直接插入排序;(注意:请仔细看准节点结构体的包装和头指针的包装再阅读以下代码);



直接插入排序的思想和直接插入排序数组的方法,我都已经在直接插入排序的文章中介绍了;



直接插入排序链接http://blog.csdn.net/bitboss/article/details/51576115



//这里直接复用直接插入排序单链表



在我现在所知的几个排序中,直接插入排序应该算是最难理解的吧;如果我分析的不够清晰,还请海涵;



 pLinkNode unfirst = NULL;//定义一个无序结点指针;
 pLinkNode cur = NULL;//用来表示有序链表的结点指针;
 pLinkNode inNode = NULL;//找到的可以插入的结点
 pLinkNode front = NULL;//用来保存指向可以插入结点位置的指针;




思路分析: 按照直接插入排序的算法思想,我们先假定链表的第一个结点是有序的序列,那么剩余的结点我们假设为无序的,从第二个结点,即无序链表的第一个结点开始,和有序结点开始比较,如果找到比无序结点大的有序结点,即找到可以插入的位置,跳出循环,则将当前指向的无序结点插入当前有序结点之前,即:front->next = inNode; inNode = cur;或者没有找到比无序结点大的有序节点,则将当前指向的front是有序结点的最后一个结点,无序结点尾插到有序链表;即:front->next = inNode; inNode = cur;此时cur = NULL;等于是尾插;如果链表是第一个节点比当前无序结点大,则头插;即:pList->pHead = inNode; inNode = cur;



理解起来比较生涩,建议多阅读几遍代码!
*/



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

typedef int DataType;

typedef struct LinkNode
{
	DataType data;
	struct LinkNode* next;
}LinkNode,*pLinkNode;//结点结构体

typedef struct LinkList
{
	LinkNode* pHead;//头结点指针
}LinkList ,*pLinkList;//链表


算法实现:


void InsertSort(pLinkList pList)
{
	pLinkNode unfirst = NULL;//定义一个无序结点指针;
	pLinkNode cur = NULL;//用来表示有序链表的结点指针;
	pLinkNode inNode = NULL;//找到的可以插入的结点
	pLinkNode front = NULL;//用来保存指向可以插入结点位置的指针;

	assert(pList);
	
	if(pList->pHead == NULL)
		return ;
	cur = pList ->pHead;//有序链表的头指针;
	unfirst = cur ->next ;//无序链表从第二个结点开始;
	cur->next = NULL;//当前有序结点只保存第一个结点;

	while(unfirst)//直到链表最后一个结点结束;
	{
		inNode = unfirst;//每次从一个新的无序结点开始;
		cur = pList ->pHead ;
		//而有序结点则从第一个开始,因为是有序的,我们以升序为例,则有序链表是从小到大排列;
		//即每次从最小的开始比较;如果比当前最小的还小放在它前面;

		while(cur && cur->data < inNode->data )
		{ //如果比当前有序结点大,则和下一个有序结点比较;
			front = cur; 
			cur = cur->next ;
		}

		unfirst = unfirst ->next ;//指向下一个无序结点;

		if(cur == pList ->pHead )//即比第一个有序结点还小,就是还没进入循环内部就跳出来了,则头插;
			pList ->pHead = inNode;
		else
			front->next = inNode;//是进入循环内部后或者循环结束跳出;

		inNode->next = cur;//
	}

}


写的不好,请多多指教!

    原文作者:John__xs
    原文地址: https://blog.csdn.net/bitboss/article/details/51606392
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。