leetcode之hot100---148排序链表（C++）

题目要求将一个无序的链表按照升序返回，涉及排序算法，下面对每个排序算法进行回顾

一、交换排序

1.冒泡排序

算法思想：反复比较相邻的两个元素，将它们中较大的（或较小的）元素逐步“冒泡”到数组的末尾。整个过程会多次遍历数组，直到数组完全有序。

以该题中示例一为例（升序排列）：

假设我们要对链表4 - > 2 - > 1 - > 3进行排序。

步骤：

第一轮

1. 比较 4 和 2，发现 4  > 2，交换，链表变为2 - > 4 - > 1 - > 3。
2. 比较 4 和 1，发现 4  > 1，交换，链表变为2 - > 1 - > 4 - > 3。
3. 比较 4 和 3，发现 4  > 3，交换，数组变为2 - > 1 - > 3 - > 4。

第二轮

1. 比较 2 和 1，发现 2  > 1，交换，链表变为1 - > 2 - > 3 - > 4。
2. 比较 2 和 3，不交换。
3. 比较 3 和 4，不交换。

经过多轮操作，最终数组变为 1 - > 2 - > 3 - > 4。

复杂度：

• 时间复杂度：当表完全逆序时，需进行n - 1轮比较，每一轮需要处理 n - 1 个节点，因此时间复杂度为O(n²)；当表完全正序时，只需要一轮比较，无需交换节点，就可以完成排序， 因此时间复杂度为O(n)
• 空间复杂度：O(1)

代码如下：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* sortList(ListNode* head) {//冒泡排序//链表为空，返回空值if(head == nullptr){return nullptr;}//链表中只有一个节点，就返回头节点if(head->next == nullptr){return head;}//设置一个哨兵节点，用于返回排序后的链表ListNode* sentry = new ListNode(0, head);//从头节点开始开始冒泡排序//由于一次冒泡排序可能无法让所有节点回到正确的位置//因此可能需要进行多次冒泡，//每轮冒泡后，如果没有发生交换（swapped == false），则退出循环bool swapped;do{//标记是否进行交换swapped = false;ListNode* pre = sentry;ListNode* cur = sentry->next;//一轮循环while(cur->next){ListNode* nxt = cur->next;//只有前一节点的值比下一临近节点的值大才会产生交换节点的操作//交换完节点后需要修改前驱节点的后继指针//由于已经发生交换，cur不需要更新if(cur->val > nxt->val){cur->next = nxt->next;nxt->next = cur;pre->next = nxt;swapped = true;}//如果两节点未进行交换，那么需更新curelse{cur = cur->next;}//修改前驱节点pre = pre->next;}}while(swapped == true);return sentry->next;}
};

2.快速排序 

算法思想：

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

• 从数列中挑出一个元素，称为 “基准”（pivot）；
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

以该题中示例一为例（升序排列）：

假设我们要对链表4 - > 2 - > 1 - > 3进行排序（挖空法）。

步骤：

第1轮交换：

选择基准节点（pivot）——节点4

将基准值提取，位置留空

       

比较 4 和 3 , 3 < 4, 交换位置

比较 4 和 2 , 2 < 4, left指针向后移动

比较 4 和 2 , 2 < 4, left指针向后移动

left, right指针重合，将pivot归位

第2轮交换：

选择基准节点（pivot）——节点3

后续步骤和第一轮交换类似，因此下述只展示过程，不做具体描述

继续从头遍历链表，发现没有发生交换的节点，上述结果就是链表排序的最终结果

复杂度：

• 时间复杂度：最好情况： O(n log n)，选择的基准值使分区基本平衡

                             最坏情况： O(n²)，选择的基准值使分区完全不平衡

• 空间复杂度：O(logn)

基于链表的快排算法写了很久也没写出可以完美满足快排思想的，关键是涉及头尾交换，在单链表的限制下，需要考虑很多细节，实在是写不出了，暂且告一段落把！

但是在写的过程中了解到了快排的三种思想（之前只了解挖坑法），以下三种方法的详细解释可以参考快排的三种思路：

1.挖坑法： 

• 选取起始位置的元素作为基准值(pivot)，将该位置视为第一个"坑"
• 从右向左遍历：
  • 寻找小于基准值的元素
  • 找到后填入左边的"坑"中
  • 此时右边的位置变成新的"坑"
• 从左向右遍历：
  • 寻找大于基准值的元素
  • 找到后填入右边的"坑"中
  • 此时左边的位置变成新的"坑"
