带头结点的单链表实现快速、冒泡、直接插入/选择排序_插入hhh

结构体

typedef int ElemType;
typedef struct LNode {
	ElemType data;
	struct LNode* next;//指针域
}LNode, * LinkList;

快速排序

LinkList Quicksort(LinkList* listHead, LinkList* listTail)
{
	LNode* current;
	LNode* lessHead = NULL, * lessTail = NULL, * moreHead = NULL, * moreTail = NULL;
	current = (*listHead)->next;//每次取首节点为枢纽，current指向第二个节点用于遍历
	if ((*listHead)->next != NULL)//当链表节点数不为1时(说明链表未排好序)
	{
		for (current = (*listHead)->next; current; current = current->next)
		{
			if (current->data < (*listHead)->data)
			{
				if (lessHead == NULL)
					lessHead = current;
				else
					lessTail->next = current;
				lessTail = current;
			}//current结点key小于枢纽key时放入less链表
			else
			{
				if (moreHead == NULL)
					moreHead = current;
				else
					moreTail->next = current;
				moreTail = current;
			}//current结点key大于枢纽key时放入more链表
		}
		//根据枢纽结点将T链表分为less和more两个链表
		if (moreTail)
			moreTail->next = NULL;
		if (lessTail)
			lessTail->next = NULL;
		//将more链表尾结点next域置空
		if (moreHead != NULL)
		{
			moreTail->next = NULL;
			Quicksort(&moreHead, &moreTail);
			(*listHead)->next = moreHead;
			*listTail = moreTail;
		}
		//若moreHead不空，则current为more链表的尾结点，对more链表进行递归处理,将more链表接在枢纽节点后
		else
		{
			(*listHead)->next = NULL;
			*listTail = *listHead;
		}
		//若moreHead为空，则只有less链表(即结点key全小于枢纽)，将枢纽结点接在less节点后
		if (lessHead != NULL)
		{
			lessTail->next = NULL;
			Quicksort(&lessHead, &lessTail);
			lessTail->next = *listHead;
			*listHead = lessHead;
		}
		//若lesseHead不空，对less链表进行递归处理，再将枢纽节点接在less链表后
		else
		{
			lessHead = *listHead;
		}
		//若lesseHead为空，则枢纽结点作为首节点
		return lessHead;
	}
	else
		return *listHead;
}

直接插入排序

//直接插入排序
void Insertsort1(LinkList& L) {
	LNode* p = L->next, * q;
	LNode* r = p->next;
	p->next = NULL;
	p = r;
	while (p!=NULL)
	{
		r = p->next;
		q = L;
		while (q->next != NULL && q->next->data < p->data)
			q = q->next;
		p->next = q->next;
		q->next = p;
		p = r;
	}
}

冒泡排序

void  BubbleSort(LinkList &L)
{
	LNode* r, *t, *p;
	p = NULL;
 
	while (L->next->next != p)
	{
		r = L;
		t = L->next;
 
		while (t->next != p)
		{
			if (t->data > t->next->data)
			{
				r->next = t->next;
				t->next = t->next->next;
				r->next->next = t;
				t = r->next;
			}
			r = r->next;
			t = t->next;
		}
		p = t;
	}
 
}

直接选择

//选出最小值
LinkList MinList(LinkList &L) {
    LinkList minp = L,  p = L->next;//minp指向头结点
    while (p != NULL) {
        if ((minp->data) > (p->data)) {
            minp = p;
        }
        p = p->next;
    }
    return minp;
}
//遍历链表并调用上述算法（选出最小值）
void SortList(LinkList& L) {
    LNode* j, * r = L->next;//j指向链表中最小的结点，r指向链表的当前结点
    int temp;//用于交换位置，设数据为整数
    while (r->next != NULL) {
        j = MinList(r);
        if (j->data != r->data) {
            temp = r->data;
            r->data = j->data;
            j->data = temp;
        }
        r = r->next;//如果当前结点数据就是最小值直接后移一位
    }
}