这篇文章分析一下链表的各种排序方法。
以下排序算法的正确性都可以在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的第二种写法(选取第一个元素作为枢纽元的版本,因为链表选择最后一元素需要遍历一遍),具体可以参考here
这里我们还需要注意的一点是数组的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); tmpHead.next = head; qsortList(&tmpHead, head, NULL); return tmpHead.next; } 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 = node2.next; lowPre->next = node1.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为希尔排序的当前步长,这种操作不适合链表。
对于堆排序,一般是用数组来实现二叉堆,当然可以用二叉树来实现,但是这么做太麻烦,还得花费额外的空间构建二叉树
【版权声明】转载请注明出处:http://www.cnblogs.com/TenosDoIt/p/3666585.html
今天的文章链表冒泡排序交换节点_归并两个单链表分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/46660.html