• 重复上述遍历的步骤，直到左右指针相遇
• 将基准值填入最后的"坑"位置
  • 此时基准值左边都是小于它的元素
  • 基准值右边都是大于它的元素

2.首尾指针法：

• 选择最左边的元素作为基准值
• 维护两个指针分别从两端向中间移动
• 位于尾部的指针从右向左找第一个小于基准值的数
• 位于头部的指针从左向右找第一个大于基准值的数
• 记录基准值的位置，不断交换直到两个指针交错
• 递归处理左右两个子区间

3.单向遍历双指针指针法：

• 选择第一个元素作为基准值(mid)
• 使用slow（遍历链表）和fast（寻找交换节点）两个指针标记区间
• 使用slow遍历数组时：
  • 如果当前元素大于基准值，fast从slow的下一位置继续遍历，寻找第一个小于基准值的节点，与slow交换
  • 如果当前元素小于等于基准值，slow右移
• 如果slow找不到对应的fast与之交换，那么最后基准值放到slow位置
• 递归处理左右两部分

二、选择排序

1.简单选择排序

算法思想：先在数据中找出最大或最小的元素，放到序列的起始；然后再从余下的数据中继续寻找最大或最小的元素，依次放到排序序列中，直到所有数据样本排序完成。

以该题中示例一为例（升序排列）：

假设我们要对链表4 - > 2 - > 1 - > 3进行排序。

步骤：

第一次遍历链表

        最小节点为1，插入链表头部，链表变为 1 - > 4 - > 2 - > 3。

        其中，已排序：1 ；待排序：  4 - > 2 - > 3

第二次遍历链表

        最小节点为2，插入链表头部，链表变为 1 - > 2 - > 4 - > 3。

        其中，已排序：1- > 4  ；待排序：  2 - > 3

第三次遍历链表

        最小节点为1，插入链表头部，链表变为 1 - > 2 - > 3 - > 4。

        其中，已排序：1 - > 2 - > 3 ；待排序：3

第四次遍历链表

        最小节点为4，插入链表头部，链表变为 1 - > 2 - > 3 - > 4。

        其中，已排序： 1 - > 2 - > 3 - > 4

复杂度：

• 时间复杂度：O(n²)（最坏和平均情况下）
• 空间复杂度：O(1)

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* sortList(ListNode* head) {//选择排序//链表为空或者只有一个节点，返回空值if(head == nullptr || head->next == nullptr){return head;}//设置一个哨兵节点，用于返回排序后的链表ListNode* sentry = new ListNode(0, head);//已排序部分的尾节点，方便插入ListNode* tail = sentry;//多轮遍历，tail左侧为排好序的链表，右侧为待排序的链表while(tail->next){ListNode* minPre = tail;//指向最小节点前驱的指针，初始时指向已排序部分的尾节点ListNode* curPre = tail;//指向正在遍历节点的前驱，初始时指向已排序部分的尾节点ListNode* cur = tail->next;//指向当前正在遍历的节点，初始时指向为已排序部分尾节点的后继ListNode* min = cur;//指向当前正在遍历的节点，初始时指向当前正在遍历的节点while(cur){/*如果当前遍历到的节点的值小于之前保存的节点的值，就更新对应指针*/if(cur->val <= min->val){min = cur;minPre = curPre;}/*移动遍历的指针和其前驱*/curPre = curPre->next;cur = cur->next;}/*如果遍历到待排序部分的最小节点，就将其插入已排序部分的尾部*/if(minPre != tail){minPre->next = min->next;//将原节点从原来位置删除/*将最小节点插入已排序链表的尾部*/min->next = tail->next;tail->next = min;}//修改已排序部分的尾节点tail = tail->next;  }//返回排序后的链表return sentry->next;}
};

PS:这段代码废了我好大的牛劲，因为题目要求是链表，在写代码的时候要注意很多细节的地方

比如：

1.为了安全断开链表，防止形成环结构 （遍历链表时cur指针）

• 在链表分区的过程中，我们将节点从原链表中移动到 headLow 或 headHigh 链表中。如果直接操作指针而不断开当前节点的 next 指针，可能会导致链表中的某些部分形成 环。
• 环的形成会导致后续的递归调用和遍历无法结束（例如，遍历时会陷入死循环），从而引发 堆栈溢出 或 无限循环。

2.确保正确分区，避免递归出错(pivot后继)

• 在递归中，pivot 是基准节点，不属于左右两部分。
• 如果 pivot->next 未设置为 nullptr，基准节点可能会错误地连接到右部分链表（headHigh），导致后续递归时 pivot 被错误地再次分区。
• 这会导致递归无法正确终止，从而引发 堆栈溢出。

 2.选择排序之堆排序

