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

. . .

left,const int mid,const int right);//两路归并算法 };

template //直接插入排序 void sortlist::insertionsort() { type temp; int j; for(int i=1;i<=currentsize-1;i++) { temp=arr[i];j=i-1; while(j>=0&&temp

template //折半插入排序 void sortlist::binaryinsertsort() { type temp; int left,right; for(int i=1;i=left;k--)//向后移动 arr[k+1]=arr[k]; arr[left]=temp; cout<<\第\<<++num<<\趟排序结果为:\; for(int t=0;t

..........

. . .

template //冒泡排序 void sortlist:: bubblesort() { int i=1; int finish=0;//0表示还没有排好序 while(iarr[j+1])//逆序 { swap(arr[j],arr[j+1]);//相邻元素交换位置 finish=0; }//排序结束标志置为,表示本趟发生了交换，说明还没有排好序 i++; cout<<\第\<<++num<<\趟排序结果为:\; for(int t=0;t

template

void sortlist::selectsort()//简单选择排序 { int k;

for(int i=0;i

template //快速排序

void sortlist::quicksort(int low,int high)//在待排序区间[low,high]上，递归地进行快速排序

..........

. . .

{ int i=low,j=high; type temp=arr[low];//取区间第一个位置为基准位置 if(i=arr[i])i++; if(i

template //建立最大堆

void sortlist::filterdown(const int start)

{//向下调整使从start开始到currentsize-1为止的子表成为最大堆 int i=start,j=2*i+1;//j为i的左孩子 int tablesize=currentsize; type temp=arr[i]; while(j<=currentsize-1) { if(j=arr[j])break; else{arr[i]=arr[j];i=j;j=2*j+1; } } arr[i]=temp; }

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

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 }

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//若只有最后一个子序列 for(int j=i;j<=currentsize-1;j++) mergedtable.arr[j]=sourcetable.arr[j]; if(len<=currentsize-1) {if(num

template

void sortlist::mergesort(sortlist &table )

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

int main()//主函数 {

cout<<\ ***********************************************************************\<

cout<<\<

<

\=========\

..........