基于单链表的直接插入排序

ゞ浴缸里的玫瑰 2022-05-28 01:21 176阅读 0赞

问题描述：

用单链表作为待排序数据的存储结构，在其上实现直接插入排序算法。

基本要求：

（1） 待排序数据表采用单链表存储结构；

（2） 设计非降序的直接插入排序算法，要求算法空间复杂度为O（1）。

（3） 输入：待排序表可从文件读入、程序中定义、键盘输入或随机生成；

（4） 输出：待排序记录，已排序记录。

Node.java

LinkList.java

Main.java

package ch01;
    public class Node
    {
    	public Object data;
    	public Node next;
    	
    	//无参的构造方法
    	public Node()
    	{
    		this(null,null);
    	}
    	
    	//有一个参数的构造方法
    	public Node(Object data)
    	{
    		this(data,null);
    	}
    	
    	//有两个参数的构造方法
    	public Node(Object data,Node next)
    	{
    		this.data = data;
    		this.next = next;
    	}
    	
    }

LinkList.java

package ch01;
    import ch01.*;
    import java.lang.*;
    public class LinkList
    {
    	public Node head;
    	
    	public LinkList()  
    	{
    		head = new Node();  //头指针
    	}
    	
    	//将一个已经存在的带头结点的单链表置成空表
    	public void clear()
    	{
    		head.data = null;
    		head.next = null;
    	}
    	
    	//单链表插入算法
    	public void insert(int i,Object x)throws Exception
    	{
    		Node p = head;
    		int j=-1;
    		while(p!=null&&j<i-1)
    		{
    			p = p.next;
    			++j;
    		}
    		if(j>i-1||p==null)
    			throw new Exception("插入位置不合法！");
    		Node s = new Node(x);
    		s.next = p.next;
    		p.next = s;
    	}
    	
    	//直接插入排序算法
    	public void insertSort(LinkList L)
    		{
    			Node p,q,r,u;
    			p = L.head.next;
    			L.head.next = null;
    			while(p!=null)
    			{
    				r =L.head;
    				q=L.head.next;
    				while(q!=null&&(Integer.valueOf((int)q.data).intValue())<=(Integer.valueOf((int)p.data).intValue()))
    				{
    					r = q;
    					q = q.next;
    				}
    				u = p.next;
    				p.next = r.next;
    				r.next = p;
    				p = u;
    			}
    
    		}
    
    	public void display()
    	{
    		Node node = head.next;
    		while(node!=null)
    		{
    			System.out.print(node.data+"  ");
    			node = node.next;
    		}
    		System.out.println();
    	}
    }

package ch01;
    import ch01.*;
    import java.util.Scanner;
    public class Main
    {
    	public static void main(String []args) throws Exception
    	{
    		int n = 10;
    		Scanner sc = new Scanner(System.in);
    		LinkList L = new LinkList();  //创建一个空的单链表
    		for(int i=0;i<n;i++) 
    		{
    			System.out.print("请输入第"+i+"个数字：");
    			int t= sc.nextInt();
    			L.insert(i,t);
    		}
    		System.out.println("单链表上的数据为：");
    		L.display();
    		System.out.println("排序后的顺序为：");
    		L.insertSort(L);
    		L.display();		
    	}
    }

![2018032712383715][]

[2018032712383715]: /images/20220528/a4f7c29e3d24459d85fa83cc9bdd1bd1.png