链表排序（冒泡、选择、插⼊、快排、归并、希尔、堆排序）这篇⽂章分析⼀下链表的各种排序⽅法。
以下排序算法的正确性都可以在LeetCode的这⼀题检测。本⽂⽤到的链表结构如下（排序算法都是传⼊链表头指针作为参数，返回排序后的头指针）
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
插⼊排序（算法中是直接交换节点，时间复杂度O（n^2），空间复杂度O（1））数组和链表
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
if(head == NULL || head->next == NULL)return head;
ListNode *p = head->next, *pstart = new ListNode(0), *pend = head;
pstart->next = head; //为了操作⽅便，添加⼀个头结点
while(p != NULL)
{
ListNode *tmp = pstart->next, *pre = pstart;
while(tmp != p && p->val >= tmp->val) //到插⼊位置
{tmp = tmp->next; pre = pre->next;}
if(tmp == p)pend = p;
else
{
pend->next = p->next;
p->next = tmp;
pre->next = p;
}
p = pend->next;
}
head = pstart->next;
delete pstart;
return head;
}
};
选择排序（算法中只是交换节点的val值，时间复杂度O（n^2），空间复杂度O（1））
class Solution {
public:
ListNode *selectSortList(ListNode *head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
//选择排序
if(head == NULL || head->next == NULL)return head;
ListNode *pstart = new ListNode(0);
pstart->next = head; //为了操作⽅便，添加⼀个头结点
ListNode*sortedTail = pstart;//指向已排好序的部分的尾部
while(sortedTail->next != NULL)
{
ListNode*minNode = sortedTail->next, *p = sortedTail->next->next;
//寻未排序部分的最⼩节点
while(p != NULL)
{
if(p->val < minNode->val)
minNode = p;
p = p->next;
}
swap(minNode->val, sortedTail->next->val);
sortedTail = sortedTail->next;
}
head = pstart->next;
delete pstart;
return head;
}
};
快速排序1（算法只交换节点的val值，平均时间复杂度O（nlogn），不考虑递归栈空间的话空间复杂度是O（1））
这⾥的partition我们参考(选取第⼀个元素作为枢纽元的版本，因为链表选择最后⼀元素需要遍历⼀遍)，具体可以参考
这⾥我们还需要注意的⼀点是数组的partition两个参数分别代表数组的起始位置，两边都是闭区间，这样在排序的主函数中：void quicksort(vector<int>&arr, int low, int high)
{
if(low < high)
{
int middle = mypartition(arr, low, high);
quicksort(arr, low, middle-1);
quicksort(arr, middle+1, high);
}
}
对左边⼦数组排序时，⼦数组右边界是middle-1，如果链表也按这种两边都是闭区间的话，到分割后枢纽元middle，到middle-1还得再次遍历数组，因此链表的partition采⽤前闭后开的区间（这样排序主函数也需要前闭后开区间），这样就可以避免上述问题
class Solution {
public:
ListNode *quickSortList(ListNode *head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
//链表快速排序
if(head == NULL || head->next == NULL)return head;
qsortList(head, NULL);
return head;
}
void qsortList(ListNode*head, ListNode*tail)
{
//链表范围是[low, high)
if(head != tail && head->next != tail)
{
ListNode* mid = partitionList(head, tail);
qsortList(head, mid);
qsortList(mid->next, tail);
}
}
ListNode* partitionList(ListNode*low, ListNode*high)
{
//链表范围是[low, high)
int key = low->val;
ListNode* loc = low;
for(ListNode*i = low->next; i != high; i = i->next)
if(i->val < key)
{
loc = loc->next;
swap(i->val, loc->val);
}
swap(loc->val, low->val);
return loc;
}
};
快速排序2（算法交换链表节点，平均时间复杂度O（nlogn），不考虑递归栈空间的话空间复杂度是O（1））
这⾥的partition，我们选取第⼀个节点作为枢纽元，然后把⼩于枢纽的节点放到⼀个链中，把不⼩于枢纽的及节点放到另⼀个链中，最后把两条链以及枢纽连接成⼀条链。
这⾥我们需要注意的是，1.在对⼀条⼦链进⾏partition时，由于节点的顺序都打乱了，所以得保正重新组合成⼀条新链表时，要和该⼦链表的前后部分连接起来，因此我们的partition传⼊三个参数，除了⼦链表的范围（也是前闭后开区间），还要传⼊⼦链表头结点的前驱；
2.partition后链表的头结点可能已经改变
class Solution {
public:
ListNode *quickSortList(ListNode *head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
//链表快速排序
if(head == NULL || head->next == NULL)return head;
ListNode tmpHead(0); = head;
qsortList(&tmpHead, head, NULL);
;
}
void qsortList(ListNode *headPre, ListNode*head, ListNode*tail)
{
//链表范围是[low, high)
if(head != tail && head->next != tail)
{
ListNode* mid = partitionList(headPre, head, tail);//注意这⾥head可能不再指向链表头了
qsortList(headPre, headPre->next, mid);
qsortList(mid, mid->next, tail);
}
}
ListNode* partitionList(ListNode* lowPre, ListNode* low, ListNode* high)
{
/
/链表范围是[low, high)
int key = low->val;
ListNode node1(0), node2(0);//⽐key⼩的链的头结点，⽐key⼤的链的头结点
ListNode* little = &node1, *big = &node2;
for(ListNode*i = low->next; i != high; i = i->next)
if(i->val < key)
{
little->next = i;
little = i;
}
else
{
big->next = i;
big = i;
}
big->next = high;//保证⼦链表[low,high)和后⾯的部分连接
little->next = low;
low->next = ;
lowPre->next = ;//为了保证⼦链表[low,high)和前⾯的部分连接
return low;
}
};
归并排序（算法交换链表节点，时间复杂度O（nlogn），不考虑递归栈空间的话空间复杂度是O（1））
⾸先⽤快慢指针的⽅法到链表中间节点，然后递归的对两个⼦链表排序，把两个排好序的⼦链表合并成⼀条有序的链表。归并排序应该算是链表排序最佳的选择了，保证了最好和最坏时间复杂度都是nlogn，⽽且它在数组排序中⼴受诟病的空间复杂度在链表排序中也从O(n)降到了O(1)
class Solution {
public:
ListNode *mergeSortList(ListNode *head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
//链表归并排序
if(head == NULL || head->next == NULL)return head;
else
{
//快慢指针到中间节点
ListNode *fast = head,*slow = head;
while(fast->next != NULL && fast->next->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
}
fast = slow;
slow = slow->next;
fast->next = NULL;
fast = sortList(head);//前半段排序
slow = sortList(slow);//后半段排序
return merge(fast,slow);
}
}
// merge two sorted list to one
ListNode *merge(ListNode *head1, ListNode *head2)
{
if(head1 == NULL)return head2;
if(head2 == NULL)return head1;
ListNode *res , *p ;
if(head1->val < head2->val)
{res = head1; head1 = head1->next;}
else{res = head2; head2 = head2->next;}
p = res;
while(head1 != NULL && head2 != NULL)
{
if(head1->val < head2->val)
{
p->next = head1;
head1 = head1->next;
}
else
{
p->next = head2;
head2 = head2->next;
}
p = p->next;
}
if(head1 != NULL)p->next = head1;
else if(head2 != NULL)p->next = head2;
return res;
}
};
冒泡排序（算法交换链表节点val值，时间复杂度O（n^2），空间复杂度O（1））
class Solution {
public:
ListNode *bubbleSortList(ListNode *head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
//链表快速排序
if(head == NULL || head->next == NULL)return head;
ListNode *p = NULL;
bool isChange = true;
while(p != head->next && isChange)
{
ListNode *q = head;
isChange = false;//标志当前这⼀轮中⼜没有发⽣元素交换，如果没有则表⽰数组已经有序
for(; q->next && q->next != p; q = q->next)
{
if(q->val > q->next->val)
{
swap(q->val, q->next->val);
isChange = true;
}
}
p = q;
}
return head;
}
};
对于希尔排序，因为排序过程中经常涉及到arr[i+gap]操作，其中gap为希尔排序的当前步长，这种操作不适合链表。
对于堆排序，⼀般是⽤数组来实现⼆叉堆，当然可以⽤⼆叉树来实现，但是这么做太⿇烦，还得花费额外的空间构建⼆叉树【版权声明】转载请注明出处：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。