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

问题描述：

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

基本要求：

（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();
	}
}

Mi

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();		
	}
}