(2)堆排序
如果建立的堆满足最大堆的条件，则堆的第一个数据元素arr[0]具有最大的关键字，将arr[0]与arr[n-1]对调，把具有最大关键字的数据元素交换到最后，再对前面的n-1个数据元素使用堆的调整算法，重新建立最大堆，结果把具有次最大关键字的数据元素又上浮到堆顶，即arr[0]的位置，再对调arr[0]和arr[n-2]，…，如此反复执行n-1次，最后得到全部排序好的数据元素序列。
伪代码如下：
template
int tablesize=currentsize;
for(int i=(currentsize-2)/2;i>=0;i--) filterdown(i); //初始建堆 for(int i=currentsize-1;i>=1;i--) {
swap(arr[0],arr[i]);//堆顶元素和最后一个元素交换 currentsize--;
filterdown(0);//重建最大堆
cout<<\第\<<++num<<\趟排序结果为:\; for(int t=0;t num=0; currentsize=tablesize; } <8>归并排序（包括归并算法，一趟归并算法和归并排序） 归并算法 其基本思想是：设有两个有序表A和B，其数据元素个数（表长）分别为n和m，变量i和j分别是表A和表B的当前检测指针；设表C是归并后的新有序表，变量k是它的当前存放指针。开始时i、j、k都分别指向A、B、C三个表的起始位置；然后根据A[i]与B[j]的关键字的大小，把关键字小的数据元素放到新表C[k]中；且相应的检测指针（i或j）和存放指针k增加1.如此循环，当i与j中有一个已经超出表长时，将另一个表中的剩余部分照抄到新表C[k]~C[m+n]中。 下面的归并算法中，两个待归并的有序表首尾相接存放在数组sourcetable.arr[]中，其中第一个表的下标范围从left到mid，另一个表的下标范围从mid+1到right。前一个表中有mid-left+1个数据元素，后一个表中有right –mid个数据元素。归并后得到的新有序表有right –mid个数据元素。归并后得到的新有序表存放在另一个辅助数组mergedtable.arr[]中，其下标范围从left到right。 伪代码如下： template sortlist int i=left,j=mid+1,k=left;//指针初始化 //i是前一段的当前元素位置，j是后一段的当前元素位置，k是辅助数组的当前位置 while(i<=mid&&j<=right) if(sourcetable.arr[i]<=sourcetable.arr[j]) {mergedtable.arr[k]=sourcetable.arr[i];i++;k++;} else{mergedtable.arr[k]=sourcetable.arr[j];j++;k++;} if(i<=mid) for(int p=k,q=i;q<=mid;p++,q++) mergedtable.arr[p]=sourcetable.arr[q];//把前一段复制到mergedtable else for(int p=k,q=j;q<=right;p++,q++) mergedtable.arr[p]=sourcetable.arr[q];//把后一段复制到mergedtable } 一趟归并算法 设数组sourcetable.arr[0]到sourcetable.arr[n-1]中的n个数据元素已经分为一些长度为len的归并项，将这些归并项两两归并，归并成一些长度为2len的归并项，结果放到mergedtable.arr[]中。如果n不是2len的整数倍，则一趟归并到最后，可能遇到两种情况： 剩下一个长度为len的归并项和一个长度不足len的归并项，可用一次merge算法，将它们归并成一个长度小于2len的归并项。 只剩下一个归并项，其长度小于或等于len，可将它直接复制到数组mergedtable.arr[]中。 伪代码如下： template sortlist int i=0; while(i+2*len<=currentsize-1)//表示至少有个子序列 { merge(sourcetable,mergedtable,i,i+len-1,i+2*len-1); i+=2*len; } if(i+len<=currentsize-1)//若只有最后两个子序列 merge(sourcetable,mergedtable,i,i+len-1,currentsize-1); else//若只有最后一个子序列 } 归并排序 在一趟归并算法的基础上，实现两路归并排序算法。在两路归并排序算法中，初始排序表存放在数组table.arr[]中,第一趟归并将table.arr[]中的归并项两两归并，结果存放在辅助数组temptable.arr[]中。第二趟将temptable.arr[]中的归并项两两归并，结果放回原数组table.arr[]中，如此反复进行。为了将最后归并结果仍放在数组table.arr[]中，归并趟数应为偶数。如果做奇数趟就能完成时，最后还需要执行一次一趟归并过程，由于这时的归并项长度len>=n，因此在则趟归并中while循环不执行，只做把temptable.arr[]中的数据元素复制到table.arr[]的工作。 伪代码如下： template void sortlist {//按数据元素关键字非递减的顺序对排序表table中数据元素进行递归排序 sortlist while(len mergepass(table,temptable,len);len*=2; mergepass(temptable,table,len);len*=2; } num=0; } <9>主函数 主要功能是显示主菜单，以及对各种排序的调用 伪代码如下： int main()//主函数 { for(int j=i;j<=currentsize-1;j++) mergedtable.arr[j]=sourcetable.arr[j]; if(len<=currentsize-1) { if(num cout<<\第\<<++num<<\趟排序结果为:\; for(int t=0;t cout< cout<<\ ***********************************************************************\< cout<<\< cout<<\可供选择的排序方法===========================\< =======================================================================\< if(ch=='0') {cout<<\您已成功退出该系统!\< int n,number; if(ch>='0'&&ch<='7') { cout<<\输入您要进行排序的数的个数：\; cin>>n; cout<<\请输入\< {cin>>number;table.insert(i,number);} switch(ch) { case '1': cout<<\您选择的是直接插入排序*******\\n\< system(\); break; case '2': cout<<\您选择的是折半插入排序*******\\n\<
