关于归并算法的排序

快速排序的算法是对数组形式的数据是非常好用的，但是对链表却是不建议使用了，今天有学习了链表的归并算法分析。自己的list是比较简单的实现，没有实现List接口。并且，该实现只是为了学习，考虑的情况都是在单核情况下，所以代码的不严谨，还请原谅。
开始贴代码了

package com.mergesort;

import com.util.support.ListNode;
import com.util.support.Node;

/**
 * 本实例是对单向链表的归并排序的实现
 * 
 * @author Administrator
 * 
 */
public class MergeSort {

	/**
	 * 分割节点
	 * 
	 * @param top
	 * @return
	 */
	public static ListNode[] spitList(ListNode list) {

		// 获得元list的length
		int length = list.getLength();
		// 裁剪的部分的长度
		int amount = length / 2;

		ListNode newList = new ListNode();

		newList.addList(list, amount);

		return new ListNode[] { newList, list };

	}

	public static void sortList(ListNode list) {
		/**
		 * if list.length > 2 spit(list)===> left,right sortList(left)
		 * sortList(right); mergeList(left,right) else sortListSpecial(list);
		 */
		if (list.getLength() > 2) {
			ListNode[] lists = spitList(list);

			sortList(lists[0]);

			sortList(lists[1]);

			mergeList(lists[0], lists[1]);
		} else if (list.getLength() == 2) {
			realsortlist(list);
		}
		// 当当前的序列的长度是1或者zero的时候，我们可以不用排序

	}

	/**
	 * 对这个序列进行真正的排序，采用的是插入排序的算法
	 * 
	 * @param list
	 */
	private static void realsortlist(ListNode list) {

		Node current = list.getFirst();

		while (current.getNext() != null) {
			Node next = current.getNext();
			if (current.getData() > next.getData()) {
				// 从头开始进行比较
				Node node = list.getFirst();
				boolean insert = false;
				while (!insert) {
					if (node.getData() > next.getData()) {
						swap(node, next);
						insert = true;
					} else {
						node = node.getNext();
					}
				}
			}
			current = next;
		}
	}

	/**
	 * Swap the node and the next Data
	 * 
	 * @param node
	 * @param next
	 */
	private static void swap(Node node, Node next) {
		int temp = node.getData();
		node.setData(next.getData());
		next.setData(temp);
	}

	/**
	 * 合并两个ListNode，将listNode 合并到listNode2中
	 * 
	 * @param listNode
	 * @param listNode2
	 */
	/**
	 * define Node current to listNode define Node pdes to listNode2
	 * 
	 * while(pdes != null)
	 * 
	 * if(current.data < pdes.data) { insert current before pdes current =
	 * current.next; }else{ pdes = pdes.next;
	 * 
	 * } insert currents after pdes
	 * 
	 * 
	 */
	private static void mergeList(ListNode listNode, ListNode listNode2) {

		Node pdes = listNode2.getFirst();

		Node temp = new Node(-1);

		temp.setNext(pdes);
		pdes = temp;
		Node current = listNode.getFirst();

		Node old;

		while (pdes.getNext() != null) {
			if (current == null)
				break;

			Node srcNode = pdes.getNext();

			if (srcNode.getData() >= current.getData()) {
				// 开始进入插入
				old = current;
				current = current.getNext();
				old.setNext(srcNode);
				pdes.setNext(old);
				listNode2.length++;
			}
			pdes = pdes.getNext();
		}

		while (current != null) {
			pdes.setNext(current);
			pdes = current;
			current = current.getNext();
			listNode2.length++;
		}

		// 回收temp的资源
		listNode2.setFirst(temp.getNext());

		temp.setNext(null);

	}

	public static void main(String[] args) {

		// ListNode list = new ListNode();
		//
		// list.add(1);
		// list.add(3);
		// list.add(2);
		//
		// realsortlist(list);
		//
		// Node first = list.getFirst();
		//
		// while(first != null)
		// {
		// System.out.println(first.getData());
		// first = first.getNext();
		// }
		//
		// ListNode list1 = new ListNode();
		//
		// list1.add(1);
		// list1.add(3);
		// list1.add(5);
		//
		// ListNode list2 = new ListNode();
		//
		// list2.add(2);
		// list2.add(4);
		// list2.add(6);
		//
		// mergeList(list1, list2);
		//
		// System.out.println("list 的长度" + list2.length);;
		//
		// printList(list2);
		//
		// //分割的测试
		// System.out.println(" 开始进行分割测试");
		// ListNode[] lists = spitList(list2);
		//
		// for(ListNode list : lists)
		// {
		// System.out.println("list的长度" + list.length);
		// printList(list);
		// }

		// 开始进行测试归并排序算法
		int[] arrays = new int[] { 128, 137, 145, 55, 532, 99, 12, 3, 1000,
				255 };
		ListNode list = initListNode(arrays);

		sortList(list);
		
		printList(list);
	}

	private static ListNode initListNode(int[] arrays) {

		ListNode list = new ListNode();

		for (int data : arrays) {
			list.add(data);
		}

		return list;

	}

	private static void printList(ListNode list) {
		Node first = list.getFirst();

		while (first != null) {
			System.out.print(first.getData() + "  ");
			first = first.getNext();
		}

		System.out.println();
	}
}

经过初步的测试，发现是能够进行排序的。