数据结构基础链表的插入排序程序

本是古典何须时尚 2022-08-04 15:52 104阅读 0赞

1.问题描述

链表的插入排序程序

2.测试用例

链表元素依次为：0、1、2 以及 大数；

3.链表的插入排序算法思想

3.1 判检原链表可否实现排序；

3.2 进入循环插入函数：

3.2.1 复制链表当前结点；

3.2.2 删除链表当前结点；

3.2.3 插入链表当前结点；

4.链表小注

4.1 创建链表之前不要给头结点分配内存空间（避免空链表）；

4.2 创建链表时，两指针梭形前进；

4.3 传入排序函数的是链表变量的地址；

5.源码实现

#include<iostream>
    #include<stdio.h>
    #include<math.h>
    
    using namespace std;
    
    typedef struct LinkNode
    {
    	int data;
    	LinkNode *next;
    }LinkNode;
    
    void InsertSort(LinkNode **phead)
    {	
    	// 链表非法 或者 链表元素数目 小于 2 不排序
    	if(phead==NULL||*phead==NULL||(*phead)->next == NULL)
    		return;
    	LinkNode *pCur = *phead;
    	int i = 0;
    	for(;pCur->next!=NULL;) 
    	{
    		// 拿出一个待插入结点
    		LinkNode *pNode = new LinkNode;
    		pNode->data = pCur->next->data;
    		pNode->next = NULL;
    		// 寻找结点插入的位置
    		LinkNode *tmp = *phead;
    		// 插入头结点，此时 pCur 不移动
    		if((*phead)->data>pNode->data)
    		{
    			pNode->next = *phead;
    			*phead = pNode;
    			LinkNode *DelNode = pCur->next;
    			pCur->next = pCur->next->next;
    			delete DelNode;
    			DelNode = NULL;
    			continue;
    		}
    		else
    		{
    			// 尾插
    			if(pNode->data>=pCur->data)
    			{
    				pCur = pCur->next;
    				continue;
    			}
    			// 乱入
    			else
    			{
    				while(tmp!=pCur&&tmp->next->data<=pNode->data)
    					tmp = tmp->next;
    				pNode->next = tmp->next;
    				tmp->next = pNode;
    				LinkNode *DelNode = pCur->next;
    				pCur->next = pCur->next->next;
    				delete DelNode;
    				DelNode = NULL;
    			}
    		}		
    	}
    }
    
    #define Num 10 // 迭代次数不要超过32，避免位溢出
    int main() {
    	int i=0;
    	LinkNode *mylink = NULL; // 链表可能为空，不提前给空间
    	LinkNode *ptr1,*ptr2 = NULL;
    	for(i=0;i<Num;i++)
    	{	
    		if(mylink == NULL)
    		{
    			mylink = new LinkNode;
    			ptr1 = mylink;
    		}
    		ptr1->next = NULL;
    		if(i%3 == 0)
    			ptr1->data = 3;
    		else
    			ptr1->data = 5+pow(-2,i+1);
    		ptr2 = ptr1;
    		ptr1 = ptr1->next;
    		ptr1 = new LinkNode;
    		ptr2->next = ptr1;
    	}
    	if(mylink!=NULL)
    		ptr2->next = NULL;
    	InsertSort(&mylink);
    	LinkNode *tmp = mylink;
    	for(i=0;i<Num;i++)
    	{
    		cout<<tmp->data<<endl;
    		tmp = tmp->next;
    	}
    	return 0;
    }

6.后记

6.1 链表之事，画图之事，未图未知，奈何奈何 ！！！

6.2 为什么 \*\*phead ？

因为可能会修改头指针，如果头指针修改不是对指向地址的的指针赋值的时候，赋值给单纯的地址头指针将导致无功而返，当然，如果确信不会修改头指针，那么就无所谓啦！！！

6.3 TFhiirnskt ！！！

6.4 二分插入排序源码：

#include<iostream>
    #include<stdio.h>
    #include<math.h>
    
    using namespace std;
    
    void InsertSort(int *a,int Num)
    {	
    	if(Num < 2)
    		return;
    	for(int i=1;i<Num;i++)
    	{
    		int tmp = a[i];
    		int high = i-1;
    		int low = 0;
    		while(high>=low)
    		{
    			int mid = (high+low)/2;
    			if(a[mid]<=tmp)
    				low = mid+1;
    			else
    				high = mid-1;
    		}
    		for(int j = i;j>high+1;j--)
    			a[j] = a[j-1];
    		a[j] = tmp;
    	}
    	return ;
    }
    
    #define Num 5 
    int main() {
    	int a[] = {11,3,3,2,2,4,5};
    	InsertSort(a,Num);
    	for(int i=0;i<Num;i++)
    		cout<<a[i]<<endl;
    	return 0;
    }