单链表插入排序

链表插入排序的基本思想是：

      在每个对象的结点中增加一个链域link。

        对于存放于数组中的一组对象V[1],V[2]，…，V[n],若V[1],V[2]，…，V[i-1]已经通过链接指针link,按其排序码的大小，从小到大链接起来

        现在要插入V[i],i=2,3,…,n,则必须在前面i-1个链接起来的对象当中，循链顺序检测比较，找到V[i]应插入（链入）的位置，把V[i]插入，并修改相应的链接指针

        这样就可得到V[1],V[2],…,V[i]的一个通过链接指针排列好的链表。如此重复执行，直到把V[n]也插入到链表中排好序为止。

public class ListInsertionSort {
	public static void sort(int[] v) {
		int n = v.length;

		// step 1: link[] creation
		int[] link = new int[n];//链表，存储对应数组每个元素所指向的下一个索引下标
		int head = 0;//记录数组中最小值的下标，即头元素
		int next = 0;//记录链表中链接指针，指向下一个索引下标
		int curr = 0;//记录循环中遍历的当前位置下标
		link[0] = -1;
		for (int i = 1; i < n; i++) {
			System.out.println("=============================");
			if (v[head] > v[i]) { // case: head is changed to i
				link[i] = head;
				head = i; // change head
			} else {
				// two stop cases:
				// curr == -1: when we reach the tail
				// v[curr] > v[i]: insert i before curr, next is the predecessor
				// of curr
				// note: this loop executes at least once so 'next' always have
				// valid value
				for (curr = head; curr != -1 && v[curr] <= v[i]; curr = link[curr])
				{
					next = curr;
				}
					
				// insert i between next and curr (also applicable to tail case
				// when curr=-1)
				link[next] = i;
				link[i] = curr;
				
			}
		}

		// step 2: arrange v[] by link[] information: find curr and swap it with
		// i
		curr = head; // to scan linked list, always start with head
		
		// note the difference:
		// in this step: between iterations, curr doesn't start with head at the
		// beginning
		// the link creation step: between iterations, we always scan from
		// curr=head to find the insert position
		for (int i = 0; i < n; i++) {
			while (curr < i)
				curr = link[curr]; // look only those elements on the right side
									// of current element

			next = link[curr]; // save for next iteration's start position
			if (curr != i) { // if curr==i, no need change since position i is
								// done.
				int swap = v[i]; // swap key
				v[i] = v[curr];
				v[curr] = swap;

				link[curr] = link[i]; // copy i's link
				link[i] = curr; // reset pointer link[i] for redirection
			}
			curr = next; // next iteration we start from 'next'
		}

		// link[] is now useless, let it be garbage collected.
	}

	public static void main(String[] args) {
		int[] v = { 49, 38, 65, 97, 76, 13, 27, 49 };
		ListInsertionSort.sort(v);

		for (int key : v) {
			System.out.format(" %d", key);
		}
	}
}