当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

单链表排序

发表于: 2013-03-15   作者:antlove   来源:转载   浏览:
摘要: 闲来无事,写了个单链表排序。本人算法很渣,欢迎各种拍砖,各种优化,各种新实现。 以下算法是基于冒泡排序的思想。两两比较将最大的放到最后(冒泡排序是将最小的升到最前)。     单链表节点类SingleLinkNode.java package link; public class SingleLinkNode { private int data; priv

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

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

 

 

单链表节点类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;
	}
}

 

 

 

 

单链表排序

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号