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

单链表排序

发表于: 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

    震惊

    震惊

编辑推荐
单链表的快排序和数组的快排序基本思想相同,同样是基于划分,但是又有很大的不同:单链表不支持基
链表插入排序的基本思想是: 在每个对象的结点中增加一个链域link。 对于存放于数组中的一组对象V[1
每日一贴,今天的内容关键字为链表节点 1 数组合并排序 1.1 合并两个已排序好的数组 需要额定的存储
Java中有两种表的数据结构:ArrayList和LinkedList,其中ArrayList以数组的形式保存数据,即相邻两
今天突然想到要搞搞数据结构,结果写了半天,还是就只到单链表的建立和访问,中间还搞出不少问题,
【1】线性表的链式存储 线性表的顺序存储结构特点: 逻辑关系上相邻的两个元素在物理位置上也相邻;
一、链表说明: 1. 链表是继数组之后的又一个使用很广泛的数据结构。链表包括有单链表、双端链表、
由于考试需要,复习一下单链表的各种常见操作,直接上代码+注释,需要的可以参考下哈~ Code: [cpp]
 我想你去很多家公司面试的时候,遇到单链表倒置的问题可能比较多,如果一定要给面试题来一个排名
这几天找工作,遇到一个挺好玩的笔试题,做完之后想了一个比较简单的实现方法。 题目是:实现一个单
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号