守望

 1template <class Record>
 2void InsertionSort(Record *array, int count)
 3{
 4    // "fu" means first unsorted
 5    for (int fu = 1; fu < count; ++fu)
 6    {
 7        if (array[fu] < array[fu - 1])
 8        {
 9            int pos = fu;
10            Record current = array[fu];
11            do
12            {
13                array[pos] = array[pos - 1];
14                --pos;
15            } while (pos > 0 && array[pos - 1] > current);
16            array[pos] = current;
17        }
18    }
19}

template <class Record>
void InsertionSort(Node<Record> *list)
{
    if (list != NULL)
    {
        // "ls" means last sorted
        Node<Record> *ls = list;
        while (ls->next != NULL)
        {
            // "fu" means first unsorted
            Node<Record> *fu = ls->next;
            if (fu->data < list->data)
            {
                ls->next = fu->next;
                fu->next = list;
                list = fu;
            }
            else
            {
                Node<Record> *itr = list;
                Node<Record> *cur = itr->next;
                while (fu->data > cur->data)
                {
                    itr = cur;
                    cur = itr->next;
                }

    if (fu == cur)
    {
        ls = fu;
    }
                else
                {
        ls->next = fu->next;
                    fu->next = cur;
                    itr->next = fu;
                }
            }
        }
    }
}