java单链表冒泡排序_JAVA_编程开发_程序员俱乐部

class="java" name="code">
//节点类
class Node{
	public Node(int value){
		this.value = value;
	}
	public Node(){
	}
	int value;
	Node next;
}

//获得一个随机的单链表
	public Node getRandomSingList(){
		Node head = new Node();
		Node n1 = new Node((int)(Math.random()*100));
		Node n2 = new Node((int)(Math.random()*100));
		Node n3 = new Node((int)(Math.random()*100));
		Node n4 = new Node((int)(Math.random()*100));
		Node n5 = new Node((int)(Math.random()*100));
		n1.next = n2;
		n2.next = n3;
		n3.next = n4;
		n4.next = n5;
		head.next = n1;
		return head;
	}

//打印单链表
	public void printList(Node head){
		String str = "";
		for(Node n = head;n!=null;){
			str = str + " " + n.value;
			n = n.next;
		}
		System.out.println(str);
	}

//单链表冒泡排序
	public Node blueSortList(Node node){
		System.out.println("blue start...");
		//当前节点
		Node cur = node.next;
		//下一个节点
		Node next = cur.next;
		//前一个节点,两节点n1,n2交换位置时需要前一个节点的next指向n2节点
		Node upperNode = node;
		//一次排序的最后一个节点
		Node lastNode = null;
		int i = 1;
		//当第二个节点为当次排序的最后一个节点时，整体排序结束
		while(node.next != lastNode){
			//当下一个节点为一次次排序的最后一个节点时，本次排序结束。
			if(next == lastNode){
				lastNode = cur;
				cur = node.next;
				next = cur.next;
				upperNode = node;
			}else if(next.value < cur.value){
				cur.next = next.next;
				next.next = cur;
				upperNode.next = next;
				upperNode = next;
			}else{
				upperNode = cur;
				cur = cur.next;
			}
			next = cur.next;
			System.out.println("第" + i++ + "次排列结果:");
			printList(node.next);
		}
		System.out.println("blue end...");
		return node;
	}

Test t = new Test();
Node randomList = t.getRandomSingList();
		System.out.println("排序前:");
		t.printList(randomList.next);
		System.out.println("====================");
		Node sortList = t.blueSortList(randomList);
		System.out.println("====================");
		System.out.println("排序后:");
		t.printList(sortList.next);