双链表-＞直接插入写的有点乱 逃....

DuLinkList.h

typedef int Status;
typedef int ElemType;


typedef struct DuLNode{
	ElemType data;
	struct DuLNode* prior;
	struct DuLNode* next;

}DuLNode,  *  DuLinkList;

//当第i个元素存在 返回位置
DuLinkList  GetElem_L(DuLinkList, int);

//插入
Status ListInsert_DuL(DuLinkList ,int,ElemType);

//删除
Status ListDelete_DuL(DuLinkList ,int ,ElemType *);

//创建
void Create_DuL(DuLinkList *);

//直接插入排序 
void InsertSort(DuLinkList);

DuLinkList.c

#include<stdlib.h>
#include "./DuLinkList.h" 

//插入
Status ListInsert_DuL(DuLinkList  L, int i, ElemType e) {
	//获取插入位置
	DuLinkList p,s;
	p = GetElem_L(L, i);
	if (!p) { return -1;};
	//创建一个新节点
	s = (DuLinkList)malloc(sizeof(DuLNode));
	if (!s) { return -1; };
	s->data = e;
	//如果 p是头结点
	if (!p->next) {
		p->next = s;
		s->prior = p;
		s->next = NULL;
		return 0;
	}

	//插入操作
	s->prior = p->prior;
	p->prior->next = s;
	s->next = p;
	p->prior = s;
	return 0;
};

//删除
Status ListDelete_DuL(DuLinkList L, int i, ElemType* e) {
	//获取删除位置
	DuLinkList p, s;
	p = GetElem_L(L, i);
	if (!p) { return -1; };
	*e = p->data;
	p->prior->next = p->next;
	p->next->prior = p->prior;
	free(p);
	return 0;
};

//创建
void Create_DuL(DuLinkList* L) {
	 *L = (DuLinkList)malloc(sizeof(DuLNode));
	 (*L)->data = 0;
	 (*L)->next = NULL;
	 (*L)->prior = NULL;
};

//当第i个元素存在 返回位置
DuLinkList  GetElem_L(DuLinkList L, int i) {
	DuLinkList p;
	int j;
	j = 1;

	if (!L->next) { return L; };
	p = L->next;

	while (p && i>j)
	{
		++j;
		p = p->next;
	}
	if (i > j) {
		exit(0);
	}

	return p;

};

//直接插入排序 
void InsertSort(DuLinkList L) {

	//记录插入到的位置 
	DuLinkList poi;
	DuLinkList p;
	DuLinkList temp;

	poi = L->next;
	while (poi)
	{	
		temp = poi->prior;
		while (temp) {

			if (!temp->prior) {
				//移动到第一个位置的时候还没有比它小的数字则 插入到第一个位置
				p = poi->next;
				poi->prior->next = poi->next;
				poi->next->prior = poi->prior;
				poi->prior = temp;
				poi->next = temp->next; 
				temp->next->prior = poi;
				temp->next = poi;
				poi = p;
				break;
			}

			//如果小于就把它放在 temp的后面位置
			if (temp->data < poi->data) {
				if (poi->prior == temp) {
					poi = poi->next;
					break;
				}
				p = poi->next;
				//断开
				if (poi->next) {
					poi->prior->next = poi->next;
					poi->next->prior = poi->prior;
			
				}else {
					//最后一个结点的时候 断开操作
					poi->prior->next = NULL;
				}

				//插在后面
				poi->prior = temp;
				poi->next = temp->next;
				temp->next->prior = poi;
				temp->next = poi;
				poi = p;
				break;

			}
			temp = temp->prior;
		}

	}

};

Main.c

#include <stdio.h>
#include <stdlib.h>
#include "./DuLinkList.h"


int main() {
	DuLinkList l;
	Create_DuL(&l);

	ListInsert_DuL(l, 0, 1);
	ListInsert_DuL(l, 1, 2);
	ListInsert_DuL(l, 2, 3);
	ListInsert_DuL(l, 1, 6);
	ListInsert_DuL(l, 1, 7);
	ListInsert_DuL(l, 1, 7);
	ListInsert_DuL(l, 1, 7);
	ListInsert_DuL(l, 1, 20);
	ListInsert_DuL(l, 1, 0);
	ListInsert_DuL(l, 1, 16);
	ListInsert_DuL(l, 1, 9);
	ListInsert_DuL(l, 1, 3);

	DuLinkList p;
	p = l->next;
	while (p)
	{
		printf("%d\n", p->data);
		p = p->next;
	};

	ElemType e; 
	printf("delete=====================================\n");
	ListDelete_DuL(l,2,&e);
	printf("删除了：%d\n", e);
	printf("delete=====================================\n");
	p = l->next;
	while (p)
	{
		printf("%d\n", p->data);
		p = p->next;
	};

	printf("sort=====================================\n");
	InsertSort(l);
	p = l->next;
	while (p)
	{
		printf("%d\n", p->data);
		p = p->next;
	};

	return 0;
}

直接插入法
2 15871
12 5871
125 871
1257 81
12578 1
112578
每次保证前面是有序的 ，用后面的值在前面找合适的位置插入
最坏的情况每次都插入到第一个位置 从第二个元素开始比较次数
元素位置 比较次数
2 *************1
3 *************2
4 ************ 3
. ************** .
. ************** .
. **************.
n-1 *********** n-1
最坏情况时间复杂度
1+2+3+…n-1 ＝ (n-1)(1+n-1)/2 ＝ n(n-1)/2文章来源地址https://uudwc.com/A/dMya4