插入排序

快速排序

归并排序

冒泡排序

插入排序

对应letecode链接：
力扣

题目描述：

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

进阶：

你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

主要介绍一下快速排序，归并排序，插入排序，冒泡排序：

插入排序：

解题思路：
链表与数组的插入排序不同，数组支持随机访问。而链表是不支持随机访问的。我们在数组中可以随意的前后移动，将指针指向值和新元素的值比较后，将新元素插入到合适的位置。我们知道链表查询元素的时间复杂度为 O（n）,我们只能够通过遍历链表查询元素。那么我们怎么才能将新元素放到合适的位置呢？

我们可以将第一个节点从链表中取下来构造一个新的链表：

将剩余的节点插入到1这个节点之中插入分为3种情况：

1.头插

2.中间插入

3.尾插

过程： 

情况1：
1.如果取链表的节点插入到新的链表中如果要插入的节点比新链表的头节点还要小此时我们只需要将这个节点头插到新链表中即可

此时cur指向的节点对应val的值小于newhead所对应的val值此时将其头插即可也就是：cur->next=newhead;newhead=cur;

但是我们将cur的next指向newhead了就找不到后面的节点。所以我们需要定义一个变量next保存下一个节点

情况二：

当cur的val比newhead的val要小并且是在中间插入时我们需要定义一个变量newheadcur和newheadprev变量新链表通过比较值找到对应的插入位置

将其插入进去即可

情况三：
cur所在节点对应的值比新链表的值都要大这是就要进行尾插

对应代码：

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
                 if(!head||!head->next){//空节点或者只有一个节点直接返回即可
                     return head;
                 }
            ListNode*cur=head->next;//遍历剩下的节点
            ListNode*newhead=head;
             head->next=nullptr;//将第一节点从链表中取下
            while(cur){
            ListNode*next=cur->next;//保存下一节点
            //头插
             if(cur->val<newhead->val){
                 cur->next=newhead;
                 newhead=cur;
             }else{
                ListNode*newheadcur=newhead->next;
                ListNode*newheadprev=newhead;
                //遍历新链表
                while(newheadcur){
                    //找到插入位置
                     if(newheadcur->val>cur->val){
                            newheadprev->next=cur;//链接
                            cur->next=newheadcur;
                            break;//插入完成结束循环
                     }else{
                          newheadprev=newheadcur;
                          newheadcur=newheadcur->next;
                     }
                }
                //尾插
                if(newheadcur==nullptr){
                    newheadprev->next=cur;
                    cur->next=nullptr;//防止成环
                }
             }
               cur=next;
            }
            return newhead;

    }
};

 快速排序

解题思路：
很多老铁可能想说链表怎么快速排序链表只能正着走不能够倒着走怎么使用快速排序其实快速排序的前后指针法是不涉及下标的：

如果不清楚的老铁可以去看一下我的排序博客

具体步骤：

