单链表实现插入排序？

在排序算法中，一般我们最先接触的是插入和选择排序。在学习之初，一般是基于对数组的操作，其能够随机读取的特性，在学习之初更加容易理清思路。

虽然数组在理解实现上更容易，但在面对大量数据增改的时候和链表相比就略显逊色。

今天就先对链表的插入排序进行分析，首先复盘一下数组的插入排序。

1. 数组实现

首先先从简单的数组类型功能实现入手。

基本思想就是将一个数组划分为只有一个元素的 子表1 和剩下的元素构成的 子表2 。每次从 子表2 取一个元素插入到 子表1 表尾，如果插入元素小于等于表尾元素，则将元素不断后移，直到遇到大于此值的元素并插入，最终实现排序的目的。

光看文字可能不太清楚，直接上代码。

public void InsertSort(int A[])
{
    // A[i-1]: 子表1表尾，A[i]：子表2表头
    for(int i = 2 ; i <= A.length ; i++){

        // 如果要插入元素小于子表表尾 
        if(A[i] < A[i-1]){  
            A[0] = A[i];    // 哨兵，临时存放待插入元素

            // 从子表表尾往前扫描，把大于哨兵的后移
            // 当遇到比哨兵大的元素结束循环，将元素插入到该位置
            for(int j = i-1 ; A[0] < A[j] ; j--){      
                A[j+1] = A[j];
            }
            A[j+1] = A[0];
        }
    }
}

2. 链表实现

数组实现起来相对比较简单，那么链表又应该怎么实现呢？

思路上其实时一致的，这里是基于含头结点的单链表。通过将链表划分为两个子链表进行操作，需要注意的一点是如果要求输出增序，链表我们应该排成降序，这是因为基于链表的头插方式第一个插入的元素会在最后一个输出。

同样附上实现代码：

void Sort(LinkList &L){
    LNode *p = L->next, *pre;    // p 指向头结点
    LNode *r = p->next;         // r 指向第一个元素
    
    p->next = NULL;     // 将 L 置为空表，仅含有头结点
    p = r;              // p 指向第一个元素

    while (p != NULL)
    {
        r = p->next;    //指向后继，保证不断链
        pre = L;        //头指针

        // 此时已经变成两条链表：
        // 一条是以 pre 为头指针的链表，一条是以 p 为第一个元素的链表

        // 插入排序, 得到一个递减的链表，根据头插法特性输出时刚好递增
        // 如果插入的元素比子表尾的值大，依次往后移动元素
        while (pre->next != NULL && p->date > pre->next->date )
        {
            pre = pre->next;
        }
        p->next = pre->next;    //插入，先链后断
        pre->next = p;
        p = r;
    }
}

实现起来和数组其实类似，建议在写代码的时候在旁边画一下草稿就很清晰了。