作者和出处：http://blog.csdn.net/xiaowei_cqu，这女孩写得文章不错，大家可以去看一下，受益匪浅。
排序算法
本次试验重点实现：希尔排序、归并排序、快速排序、堆排序
插入排序
简单说就是每次选未排序的队列中最小的条目插入到已排序队列的最后：
选择排序
选择排序和插入有点像，是每次从拿未排序中的第一个条目插入到已排序中应该插入的位置：
希尔排序
1.编写函数shell_sort。函数中我们从首先定义increment=0，观察题目要求，可以得到在循环中有这样的关系increment=increment/2;使用循环将每次分组后的每组排列，排列我们再增加函数sort_interval（）；在每组的排序中使用的直接插入排序，所以可以这样实现sort_interval：每次定义一个临时的Sortable_list对象tmp记录每次分组的小组，对tmp使用insertion_sort，进而我们编写函数insertion_sort（）；
2.实现表的排序一个重要的步骤是将Record换到相应位置，即交换，所以编写函数swap；
3.为了输出每趟排序结果，我们再编写一个全局函数print_out，由List的成员函数traverse（）调用；调用的过程在置于swap之中，即每次有交换（或看做移动）则看做一趟排序。
相应算法函数如下：
希尔排序是插入排序的一种，是针对直接插入排序算法的改进。
希尔排序的基本思想是：先取一个小于count的增量increment，把表中Record分为increment组，所有距离为increment的Record为同一组，现在各组中进行直接插入排序（insert_sort），然后减小increment重复分组和排序，知道increment=1，即所有Record放在同一组中进行直接插入排序为止。
希尔排序的基本思想是：先取一个小于count的增量increment，把表中Record分为increment组，所有距离为increment的Record为同一组，现在各组中进行直接插入排序（insert_sort），然后减小increment重复分组和排序，知道increment=1，即所有Record放在同一组中进行直接插入排序为止。
【相关实验】
首先从类表List中派生子表Sortable_list。为了方便定义，我们可以重载这样的构造函数
- template<classRecord>
- Sortable_list<Record>::Sortable_list(constRecordA[],intsize)
- {
- for(inti=0;i<size;i++)
- insert(i,A[i]);
- }
2.实现表的排序一个重要的步骤是将Record换到相应位置，即交换，所以编写函数swap；
3.为了输出每趟排序结果，我们再编写一个全局函数print_out，由List的成员函数traverse（）调用；调用的过程在置于swap之中，即每次有交换（或看做移动）则看做一趟排序。
相应算法函数如下：
copy
- voidSortable_list<Record>::shell_sort()
- /*Post:TheentriesoftheSortable_listhavebeenrearrangedsothatthekeysin
- alltheentriesaresortedintonondecreasingorder.
- Uses:sort_interval.
- */
- intincrement,//spacingofentriesinsublist
- start;//startingpointofsublist
- increment=count;
- do{
- increment=increment/2;
- for(start=0;start<increment;start++){
- sort_interval(start,increment);//modifiedinsertionsort
- traverse(print_out);
- cout<<endl;
- }
- }while(increment>1);
- voidSortable_list<Record>::sort_interval(intstart,87); background-color:inherit; font-weight:bold">intincrement)
- Sortable_list<Record>temp;
- intj=0;
- inti=start;i<size();i=i+increment){
- Recordtemp_record;
- retrieve(i,temp_record);
- temp.insert(j,temp_record);
- j++;
- temp.insertion_sort();
- j=0;
- intk=start;k<size();k+=increment){
- temp.retrieve(j,108); list-style:decimal-leading-zero outside; color:inherit; line-height:18px"> replace(k,248); line-height:18px"> }
- voidSortable_list<Record>::insertion_sort()
- Uses:MethodsfortheclassRecord;thecontiguousList
- intfirst_unsorted;//positionoffirstunsortedentry
- intposition;//searchessortedpartoflist
- Recordcurrent;//holdstheentryemporarilyremovedfromlist
- for(first_unsorted=1;first_unsorted<count;first_unsorted++)
- if(entry[first_unsorted]<entry[first_unsorted-1]){
- position=first_unsorted;
- current=entry[first_unsorted];//Pullunsortedentryoutofthelist.
- do{//Shiftallentriesuntiltheproperpositionisfound
- entry[position]=entry[position-1];
- position--;//positionifempty.
- while(position>0&&entry[position-1]>current);
- entry[position]=current;
- //其他辅助函数见源文件
【实验结果】
归并排序
归并排序是采用分治的思想将两个已排序的表合并成一个表
归并排序算法的基本思想是：先将一个表分成两个表（当个数是奇数时，使左表的元素比右表多一）。对两个表分别进行归并排序，然后将两个已排序好的表合并。合并的思路就像将两罗纸牌混成一摞，每次取顶上最小的纸牌。
归并排序算法的基本思想是：先将一个表分成两个表（当个数是奇数时，使左表的元素比右表多一）。对两个表分别进行归并排序，然后将两个已排序好的表合并。合并的思路就像将两罗纸牌混成一摞，每次取顶上最小的纸牌。
1.仍旧使用上述的Sortable_list
2.根据归并排序的思想，每次子表仍旧使用归并排序，可以通过递归实现。所以编写递归函数recursive_merge_sort()，要把已排序好的子表合并，所以编写合并子表的辅助函数merge（）
3.为了输出每趟排序结果，在归并时merge中加入traverse(print_out) //但因为递归调用的问题，很多次我们还是看不到过程
2.根据归并排序的思想，每次子表仍旧使用归并排序，可以通过递归实现。所以编写递归函数recursive_merge_sort()，要把已排序好的子表合并，所以编写合并子表的辅助函数merge（）
3.为了输出每趟排序结果，在归并时merge中加入traverse(print_out) //但因为递归调用的问题，很多次我们还是看不到过程
- classRecord>
- voidSortable_list<Record>::merge(intlow,87); background-color:inherit; font-weight:bold">inthigh)
- {
- Record*tmp=newRecord[high-low+1];
- intindex=0;
- intindex1=low,mid=(low+high)/2,index2=mid+1;
- while(index1<=mid&&index2<=high){
- if(entry[index1]<entry[index2])
- tmp[index++]=entry[index1++];
- else
- tmp[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;
- }
- voidSortable_list<Record>::recursive_merge_sort(/*Post:Theentriesofthesortablelistbetween
- indexlowandhighhavebeenrearrangedsothat
- theirkeysaresortedintonondecreasingorder.
- Uses:Thecontiguouslist
- */
- {
- if(high>low){
- recursive_merge_sort(low,(high+low)/2);
- recursive_merge_sort((high+low)/2+1,high);
- merge(low,high);
- classRecord>
- voidSortable_list<Record>::merge_sort()
- /*Post:Theentriesofthesortablelisthavebeenrearrangedsothat
- recursive_merge_sort(0,size()-1);
- }
【实验结果】
快速排序
快速排序是对冒泡排序的一种改进。
快速排序算法的基本思想是：每一趟排序中找一个点pivot，将表分割成独立的两部分，其中一部分的所有Record都比pivot小，另一部分比pivot大，然后再按此方法对这两部分数据分别进行快速排序。
快速排序算法的基本思想是：每一趟排序中找一个点pivot，将表分割成独立的两部分，其中一部分的所有Record都比pivot小，另一部分比pivot大，然后再按此方法对这两部分数据分别进行快速排序。
【相关实验】
1.仍旧使用上述的Sortable_list。
2.根据快速排序的思想，每趟排序将表分成两部分然后仍旧进行快速排序，所以可以通过递归实现，而为了调用递归函数，我们首先编写给定要排序范围的参数的函数recursive_quick_sort(int low,int high)//之所以不将开始的quick_sort直接写作递归函数，是为了避免输入参数而方便用户调用。另外需要一个partition函数，返回每趟排序之后的分点。
3.为了输出每趟排序，我的想法是在每次递归中使用traverse（print_out）输出，但却不是想象的结果。因为递归是每次递归出来之后才执行函数print_out，除了前几次可以看到结构，后来都是在排序好之后…所以我们仍旧通过swap函数实现输出。
2.根据快速排序的思想，每趟排序将表分成两部分然后仍旧进行快速排序，所以可以通过递归实现，而为了调用递归函数，我们首先编写给定要排序范围的参数的函数recursive_quick_sort(int low,int high)//之所以不将开始的quick_sort直接写作递归函数，是为了避免输入参数而方便用户调用。另外需要一个partition函数，返回每趟排序之后的分点。
3.为了输出每趟排序，我的想法是在每次递归中使用traverse（print_out）输出，但却不是想象的结果。因为递归是每次递归出来之后才执行函数print_out，除了前几次可以看到结构，后来都是在排序好之后…所以我们仍旧通过swap函数实现输出。
copy
