insert.cpp

来自「数据结构与程序设计教材源码 数据结构与程序设计教材源码」· C++ 代码 · 共 51 行

 
template <class Record>
void Sortable_list<Record>::insertion_sort()
/* 
 
Post: The entries of the Sortable_list
have been rearranged so that the keys in all the
entries are sorted into nondecreasing order.
Uses: Methods for the class Record.  The linked
      List implementation of ?list_ch?.
 
*/
{
   Node <Record> *first_unsorted,  //  the first unsorted node to be inserted
                 *last_sorted,     //  tail of the sorted sublist
                 *current,         //  used to traverse the sorted sublist
                 *trailing;        //  one position behind current 

   if (head != NULL) {          //  Otherwise, the empty list is already sorted.
      last_sorted = head;       //  The first node alone makes a sorted sublist.
      while (last_sorted->next != NULL) {
         first_unsorted = last_sorted->next;
         if (first_unsorted->entry < head->entry) {
            //  Insert *first_unsorted at the head of the sorted list:
            last_sorted->next = first_unsorted->next;
            first_unsorted->next = head;
            head = first_unsorted;
         }
         else {
            //  Search the sorted sublist to insert *first_unsorted:
            trailing = head;
            current = trailing->next;
            while (first_unsorted->entry > current->entry) {
               trailing = current;
               current = trailing->next;
            }

            //  *first_unsorted now belongs between *trailing and *current.

            if (first_unsorted == current)
               last_sorted = first_unsorted;  //  already in right position
            else {
               last_sorted->next = first_unsorted->next;
               first_unsorted->next = current;
               trailing->next = first_unsorted;
            }
         }
      }
   }
}