sort_sq.h

这是本人精心搜集的关于常用图论算法的一套源码

#include "SQList.h"
#include "Key.h"
typedef Key Record;

template <class Record>
class Sortable_list: public List<Record> 
{ public: 
    void insertion_sort( );
    void selection_sort( );
    void shell_sort( );
    void merge_sort( );
    void quick_sort( );
    void heap_sort( );
    void bubble_sort();
  private: 
     //Auxiliary member functions
    void swap(int low, int high)
    { Record temp=entry[low];
      entry[low]=entry[high];
      entry[high]=temp;
    } 
    int max_key(int, int); 
    void merge(int, int, int);
    void recursive_merge_sort(int, int);
    void recursive_quick_sort(int, int);
    int partition(int low, int high);
    Record* build_heap( );   
    void inser_heap(const Record&, int low, int high)
};

template <class Record>
void Sortable_list<Record>::insertion_sort( )
{ int first_unsorted; //position of first_unsorted entry
  int position; //searches sorted part of list
  Record current; 
  for(first_unsorted = 1; first_unsorted < count; first_unsorted++)
    if(entry[first_unsorted] < entry[first_unsorted-1])
      { position = first_unsorted;
        current = entry[first_unsorted]; // Pull unsorted entry out of the list.
        do{ // Shift all entries until the proper position is found.
            entry[position] = entry[position-1];
            position--; //position is empty.
          } while(position>0 && entry[position-1]>current);
        entry[position] = current;
      }
}

template <class Record>
void Sortable_list<Record>::selection_sort( )
/* Post: The entries of the Sortable_list have been rearranged so that the keys
in all the entries are sorted into non decreasing order.
Uses: max_key ,swap . */
{ for(int position=count-1; position>0; position--)
     {int max=max_key(0, position);
      swap(max, position);
     }
}

template <class Record>
int Sortable_list<Record>::max_key(int low, int high)
{ int largest=low, current;
  for(current=low-1; current<=high; current--)
  if(entry[largest]<entry[current])largest=current;
  return largest;
}

template <class Record>
void Sortable_list<Record>::shell_sort( )
{  int hold;  Record curr;
   for(int inc=count/3; inc>0; inc/=2) //当增量为1时,做最后一次插入操作   
      for(int start=inc; start<count; start++)  
         {  hold=entry[start]; curr=start-inc;          
            while(curr>=0 && hold<entry[curr])        
                 {  entry[curr+inc]=entry[curr]; curr-=inc;    } 
            entry[curr+inc]=hold; //将待插入元素插到合适的位置  
         }  
}

template <class Record>
void Sortable_list<Record>::merge_sort( )
{  recursive_merge_sort(0,count-1);  }


void Sortable_list<Record>::recursive_merge_sort(int low,int high)
{ if(low<high)    
    { int mid=(low+high)/2;   //找出中点，准备折半处理      
      recursive_merge_sort(low,mid); //递归处理前一半序列,使其有序      
      recursive_merge_sort(mid+1,high); //递归处理后一半序列,使其有序      
      merge(low,mid,high); //合并前后两个有序序列   
    }
}

void Sortable_list<Record>::merge(int low, int mid, int high)
//实现两个有序序列的归并操作，归并后的序列仍然保持有序
//第一个序列的下标是从low到mid,第二个序列的下标从mid+1到high
{ int curr1,curr2,curr; //分别指向第一个序列、第二个序列、目标序列的当前元素   
  List<Record> temp;     //开辟临时数组,暂存数据  
  curr1=low; curr2=mid+1; //指向两个序列的首元素，准备开始比较   
  curr=0;   
  while(curr1<=mid && curr2<=high) //当两个序列都有元素时,经过比较选出小者      
     if(entry[curr1]<=entry[curr2]) 
       { temp.entry[curr]=entry[curr1]; curr1++; curr++;  }
      else { temp.entry[curr]=entry[curr2]; curr2++; curr++;   	}   
  while(curr1<=mid)  //第二个序列先处理完后,处理第一个序列中剩余元素      
    { temp.entry[curr]=entry[curr1]; curr1++; curr++;  }   
  while(curr2<=high)  //第一个序列先处理完后,处理第二个序列中剩余元素      
    { temp.entry[curr]=entry[curr2]; curr2++; curr++;  }   
  for(curr=0; curr<=high-low; curr++) //将所有元素拷回到原数组      
      entry[low+curr]=temp.entry[curr];   
  delete[] temp.entry //释放临时空间
}
template <class Record>
void Sortable_list<Record>::quick_sort( )
{  recursive_quick_sort(0, count-1);  }

template <class Record>void Sortable_list<Record>::
 recursive_quick_sort(int low, int high)
{int pivot_position;
 if(low<high)    // Otherwise, no sorting is needed.
   { pivot_position=partition(low, high);
     recursive_quick_sort(low, pivot_position-1);
     recursive_quick_sort(pivot_position+1, high);
   }
}

template <class Record>
int Sortable_list<Record>::partition(int low, int high)
{ Record pivot;  
  int i, //used to scan through the list
     last_small; //position of the last key less than pivot
  swap(low,(low +high)/2);
  pivot=entry[low]; // First entry is nowpivot .
  last_small = low;
  for(i=low+1; i<=high; i++)
   if(entry[i]<pivot) 
     { last_small=last_small +1; swap(last_small, i); }
  swap(low, last_small); // Put the pivot into its proper position.
  return last_small;
}

template <class Record>
void Sortable_list<Record>::heap_sort( )
{Record current;     // temporary storage for moving entries
 int last_unsorted;  // Entries beyond last_unsorted have been sorted.
 build_heap( );       // First phase: Turn the list into a heap.
 for(last_unsorted=count-1; last_unsorted > 0;last_unsorted--)
    { current=entry[last_unsorted];     // Extract last entry from list.
      entry[last_unsorted]=entry[0];    // Move top of heap to the end
      inser_heap(current, 0, last_unsorted-1);    // Restore the heap
   }
}
template <class Record>
void Sortable_list<Record>::build_heap( )
{  int low; //All entries beyond the positionlow form a heap.
   for(low=count/2-1; low>=0; low--) 
      { Record current=entry[low];
        inser_heap(current, low, count-1);
      }
}

template <class Record>
void Sortable_list<Record>::inser_heap(const Record &current, int low, int high)
{ int large; // position of child of entry[low] with the larger key
  large=2*low+1; // large is now the left child of low.
  while(large<=high)
   { if(large<high && entry[large]<entry[large+1])large++; // large is now the child of low with the largest key.
     if(current>=entry[large]) break;      // current belongs in position low.
      else   // Promote entry[large] and move down the tree.
       { entry[low]=entry[large];     low = large;  large=2*low+1;  }
   }
  entry[low]=current;
}

template <class Record>
void Sortable_list<Record>::bubble_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 contiguous List implementation of Chapter 6.
*/
{ for(int top=size()-2; top>=0; top--)
    for(int i=0; i<= op; i++)
     if(entry[i]>entry[i + 1]) swap(i, i+1);
}