算法思想：从最后一个非叶子节点开始 建堆 ，自下而上进行堆调整 ， 确保父节点大于子节点。 将堆顶元素与末尾元素交换，提取堆顶元素，堆的大小减1，对新的堆顶进行调整，重复上述步骤直到堆空

以该题中示例一为例（升序排列）：

假设我们要对链表4 - > 2 - > 1 - > 3进行排序。

初始节点形成的完全二叉树：

从最后一个非叶子节点（2）开始建立大顶堆，根节点与叶子节点进行比较(3>2，交换)，调整大顶堆

继续处理下一个非叶子节点（4），4>3，不用交换

交换最后一个叶子节点（2）和根节点（4），同时根据上述方法调整大顶堆

交换最后一个叶子节点（1）和根节点（3），调整大顶堆，提取根节点，使用尾插法与排好序的数字进行排序

重复上述步骤，最终获得排好序的链表：

复杂度：

• 时间复杂度：建堆：对于高度为 i 的节点，向下调整的代价是 O(i)在高度为 i 的层次上，节点数最多为 n/2^(i+1)，总代价 = ∑(i=0 到 h) (节点数 × 调整代价) = ∑(i=0 到 h) (n/2^(i+1)) × i；取出堆顶并调整：需要进行 n-1 次操作，每次取出堆顶后，需要从根节点开始向下调整，调整过程是和左右子节点比较，选择较大(大顶堆)或较小(小顶堆)的交换，最坏情况下要调整到叶子节点，树的高度是 logn，所以每次调整是 O(logn)，n-1 次调整总共是 O(nlogn)，总体时间复杂度：T(n) = O(n) + O(nlogn)，取较大的量级，最终复杂度是 O(nlogn)
• 空间复杂度：O(logn)

代码待更新 

三、插入排序

1. 直接插入排序

算法思想：

• 将数组分为已排序和未排序两部分
• 从未排序部分取一个元素，插入到已排序部分的合适位置

以该题中示例一为例：

假设我们要对链表4 - > 2 - > 1 - > 3进行排序。（升序）

复杂度：

• 时间复杂度：O(n²)
• 空间复杂度：O(1)

代码如下：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* sortList(ListNode* head) {if(head == nullptr || head->next == nullptr){return head;}ListNode* sentry = new ListNode(-9999, head);//设置哨兵节点，后继指向头节点ListNode* tail = head;//确定已排序界限，默认第一个节点时已经排好序的ListNode* cur = head->next;//遍历待排序序列的指针while(cur){//保存下一个待处理节点的位置ListNode* nxt = cur->next;//如果待排序节点的值大于已排序链表中所有节点的值，直接插在已排序链表的尾部if(cur->val >= tail->val){tail = cur;}//否则就遍历已排序链表，寻找可以插入的位置else{ListNode* pre = sentry;ListNode* target = sentry->next;//从已排序好的子链表中进行遍历，寻找可以插入的位置while(target != cur && target->val <= cur->val){pre = target;target = target->next;}//执行插入操作cur->next = target;pre->next = cur;tail->next = nxt;}cur = nxt;}ListNode* ans = sentry->next;delete sentry;//释放哨兵节点return ans;}
};

2.希尔排序

算法思想：

• 将待排序序列分成若干子序列（按间隔分组）
• 对每个子序列进行直接插入排序
• 逐步缩小间隔直到为1

对链表进行希尔排序比较复杂，因为链表不能像数组那样直接通过索引访问元素。

假设要对数组 [8, 9, 1, 7, 2, 3, 5, 4, 6] 进行排序：

1.初始化间隔序列(gap)：

    n = 9      gap = n/2 = 4 (向下取整)

2.第一轮排序 (gap = 4):
   将数组分成若干组，每组间隔为4:

   组1: [8, 2]         位置 0,4

   组2: [9, 3]         位置 1,5

   组3: [1, 5]         位置 2,6

   组4: [7, 4, 6]         位置 3,7,8

对每组进行插入排序：

组1: [8, 2]  -> [2, 8]

组2: [9, 3] -> [3, 9]

组3: [1, 5] -> [1, 5]

组4:[7, 4, 6] -> [4, 6, 7]

排序后数组变为：[2, 3, 1, 4, 8, 9, 5, 6, 7]（同组数字用同一颜色标注）

3.第二轮排序 (gap = 2):

组1: [2, 1, 8, 5]         位置 0,2,4,6

组2: [3, 4, 9, 6, 7]         位置 1,3,5,7,8

