单链表排序

闲来无事，写了个单链表排序。本人算法很渣，欢迎各种拍砖，各种优化，各种新实现。

以下算法是基于冒泡排序的思想。两两比较将最大的放到最后(冒泡排序是将最小的升到最前)。

 

 

单链表节点类SingleLinkNode.java

package link;
public class SingleLinkNode {
	private int data;
	private SingleLinkNode nextNode;
	public SingleLinkNode(int data, SingleLinkNode nextNode) {
		this.data = data;
		this.nextNode = nextNode;
	}
	public int getData() {
		return data;
	}
	public void setData(int data) {
		this.data = data;
	}
	public SingleLinkNode getNextNode() {
		return nextNode;
	}
	public void setNextNode(SingleLinkNode nextNode) {
		this.nextNode = nextNode;
	}
}

 

单链表类SingleLinkList.java

package link;
import java.util.Random;
public class SingleLinkList {
	// the header node of the single link list
	private SingleLinkNode headerNode;
	
	public SingleLinkNode getHeaderNode() {
		return headerNode;
	}
	// construct the single link list which contains 10 nodes
	public SingleLinkList() {
		headerNode=new SingleLinkNode(new Random().nextInt(100),null);
		SingleLinkNode currentNode=headerNode;
		for(int i=0;i<9;i++){
			SingleLinkNode nextNode=new 
			SingleLinkNode(new Random().nextInt(100),null);
			currentNode.setNextNode(nextNode);
			currentNode=nextNode;
		}
	}
	public String toString(){
		String result="";
		SingleLinkNode currentNode=headerNode;
		while(currentNode!=null){
			result+=currentNode.getData()+"-->";
			currentNode=currentNode.getNextNode();
		}
		result+="null";
		return result;
	}
}

 

 排序算法类Utils.java

package link;
public class Utils {
	// base on bubble sort
	public static SingleLinkList sort(SingleLinkList singleLinkList) {
		SingleLinkNode headerNode=singleLinkList.getHeaderNode();
		SingleLinkNode currentNode=headerNode;
		SingleLinkNode nextNode=currentNode.getNextNode();
		if(nextNode==null){
			return singleLinkList;
		}
		SingleLinkNode lastNode=null;
		
		int tempData=-1;
		// if the last node is the second node,the loop is over
		while(headerNode.getNextNode()!=lastNode){
			// check whether the next node is the last node.
			// if yes, then ship this loop.
			if(nextNode==lastNode){
				lastNode=currentNode;
				currentNode=singleLinkList.getHeaderNode();
				nextNode=currentNode.getNextNode();
				continue;
			}
			if(currentNode.getData()>nextNode.getData()){
				// exchange the data
				tempData=currentNode.getData();
				currentNode.setData(nextNode.getData());
				nextNode.setData(tempData);
			}
			currentNode=currentNode.getNextNode();
			nextNode=currentNode.getNextNode();
		}
		return singleLinkList;
	}
}

 

 

 

 

评论

2 楼 antlove 2013-03-18  

lijiejava 写道

好帖，支持，顶！！！！

每次都赏脸，谢谢哟。

1 楼 lijiejava 2013-03-16  

好帖，支持，顶！！！！