重走算法路之用链表排序（一）

        昨天把链表敲了一下，我们可以实现一个不要为他内存浪费和溢出而伤脑筋的存放数据的结构，我们以前对数据进行排序的时候都是喜欢放在数组里面，用数组来保存我们的排好序的数据，同时在数组中对数组进行操作，实现排序。今天就用昨天的链表来给数据排排序，在插入元素节点的时候就进行判断，然后插入，最后得到的链表也就是一个排好了序的链表。

       用这个思想我们可以把他用到一个高效的排序机制里面，假设有一个无序的数组，我们把他们取出来一个一个的插入到有序链表，在插入的时候他们自动完成了排序，插入完毕之后，把他们从有序链表中删除（删除的时候返回头节点），重新放入数组，经过这样的操作我们就可以完成无序数组的排序了。

        这种排序的方式和数组的插入排序的思想是一样的，但是比数组中的插入排序效率更高一些，主要是复制的次数少一些，在数组中进行插入排序需要一栋N^2次，而在链表中，每一个节点只要复制两次，也就是2N次，一次是从数组到链表，一次是从链表在到数组。虽然他们的时间复杂度还全都是O(N^2)（因为用链表插入每个节点平均还是会和 链表中的N/2个元素进行比较，插入N个元素时间复杂度还是到了O(N^2)）但是第二种还是好一点。因为在移动数据这里少了很多时间。

       

    下面把用链表把插入的数据排好序的代码贴出来，可以扩展到对存放到数组中的一组元素进行排序：

       

    先是链表中的节点类：

      

package 有序链表;

/*
 * 节点类，封装了属性
 * @author TMS
 *
 */
public class Link {
	public long data;
	public Link next;         //定义指向下一个节点
	
	/*
	 * 初始化节点的属性
	 */
	public Link(long data) {  
		this.data = data;
	}
   
	/*
	 * 打印出每个节点的信息
	 */
    public void displayLink() {
    	System.out.println("data = "+data);
    }
}

   

    再是主类：关键代码也就是里面的Insert();方法，插入节点后，自动排好序了。

   

package 有序链表;

public class SortLink {
	
	/*
	 * 定义第一个节点
	 */
	private Link first;
	
	/*
	 * 初始化头节点
	 */
	public SortLink() {
		first = null;
	}
	
	/*
	 * 判断是否为空
	 */
	public boolean isEmpty() {
		return first == null;
	}
	
	/*
	 * 插入一个节点，并进行判断，使链表成为有序的
	 */
	public void insert(long data) {
		Link newLink = new Link(data);
		Link old = null;
		Link current = first;
		
		while( current !=null && data>current.data ) {    //遍历进行判断，插入节点
			old = current;                                //先记录当前的节点
			current = current.next;                       //节点依次往下跑
		}
		if(old == null) {                                 //链表中为空的时候
			first = newLink;                              //将新的节点直接赋给第一个节点
		} 
		else {
			old.next = newLink;                           //开始的时候链表就不为空，也就是会将新的
			                                              //元素插入到中间时，原先的节点指向新的节点
			                                              //新的节点指向当前的节点
			newLink.next = current;
		}
	}
	
	/*
	 * 删除头节点
	 */
	public Link remove() {
		Link temp = first;
		first = first.next;
		return temp;
	}
	
	/*
	 * 打印出每个节点，从头节点开始
	 */
	public  void display() {
		Link current = first;
		while(current!= null) {
			current.displayLink();
			current = current.next;
		}	
	}
	
	/*
	 * 测试方法
	 */
	public static void main(String[] args) {
		SortLink sl = new SortLink();
		System.out.println("添加几个节点：");
		sl.insert(2);
		sl.insert(32);
		sl.insert(17);
		sl.insert(18);
		sl.insert(10);
		System.out.println("打印出每个节点，经过排序了的：");
		sl.display();
		System.out.println("<----------------------------------->");
		System.out.println("删除几个节点是从头节点开始删的 ：");
		System.out.println("删除一个节点："+sl.remove().data);
		System.out.println("删除一个节点："+sl.remove().data);
		System.out.println("打印出每个节点，删除几个节点后：");
		sl.display();
		
	}
}

 

    打印出结果，和上面插入的数据进行比较,看是否排好序了：

    

添加几个节点：
打印出每个节点，经过排序了的：
data = 2
data = 10
data = 17
data = 18
data = 32
<----------------------------------->
删除几个节点是从头节点开始删的 ：
删除一个节点：2
删除一个节点：10
打印出每个节点，删除几个节点后：
data = 17
data = 18
data = 32

 

   PS:好了！洗洗睡了！渣渣每天都会来一发，不要说我水。一天的谢幕。