【21天考研算法带刷leetcode-147】链表的直接插入排序、简单选择排序、冒泡排序（8/21）

附 力扣 链接https://leetcode.cn/problems/insertion-sort-list/随着专业课难度的增加，算法题目有同时考察多种操作的趋势，作为基础操作之一的链表排序可能最为专业课大题中的一部分来考察。

实现对不带头结点的链表进行排序，下文介绍两种方法：

一、直接插入排序

工作指针一趟遍历，但期间需要第二个while循环确定插入的位置。链表的题目关键在于实现逻辑闭环。

struct ListNode* insertionSortList(struct ListNode* head){
    struct ListNode* p=head->next;
    struct ListNode* head2=(struct ListNode*)malloc(sizeof(struct ListNode));//head2虚拟头节点
    head2->next=head;
    head->next=NULL;//要返回的头节点，尾指针设空
    while(p!=NULL)   {
        struct ListNode* q=head2;
        struct ListNode* temp=p->next;
        while(q->next!=NULL&&p->val>q->next->val){//q是确定直接插入位置的工作指针
            q=q->next;
        }
        p->next=q->next;
        q->next=p;
        p=temp;
    }
    return head2->next;
}

二、简单选择排序

简单选择排序的实现要复杂得多，总体的思想是每次每次选择最小的进行尾插法，而不用确定插入位置，但是因为涉及到每次遍历都要从头到尾，趟数相对要变多，第二涉及到当head结点需要被更改的时候，第三跟直接插入排序【while里的if语句】一样，涉及从链表中取下结点。

struct ListNode* insertionSortList(struct ListNode* head){
    struct ListNode* p=head;
    struct ListNode* head2=(struct ListNode*)malloc(sizeof(struct ListNode));//采用带虚拟头结点的尾插法
    struct ListNode* tail=head2;
    int min=INT_MAX;
    while(p!=NULL){
        min=p->val;//先让首结点作为min
        struct ListNode* min_pre=p; 
        while(p->next!=NULL){
            if(p->next->val<min){
                min_pre=p;
                min=p->next->val;        //找到最小结点的前驱
            }
            p=p->next;
        }
        
        if(min==head->val){ p=head->next; tail->next=head; head->next=NULL;tail=tail->next; head=p;continue;}


        tail->next=min_pre->next;
        min_pre->next=min_pre->next->next;
        tail=tail->next;
        p=head;
    }
    //tail->next=NULL;
    return head2->next;
}

三、链表的冒泡排序（待补充）

注释①：
1.因为通常情况下来说，我们都不知道链表的结点个数，所以需要去计算出来做为循环的次数，如果知道的话，那也可以直接传入参数作为count。
2.为什么不直接用 p！=NULL 作为循环的次数呢，因为在交换后结点会混乱，接下来我会解释。
注释②
1.这里为什么要采用tail作为下一步操作的重要点呢，因为如果直接通过p，和q操作，很容易重复循环了，但如果通过tail进行操作的话，结点始终不会有问题

当排序完成后，进行tail = tail- >next；此时tail就是下一个结点，p和q只要按照tail的结点走，就不会出问题。

所以我们借用tail这个结点，就可以达到跟数组的冒泡排序一样的操作。

void BubbleSort(NODE * &L)
{
	int i ,count = 0, num;//count记录链表结点的个数，num进行内层循环，
	NODE *p, *q, *tail;//创建三个指针，进行冒泡排序
	p = L;
	while(p->next != NULL)//计算出结点的个数
	{
		count++;//注释①
		p = p->next;
	}
	for(i = 0; i < count - 1; i++)//外层循环，跟数组冒泡排序一样
	{
		num = count - i - 1;//记录内层循环需要的次数，跟数组冒泡排序一样，
		q = L->next;//令q指向第一个结点
		p = q->next;//令p指向后一个结点
		tail = L;//让tail始终指向q前一个结点，方便交换，也方便与进行下一步操作
		while(num--)//内层循环 次数跟数组冒泡排序一样
		{
			if(q->data > p->data)//如果该结点的值大于后一个结点，则交换
			{
				q->next = p->next;
				p->next = q;
				tail->next = p;
			}
			tail = tail->next;//注释②
			q = tail->next;//注释②
			p = q->next;//注释②
		 } 
	} 
}