精华内容
下载资源
问答
  • 链表排序

    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)定义两个指针pslowpfast,其中pslow指向单链表的头结点,pfast指向单链表头结点的下一个结点;
           2)使用pfast遍历单链表,每遇到一个比支点小的元素,就令pslow=pslow->next,然后和pslow进行数据交换。
           3)、交换数据方式,直接交换链表数据指针指向的部分,不必交换链表节点本身。

           链表快速排序描述来源:深入单链表的快速排序详解

    展开全文
  • 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...

    题目描述:一个链表,奇数位升序偶数位降序,让链表变成升序的。比如: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;
    		}
    	}
    }
    
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,925
精华内容 12,370
关键字:

链表排序