-
链表排序
2019-03-01 15:07:36链表定义及主函数 1、list.h文件 1、 #ifndef _LIST_H_ 2、 #define _LIST_H_ 3、 4、 struct ListNode 5、 { 6、 int val; 7、 ListNode* next;...2、main.cpp(省去链表排序代码) 1. #in...链表定义及主函数
1、list.h文件
1、 #ifndef _LIST_H_ 2、 #define _LIST_H_ 3、 4、 struct ListNode 5、 { 6、 int val; 7、 ListNode* next; 8、 }; 9、 10、#endif
2、main.cpp(省去链表排序代码)
1. #include <iostream> 2. 3. using namespace std; 4. 5. #include "List.h" 6. 7. void InsertionSortList(); 8. void SelectSortList(); 9. 10. //构建链表头结点 11. ListNode* head = new ListNode; 12. 13. int main() 14. { 15. head->next = NULL; 16. 17. //对链表赋值 18. for (int i = 0; i < 10; ++i) 19. { 20. 21. ListNode* p = new ListNode; 22. cin >> p->val; 23. p->next = head->next; 24. head->next = p; 25. 26. } 27. 28. //这里填写链表排序函数,如下: 29. //InsertionSortList(); 30. SelectSortList(); 31. 32. ListNode* q = head->next; 33. while (q) 34. { 35. cout << q->val << ' '; 36. q = q->next; 37. } 38. 39. return 0; 40. }
一、交换结点
1、直接插入排序
假设排序规则为从小到大。
左边的有序区为:head - pend的区域
右边的无序区为:p – NULL的区域
每次从head->next开始,tmp = head->next; 比较tmp->val与p->val和tmp与p的关系。
pre为tmp的前缀节点。
当tmp->val < p->val时,tmp、pre一直向后移;
当tmp->val > p->val时,将tmp与p两结点交换;
当tmp == p时,说明head – p为有序区,将pend = p。
插入排序在链表应用中交换结点。
二、交换元素
1、选择排序
假设排序规则由小到大。
将待排序列分为有序序列与无序序列。
每次在无序序列中找到最小的元素,将其与有序序列的最后一个值进行交换。
选择排序在链表应用中交换元素而不交换节点。
2、快速排序
单链表的快排序和数组的快排序基本思想相同,同样是基于划分,但是又有很大的不同:单链表不支持基于下标的访问。故算法中把待排序的链表拆分为2个子链表。
为了简单起见,选择链表的第一个节点作为基准,然后进行比较,比基准小得节点放入左面的子链表,比基准大的放入右边的子链表。在对待排序链表扫描一遍之后,左边子链表的节点值都小于基准的值,右边子链表的值都大于基准的值,然后把基准插入到链表中,并作为连接两个子链表的桥梁。然后分别对左、右两个子链表进行递归快速排序,以提高性能。
但是,由于单链表不能像数组那样随机存储,和数组的快排序相比较,还是有一些需要注意的细节:1、支点的选取,由于不能随机访问第K个元素,因此每次选择支点时可以取待排序那部分链表的头指针;
2、遍历量表方式,由于不能从单链表的末尾向前遍历,因此使用两个指针分别向前向后遍历的策略失效。
事实上,可以采用一趟遍历的方式将较小的元素放到单链表的左边。具体方法为:
1)定义两个指针pslow,pfast,其中pslow指向单链表的头结点,pfast指向单链表头结点的下一个结点;
2)使用pfast遍历单链表,每遇到一个比支点小的元素,就令pslow=pslow->next,然后和pslow进行数据交换。
3)、交换数据方式,直接交换链表数据指针指向的部分,不必交换链表节点本身。链表快速排序描述来源:深入单链表的快速排序详解
-
链表排序--奇偶链表排序
2019-11-17 13:28:50public class 奇偶链表排序 { public static void main(String[] args) { ListNode head = new ListNode(1); ListNode node2 = new ListNode(8); ListNode node3 = new ListNode(3); ListNode node4...题目描述:一个链表,奇数位升序偶数位降序,让链表变成升序的。比如:1 8 3 6 5 4 7 2 9,最后输出1 2 3 4 5 6 7 8 9。
分析:
这道题可以分成三步:
首先根据奇数位和偶数位拆分成两个链表。
然后对偶数链表进行反转。
最后将两个有序链表进行合并。package com.Link; public class 奇偶链表排序 { public static void main(String[] args) { ListNode head = new ListNode(1); ListNode node2 = new ListNode(8); ListNode node3 = new ListNode(3); ListNode node4 = new ListNode(6); ListNode node5 = new ListNode(5); ListNode node6 = new ListNode(4); ListNode node7 = new ListNode(7); ListNode node8 = new ListNode(2); ListNode node9 = new ListNode(9); head.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; node5.next = node6; node6.next = node7; node7.next = node8; node8.next = node9; //printList(head); ListNode[] heads = splitList(head); //printList(heads[0]); //printList(heads[1]); ListNode reverseHead =reverseList(heads[1]); //printList(reverseHead); ListNode mergeHead =mergeLists(heads[0], reverseHead); printList(mergeHead); } // 按照奇偶位拆分成两个链表 private static ListNode[] splitList(ListNode head) { ListNode head1 = null; ListNode head2 = null; ListNode cur1 = null; ListNode cur2 = null; int count = 1; while (head != null) { if (count % 2 == 1) { if (cur1 != null) { cur1.next = head; cur1 = cur1.next; } else { cur1 = head; head1 = cur1; } } else { if (cur2 != null) { cur2.next = head; cur2 = cur2.next; } else { cur2 = head; head2 = cur2; } } head = head.next; ++count; } // 跳出循环,要让最后两个末尾元素的下一个都指向null cur1.next = null; cur2.next = null; ListNode[] heads = new ListNode[]{head1, head2}; return heads; } // 反转链表 private static ListNode reverseList(ListNode head) { ListNode cur = head; ListNode pre = null; ListNode next = null; while (cur != null) { next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; } // 合并两个有序链表 private static ListNode mergeLists(ListNode head1, ListNode head2) { if (head1 == null && head2 == null) return null; if (head1 == null || head2 == null) return head1 == null ? head2 : head1; ListNode first = new ListNode(-1); ListNode cur = first; while (head1 != null && head2 != null) { if (head1.val < head2.val) { cur.next = head1; head1 = head1.next; } else { cur.next = head2; head2 = head2.next; } cur = cur.next; } cur.next = head1 != null ? head1 : head2; return first.next; } // 初始化链表 // 打印链表 private static void printList(ListNode head) { if (head == null) return; ListNode cur = head; while (cur.next != null) { System.out.print(cur.val + "\t"); cur = cur.next; } System.out.println(cur.val); } public static class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } } }