所谓表插入排序，是利用一个有序链表，将无序数组的元素依次插入有序链表中，则元素自动按顺序排列，然后循环删除表头元素，并重新放入数组，即排好序。
在效率上，在有序链表中插入数据，平均比较次数为 N/2, 插入N个数据， 比较次数为 N^2/4，即 O(N^2). 但复制仅需两次，一次从数组到链表，一次从链表到数组，对N个元素为 2*N 次，即 O(N).
对于有现成有序链表的情况来说，这是个不错的选择， 它的算法实际在有序链表的插入操作中实现， 由于链表的插入，删除效率很高, 都为O(n)，且不需移动元素。 但是注定它不能用在大型的数组排序中， 它不但需要一个现成的有序链表结构，而且在内存中占用双倍的空间。
代码片断
/*
insert the elements of array into the sorted list
then remove them and copy the returned elem
back into a array, finally return it.
*/
public void sort () {
ListNode[] nodeArray = new ListNode[maxSize]; // 根据要排序数组的大小生成链表结点的数组
for (int i=0; i<maxSize; i++) {
nodeArray[i] = new ListNode (array[i]); // 根据数组中元素类型生成结点
list.insert (nodeArray[i]); // 在链表中插入结点
}
for (int i = 0; i<maxSize; i++) {
array[i] = list.removeHead().getData(); // 移除头结点并复制回数组
}
}