template<class Record>
Sortable_list<Record>::Sortable_list(const Record A[],int size)
{for(int i=0;i<size;i++)insert(i,A[i]);
}

template<class Record>
void Sortable_list<Record>::shell_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: sort_interval.
*/
{int increment,   //spacing of entries in subliststart;       //starting point of sublistincrement=count;do{increment=increment/2;for(start=0;start<increment;start++){sort_interval(start,increment);  //modified insertion sorttraverse(print_out);cout<<endl;}}while(increment>1);
}template<class Record>
void Sortable_list<Record>::sort_interval(int start,int increment)
{Sortable_list<Record> temp;int j=0;for(int i=start;i<size();i=i+increment){Record temp_record;retrieve(i,temp_record);temp.insert(j,temp_record);j++;}temp.insertion_sort();j=0;for(int k=start;k<size();k+=increment){Record temp_record;temp.retrieve(j,temp_record);replace(k,temp_record);j++;}
}
template<class Record>
void Sortable_list<Record>::insertion_sort()
/*Post: The entries of the Sortable_list have been rearranged so that the keys inall the entries are sorted into nondecreasing order.Uses: Methods for the class Record; the contiguous List 
*/
{int first_unsorted;            //position of first unsorted entryint position;                  //searches sorted part of listRecord current;                //holds the entry emporarily removed from listfor(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 foundentry[position]=entry[position-1];position--;         //position if empty.}while(position>0&&entry[position-1]>current);entry[position]=current;}
}
//其他辅助函数见源文件

【实验结果】

归并排序

template<class Record>
void Sortable_list<Record>::merge(int low,int high)
{Record *tmp=new Record[high-low+1];int index=0;int index1=low,mid=(low+high)/2,index2=mid+1;while(index1<=mid&&index2<=high){if(entry[index1]<entry[index2])tmp[index++]=entry[index1++];elsetmp[index++]=entry[index2++];}while(index1<=mid)tmp[index++]=entry[index1++];while(index2<=high)tmp[index++]=entry[index2++];for(index=low;index<=high;index++)entry[index]=tmp[index-low];delete []tmp;traverse(print_out);cout<<endl;}template<class Record>
void Sortable_list<Record>::recursive_merge_sort(int low,int high)
/*Post: The entries of the sortable list betweenindex low and high have been rearranged so thattheir keys are sorted into nondecreasing order.Uses: The contiguous list
*/
{if(high>low){recursive_merge_sort(low,(high+low)/2);recursive_merge_sort((high+low)/2+1,high);merge(low,high);}
}template<class Record>
void Sortable_list<Record>::merge_sort()
/* Post: The entries of the sortable list have been rearranged so thattheir keys are sorted into nondecreasing order.Uses: The contiguous list
*/
{recursive_merge_sort(0,size()-1);
}

【实验结果】

快速排序

【相关实验】

template<class Record>
int Sortable_list<Record>::partition(int low,int high)
/*Pre:  low and high are valid positions of the Sortable_list, with low<=high.Post: The center (or left center) entry in the range between indices low and high of the Sortable_list has been chosen as a pivot. All entries of theSortable_list between indices low and high, inclusive, have been rearrangedso that chosen with keys less than the pivot com before the pivotand the remaining entries come after the pivot. The final position of the pivot is returned.Uses: swap(int,int j) contigious list
*/
{Record pivot;int i,           //used to scan through the listlast_small;  //position of the last key less than pivotswap(low,(low+high)/2);pivot=entry[low];last_small=low;for(i=low+1;i<=high;i++)//At the beginning of each iteration of this loop, we have the following conditions://    If low<j<=last_samll then entry[j].key<pivot//    If last_small<j<i then entry[j].key>=pivot.if(entry[i]<pivot){last_small=last_small+1;swap(last_small,i);  //Move large entry to right and small to left}swap(low,last_small);   //Put the pivot into its proper position.return last_small;
}template<class Record>
void Sortable_list<Record>::recursive_quick_sort(int low,int high)
/*Pre:  low and high are valid positions in the Sortable list.Post: The entries of the Sortable_list have been rearranged so that their keysare sorted into nondecreasing order.Uses: The contiguous list, recursive_quick_sort, partition.
*/
{int pivot_postion;if(low<high){pivot_postion=partition(low,high);recursive_quick_sort(low,pivot_postion-1);recursive_quick_sort(pivot_postion+1,high);}
}template<class Record>
void Sortable_list<Record>::quick_sort()
{recursive_quick_sort(0,count-1);
}
//其他函数见源码

【实验结果】

template<class Record>
void Sortable_list<Record>::insert_heap(const Record ¤t,int low,int high)
/*Pre:  The entries of the Sortable_list between indices low+1 and high,inclusive,form a heap. The entry in position low will be discarded.Post: The entry current has been inserted into the Sortabl_list and the entries,rearranged so that the entries between indices low and high, inclusiveform a heap.
*/
{int large;       //position of child of entry[low] with the larger keylarge=2*low+1;   //large is now the left child of lowwhile(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 lowelse{           //Promote entry[large] and move down the tree entry[low]=entry[large];low=large;large=2*low+1;}}entry[low]=current;traverse(print_out);cout<<endl;
}template<class Record>
void Sortable_list<Record>::build_heap()
/*Post: The entries of the Sortable_list have been rearranged so that it becomes a heapUses: The contiguous list and insert_heap
*/
{int low;for(low=count/2-1;low>=0;low--){Record current=entry[low];insert_heap(current,low,count-1);}
}template<class Record>
void Sortable_list<Record>::heap_sort()
/*Post: The entries of the Sortable_list have been rearranged so that their keysare sorted into nondecreasing order.Uses: The contiguous list, build_heap, insert_heap
*/
{Record current;       //temporary storage for moving entriesint last_unsorted;    //Entries beyond last_unsorted have been sorted.build_heap();         //First phase: Turn the list into a heapfor(last_unsorted=count-1;last_unsorted>0;last_unsorted--){current=entry[last_unsorted];   //Extract the last entry from the listentry[last_unsorted]=entry[0];  //Move top of heap to the endinsert_heap(current,0,last_unsorted-1);  //Restore the heap}
}
//其他函数见源码

【实验结果】

结果分析

（转载请注明作者和出处：http://blog.csdn.net/xiaowei_cqu 未经允许请勿用于商业用途）