我们可以选取头节点作为基准值，遍历链表，将比它小的节点头插在它前面，比它大的节点尾插在它后面
假设smallHead维护的是小于基准值的头插指针，greaterHead维护的是大于等于基准值的尾插指针
则一次对[head , end）快排结束后有
-[ smallHead , head ) （左闭右开）是小于基准值的一部分
-[ head->next , end ) （左闭右开）是大于等于基准值的一部分
再分治这两部分即可

对应代码：

class Solution {
public:
    ListNode* sortList(ListNode* head) {
         return quick_sortListNode(head,nullptr);
    }
    ListNode*quick_sortListNode(ListNode*head,ListNode*end){
                 if(head==end||head->next==end){
                      return head;//一个节点或者没有节点返回head即可
                 }
                 ListNode*smallHead=head;
                 ListNode*greaterHead=head;
                 ListNode*cur=head->next;
                 int key=head->val;
                 //选取第一个值做key
                 while(cur!=end){
                 ListNode*next=cur->next;//保存cur的下一个节点
                 //头插
                 if(cur->val<key){
                     cur->next=smallHead;
                     smallHead=cur;
                 }else{
                      greaterHead->next=cur;
                      greaterHead=greaterHead->next;
                 }
                 cur=next;
        }
            greaterHead->next=end;//链接最后一个节点
          //递归两部分
          ListNode*ans=quick_sortListNode(smallHead,head);
          head->next=quick_sortListNode(head->next,end);
          return ans;
    }
};

归并排序

解题思路：
归并排序，逃脱不了，分合。 思路如下：

分割 -> 通过递归不断分割链表，在此过程中需要保证链表不丢失的情况下，不断想下切割 （e.g. 8 -> 4 -> 2）
关键在于找到链表的中心点， 并从中心点将链表分割成 2 部分。
我们可以使用经典的快慢双指针链表分割方法，其中有个点需要注意，链表长度为奇偶，切割处理方式是不同的，这里根据大家喜欢的方式处理即可，这里没有明确规定必须使用什么切割方式，笔者的切换策略如下：
快指针每次移动 2 步，慢指针每次移动 1​​ 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
找到中点后，将链表进行断开，将当前链表分成 2 部分
对两个链表分别排序，慢指针的下一节点，指向空即可
分割阶段结束 -> 递归退出 -> 直到分割的链表长度为 1。此时递归到底了
merge 环节，退出递归的过程中，不断的排序合并merge 节点，其实包含在分割阶段里边，merge -> 排序当前链表。

对应分割链表代码：

ListNode*splitListNode(ListNode*head){
        if(!head||!head->next)return head;
        ListNode*slow=head;
        ListNode*fast=head;
        ListNode*prev=nullptr;
        while(fast&&fast->next){
            prev=slow;
            fast=fast->next->next;
            slow=slow->next;
        }

        return prev;
    }

注意中间那个节点要分给对分割的第二段链表

如果只有两个节点的话，slow指向的就是第二个节点。如果将其分给第一个合并的链表那么就会死循环！！！！ 

合并链表对应代码：

ListNode*mergeListNode(ListNode*head1,ListNode*head2){
            ListNode*dummyHead=new ListNode(-1);
            ListNode*ans=dummyHead;
              while(head1&&head2){
                  if(head1->val<=head2->val){
                      ans->next=head1;
                      ans=ans->next;
                      head1=head1->next;
                  }
                  else{
                      ans->next=head2;
                      ans=ans->next;
                      head2=head2->next;
                  }
              }
              if(head1)ans->next=head1;
              if(head2)ans->next=head2;
              return dummyHead->next;
       }

上面的操作都在之前的链表博客里面解释过了如果不太清楚的老铁可以去看一下我之前的博客

总代码：

class Solution {
public:
    ListNode*splitListNode(ListNode*head){
        if(!head||!head->next)return head;
        ListNode*slow=head;
        ListNode*fast=head;
        ListNode*prev=nullptr;
        while(fast&&fast->next){
            prev=slow;
            fast=fast->next->next;
            slow=slow->next;
        }

        return prev;
    }

     ListNode*mergeListNode(ListNode*head1,ListNode*head2){
            ListNode*dummyHead=new ListNode(-1);
            ListNode*ans=dummyHead;
              while(head1&&head2){
                  if(head1->val<=head2->val){
                      ans->next=head1;
                      ans=ans->next;
                      head1=head1->next;
                  }
                  else{
                      ans->next=head2;
                      ans=ans->next;
                      head2=head2->next;
                  }
              }
              if(head1)ans->next=head1;
              if(head2)ans->next=head2;
              return dummyHead->next;
       }

    ListNode* sortList(ListNode* head) {
               if(!head||!head->next)return head;
               ListNode*mid=splitListNode(head);
               ListNode*midNext=mid->next;
               mid->next=nullptr;
               //化分链表
               ListNode*head1=sortList(head);
             ListNode*head2= sortList(midNext);
          return mergeListNode(head1,head2);
    }
   
};

 冒泡排序

冒泡排序就比较简单了在这里就直接给出代码：

对应代码：

void  BubbleSort(struct Node* headNode)
{
	struct Node* firstNode = headNode->next;
	struct Node* secondNode = headNode;
	while (firstNode != NULL)
	{
		while (firstNode->next != NULL)
		{
			if (firstNode->data > firstNode->next->data)
			{
				int temp = firstNode->data;
				firstNode->data = firstNode->next->data;
				firstNode->next->data = temp;
			}
			firstNode = firstNode->next;
		}
		//减少排序次数
		firstNode = secondNode->next;
		secondNode = firstNode;
	}

}

如果觉得不错的老铁可以点个赞