数据结构课程设计报告---几种排序算法的演示(附源代码) 下载本文

(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\<