把所有需要排序的数据分成两个集合，一个是待排序集合，一个是已排序的集合，算法每次从未排序集合顺序或随机拿取一个数据，把它加入到已排序集合使其有序，直到未排序集合中的数据被取走完，算法结束

数组a是未排序集合，已排序的集合是逻辑上的一个集合，可以看作是head，实现是一个双向链表，add方法向集合添加数据，每次找到对应的位置，使链表有序，toArray方法使已排序的集合输出成int数组。

public class Test5{
	public static void main(String args[]){
		int[] a=new int[]{1,9,5,4,2,5,1,5,6,8,7,4,1,5,4,5,1,2,1,2};
		a=sort(a);
		for(int i=0;i<a.length;i++){
			System.out.print(a[i]+" ");
		}
	}
	public static int[] sort(int[] a){
		for(int i=0;i<a.length;i++){
			add(a[i]);
		}
		return toArray(a.length);
	}
	public static int[] toArray(int size){
		int a[]=new int[size];
		Node p=head;
		int i=0;
		while(p!=null){
			a[i++]=p.data;
			p=p.next;
		}
		return a;
	}
	public static void add(int data){
		Node n=new Node(data);
		if(head==null){
			head=n;
			return;
		}else{
			Node p=head;
			while(p!=null){
				if(n.data<=p.data){
					if(p!=head){
						n.next=p;
						p.prev.next=n;
						n.prev=p.prev;
						p.prev=n;
						return;
					}else{
						p.prev=n;
						n.next=p;
						head=n;
						return;
					}
				}else{
					if(p.next!=null){
						p=p.next;
					}else{
						break;
					}
				}
			}
			p.next=n;
			n.prev=p;
		}
	}
	public static Node head;
	static class Node{
		public int data;
		public Node next;
		public Node prev;
		public Node(int data){
			this.data=data;
		}
	}
}