Day107 | 147.对链表进行插入排序 | 简单选择、冒泡、直接插入

Day107 | 147.对链表进行插入排序 | 简单选择、冒泡、直接插入

147. 对链表进行插入排序 - 力扣（LeetCode）

147题直接用插入排序就可以解决，只是想着顺手总结一下

简单选择排序

思路：

笔者的思路：比较简单粗暴，我新建一个链表res，然后遍历原来的链表head，找到一个最大值的结点的前驱结点p，就保存到temp中，然后把p->next节点删掉，然后就用头插法把temp->next插入新的链表res中

简单排序得知道已经排序过的序列的位置，而笔者用的是新创建的连接的虚拟头结点的res来表示已经排序好的序列的位置

也可以不用新的链表直接在原地修改，基本思路：

用sortedTail指针标记已经排序好的序列的最后一个节点

用四个指针进行标记，min标记最小值的节点，premin表示pre的前驱结点

cur用来遍历找最小值，precur表示cur的前驱结点和更新premin（有前驱结点好进行修改）

遍历过程中，如果cur的值比min的值小的话，就把min更新为cur

然后利用premin把min给删掉，把min给接到已排序链表的末尾，也就是sortedTail的后面

最后把sortedTail指针更新为min即可

完整代码：

笔者第一次写的代码

//简单选择排序
class Solution {
public:ListNode* sortList(ListNode* head) {//虚拟头结点ListNode *t=new ListNode;//用来返回的链表的虚拟头结点ListNode *res=new ListNode;t->next=head;//原来链表全都删除完毕代表排序结束while(t->next!=nullptr){int maxVal=INT_MIN;ListNode *p=t;//temp保存有最大值的节点，因为这个结点要从原来的链表中删除掉ListNode *temp=new ListNode;//找最大值while(p->next!=nullptr){if(p->next->val>maxVal){maxVal=p->next->val;temp=p;}p=p->next;}//删除原来的节点ListNode *add=temp->next;temp->next=temp->next->next;//插入到新的链表中add->next=res->next;res->next=add;}return res->next;}
};

在原地进行修改的代码

ListNode* selectionSort(ListNode* head) {ListNode dummy(0);                // 虚拟头节点dummy.next = head;ListNode *sortedTail = &dummy;   // 维护已排序部分的尾指针while (sortedTail->next) {        // 遍历未排序部分//这两个一个指向最小值节点，一个指向最小值节点的前驱结点ListNode *preMin = sortedTail, *minNode = sortedTail->next;//cur是用来遍历的指针，pre是cur的前驱节点，这两个是一起的ListNode *curr = minNode->next, *preCurr = minNode;// 寻找最小值节点及其前驱（时间复杂度O(n)）while (curr) {                // 遍历剩余未排序节点if (curr->val < minNode->val) {preMin = preCurr;     // 更新最小值前驱指针minNode = curr;       // 更新最小值节点指针}preCurr = curr;           // 前驱指针跟随移动curr = curr->next;        // 当前指针后移}// 将最小节点从原链表中移除preMin->next = minNode->next; // 断开原链// 将最小节点插入已排序链表的尾部minNode->next = sortedTail->next; // 保持未排序部分连接sortedTail->next = minNode;    // 插入到已排序末尾sortedTail = minNode;          // 更新尾指针}return dummy.next;
}

冒泡排序

太麻烦了不说了，大家自己看吧

ListNode* bubbleSort(ListNode* head) {if (!head || !head->next) return head;ListNode dummy(0);                // 虚拟头节点处理头指针变化dummy.next = head;bool swapped = true;ListNode* end = nullptr;          // 记录每轮冒泡的终止边界while (swapped) {swapped = false;ListNode *prev = &dummy;      // 前驱指针（关键修正点）ListNode *curr = prev->next;  // 当前指针while (curr->next != end) {   // 遍历至已排序边界前ListNode *next = curr->next;if (curr->val > next->val) {// 交换相邻节点（调整指针而非数据域）prev->next = next;     // 前驱连接下一节点curr->next = next->next;next->next = curr;// 更新标记和指针swapped = true;prev = next;          // 前驱指针后移} else {prev = curr;          // 无需交换则正常后移curr = curr->next;}}end = curr;                   // 更新排序边界}return dummy.next;
}

直接插入排序

这个比较好理解一些，直接插入排序就是先找插入位置，也就是下一次处理节点要插入到我们已经排序的子序列的哪里

用cur遍历要处理的结点，而因为我们要把cur所指向的结点插入到已经排好序的子序列中，所以要有一个next保存cur的next结点，否则处理完一个节点直接找不到后续节点了。而我们要找插入位置，那就是要在排好序的子序列中找到最后一个小于cur的结点，然后把cur插入到该节点的后面。

我们用pre表示这个结点，那么比较的时候就是pre->next->val和cur->val进行比较了，只有满足这个条件的时候pre才会往后移动，否则不移动

而while条件里面的pre->next不为nullptr对应的是cur的节点值大于已经排好序的子序列的全部的值

其余情况对应的是pre->next->val < curr->val

ListNode* insertionSort(ListNode* head) {ListNode dummy(0);                // 虚拟头节点ListNode *curr = head;            // 遍历原链表的指针while (curr) {                     // 逐个处理未排序节点ListNode *next = curr->next;   // 保存下一个待处理节点ListNode *pre = &dummy;        // 从虚拟头开始寻找插入位置// 寻找插入位置（时间复杂度O(n)）while (pre->next && pre->next->val < curr->val) {pre = pre->next;           // 移动至最后一个小于curr的节点}// 插入操作curr->next = pre->next;        // 将curr插入pre之后pre->next = curr;              // 更新前驱指针curr = next;                   // 处理下一个节点}return dummy.next;
}