对每组进行插入排序：

组1: [2,1,8,5]-> 1,2,5,8

组2: [3,4,9,6,7] -> 3,4,6,7,9

排序后数组变为：[1, 3, 2, 4, 5, 6, 8, 7, 9]

4.最后一轮排序 (gap = 1):

此时就是普通的插入排序，比较相邻元素

[1, 3, 2, 4, 5, 6, 8, 7, 9]

处理2： 1,2,3,4,5,6,8,7,9

处理7： 1,2,3,4,5,6,7,8,9

最终得到有序数组：[1, 2, 3, 4, 5, 6, 7, 8, 9]

复杂度：

• 时间复杂度：最坏情况（完全逆序）：O(n²)

                             最好情况（近似有序）：O(nlogn)

• 空间复杂度：O(1)

代码待更新 

四、归并排序

算法思想：

1. 分解：将数组递归拆分成两半
2. 解决：递归排序两个子数组
3. 合并：将已排序的子数组合并成一个有序数组

以数组[38, 27, 43, 3, 9, 82, 10]为例

第一步：分解过程

第二步：合并过程

复杂度

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

代码如下：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public://公共接口ListNode* sortList(ListNode* head) {return sortList(head, nullptr);}//函数的重载ListNode* sortList(ListNode* head, ListNode* tail){//如果递归到链表为空，就返回头指针if(head == nullptr){return head;}//如果链表中只有一个节点，就要将这个节点作为一个独立的子链表返回。if(head->next == tail){head->next = nullptr;return head;}//使用快慢指针寻找链表中点ListNode* slow = head;ListNode* fast = head;while(fast != tail){slow = slow->next;fast = fast->next;//为了防止fast指针处理链表长度为偶数的情况时访问空指针if(fast != tail){fast = fast->next;}}ListNode* mid = slow;//mid所指向节点作为第二部分的头结点return merge(sortList(head, mid), sortList(mid, tail));}//边排序边合并ListNode* merge(ListNode* head1, ListNode* head2){//哨兵节点，方便返回链表ListNode* dummyHead = new ListNode(0);ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;//合并两个有序链表while(temp1 && temp2){if(temp1->val <= temp2->val){temp->next = temp1;temp1 = temp1->next;}else{temp->next = temp2;temp2 = temp2->next;}temp = temp->next;}//处理剩余节点if(temp1){temp->next = temp1;}if(temp2){temp->next = temp2;}ListNode* ans = dummyHead->next;delete dummyHead;return ans;}
};

五、基数排序

算法思想：

1. 将整数按位数切割，从最低位开始排序
2. 每一位采用计数排序的思想进行处理
3. 每一轮排序都基于上一轮的结果
4. 直到所有位数都排序完成

六、计数排序

算法思想：

1. 找出数组的最大值和最小值
2. 创建计数数组，统计每个元素出现的次数
3. 根据计数数组构建结果数组

假设数组为 [4, 2, 2, 8, 3, 3, 1]：

第一步：找出最大值和最小值

min = 1 max = 8 需要大小为 8-1+1 = 8 的计数数组

第二步：统计每个数字出现次数

数字 1 2 3 4 5 6 7 8

次数 1 2 2 1 0 0 0 1

索引 0 1 2 3 4 5 6 7

第三步：重构数组

原始数组：[4, 2, 2, 8, 3, 3, 1]

排序后： [1, 2, 2, 3, 3, 4, 8]

七、桶排序

1. 创建一定数量的桶（通常是数组或链表）
2. 将数据分散到各个桶中
3. 对每个桶内部进行排序
4. 将所有桶中的数据按顺序合并

非线性时间比较类排序算法总结

排序方法	时间复杂度（平均）	时间复杂度（最坏）	时间复杂度（最好）	空间复杂度	稳定性
冒泡排序	O(n²)	O(n²)	O(n)	O(1)	稳定
快速排序	O(nlogn)	O(n²)	O(nlogn)	O(logn)	不稳定
简单选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)原地 O(log n)栈	不稳定
插入排序	O(n²)	O(n²)	O(n)	O(1)	稳定
希尔排序	O(nlogn)	O(n²)	O(nlogn)	O(1)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定

线性时间非比较类排序算法总结

排序方法	时间复杂度（平均）	时间复杂度（最坏）	时间复杂度（最好）	空间复杂度	稳定性
基数排序	O(n*k)	O(n*k)	O(n*k)	O(n+k)	稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(n+k)	稳定
桶排序	O(n+k)	O(n²)	O(n)	O(n+k)	稳定