表插入排序

1.算法思想

表插入排序算法主要利用单链表的插入删除操作简单的特性减少排序过程中的移动次序。首先将链表分为以排序和未排序两部分，将当前待排序结点与已排序的结点从左往右比较，找到插入位置。然后将当前待排序结点从链表中断开后插入找到的位置，完成一次排序，当前待排序结点向后移动一个结点，重复上面的操作直到待排序的结点为空，整个排序算法结束。

2.算法图解

已排序的部分为12，32两个结点，当前待排序的为第三个结点，通过比较当前结点的插入位置为结点12的前面，所以先断开当前结点，然后将当前结点插入12结点的前面，即完成对当前待排序结点的排序。

3.代码实现

下面是算法的C语言代码实现：

/*
表插法排序（升序）
 */
#include<stdio.h>
#include<stdlib.h>
struct Node;
typedef struct Node *ListNode;
struct Node
{
    int key;
    ListNode next;
};
typedef ListNode LinkList;

LinkList createEmptyList();
void addList(LinkList plist,ListNode p,int x);
void listSort(LinkList plist);
void printList(LinkList list);

LinkList createEmptyList()
{
    LinkList list = (LinkList)malloc(sizeof(struct Node));
    if(list!=NULL)
    {
        list->next = NULL;
    }
    else{
        printf("Out of memery!\n");
    }
    return list;
}
void addList(LinkList plist,ListNode p,int x)
{
    ListNode q = (ListNode)malloc(sizeof(struct Node));
    if(q==NULL)
    {
        printf("Out of memery\n");
    }
    else{
        q->key = x;
        q->next = p->next;
        p->next = q;
    }
}
void listSort(LinkList plist)
{
    ListNode now,pre,p,q,head;
    head = plist;
    pre = head->next;
    if(pre==NULL)
    {
        return;
    }
    now = pre->next;//当前待排序的结点
    if(now==NULL)
    {
        return;
    }
    //以下为排序代码
    while(now!=NULL)
    {
        q = head;
        p = head->next;
        while(p!=now&&p->key<=now->key)
        {
            q = p;
            p = p->next;
        }
        if(p==now)
        {
            pre = pre->next;
            now = pre->next;;
            continue;
        }
        pre->next = now->next;
        q->next = now;
        now->next = p;
        now = pre->next;
    }
}
void printList(LinkList list)
{
    ListNode p;
    p = list->next;
    while(p!=NULL)
    {
        printf("%d ", p->key);
        p = p->next;
    }
    printf("\n");
}
int main()
{
    int a[] = {49,38,65,97,76,13,27,49};
    LinkList list = createEmptyList();
    ListNode p = list;
    for(int i=0;i<sizeof(a)/sizeof(a[0]);i++)
    {
        addList(list,p,a[i]);
    }
    listSort(list);
    printList(list);
    return 0;
}

下面是算法的Java代码实现：

package tableInsertSort;
/*
 * 表插法排序（升序）
 */
public class TableInsertSort {

    public static Node init()
    {
        int []a = {49,38,65,97,76,13,27,49};
        Node head = new Node();
        Node p = head;
        for(int i=0;i<a.length;i++)
        {
            Node node = new Node();
            node.setKey(a[i]);
            p.setNode(node);
            p = node;
        }
        return head;
    }
    public static void sort(Node list)
    {
        Node pre,now,p,q,head;
        head = list;
        pre = list.getNode();
        now = pre.getNode();
        while(now!=null)
        {
            q = head;
            p = q.getNode();
            while(p!=now&&p.getKey()<=now.getKey())
            {
                q = p;
                p = p.getNode();
            }
            if(p==now)
            {
                pre = pre.getNode();
                now = pre.getNode();
                continue;
            }
            pre.setNode(now.getNode());
            q.setNode(now);
            now.setNode(p);
            now = pre.getNode();
        }
    }
    public static void printList(Node head)
    {
        Node p = head.getNode();
        while(p!=null)
        {
            System.out.print(p.getKey()+" ");
            p = p.getNode();
        }
    }
    public static void main(String agrs[])
    {
        Node list = init();
        sort(list);
        printList(list);
    }
}
class Node
{
    private int key;
    private Node node;
    public Node()
    {
        
    }
    public Node(int key,Node node)
    {
        this.key = key;
        this.node = node;
    }
    public int getKey() {
        return key;
    }
    public void setKey(int key) {
        this.key = key;
    }
    public Node getNode() {
        return node;
    }
    public void setNode(Node node) {
        this.node = node;
    }
    
}

4.小结

表插入排序时元素移动的次数为0，算法比较次数和直接插入排序算法比较次数同级，平均时间复杂度为T(n)=O(n^2)。每个元素中增加了指向下一个结点的指针字段，所以辅助空间为S(n)=O(n)。算法条件由p->key<=now-<key控制循环结束，所以表插入排序算法是稳定的。