(2)堆排序

如果建立的堆满足最大堆的条件，则堆的第一个数据元素arr[0]具有最大的关键字，将arr[0]与arr[n-1]对调，把具有最大关键字的数据元素交换到最后，再对前面的n-1个数据元素使用堆的调整算法，重新建立最大堆，结果把具有次最大关键字的数据元素又上浮到堆顶，即arr[0]的位置，再对调arr[0]和arr[n-2]，…，如此反复执行n-1次，最后得到全部排序好的数据元素序列。

伪代码如下：

template //堆排序 void sortlist::heapsort() {

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 void

sortlist::merge(sortlist&sourcetable,sortlist&mergedtable,const int left,const int mid,const int right) {

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 template void

sortlist::mergepass(sortlist&sourcetable,sortlist&mergedtable,const int len) {

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::mergesort(sortlist &table )

{//按数据元素关键字非递减的顺序对排序表table中数据元素进行递归排序 sortlist temptable; int len=1;

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<<\可供选择的排序方法===========================\<

=======================================================================\<>ch;

if(ch=='0') {cout<<\您已成功退出该系统!\<

int n,number;

if(ch>='0'&&ch<='7') {

cout<<\输入您要进行排序的数的个数：\; cin>>n;

cout<<\请输入\<table(n); for(int i=0;i

{cin>>number;table.insert(i,number);} switch(ch) {

case '1':

cout<<\您选择的是直接插入排序*******\\n\<

system(\); break; case '2':

cout<<\您选择的是折半插入排序*******\\n\<