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

内容发布更新时间 : 2024/12/23 6:45:12星期一 下面是文章的全部内容请认真阅读。

int finish=0;//0表示还没有排好序 while(i

finish=1;//排序结束标志置为,假定已经排好序 for(int j=0;jarr[j+1])//逆序 {

swap(arr[j],arr[j+1]);//相邻元素交换位置 finish=0;

}//排序结束标志置为,表示本趟发生了交换，说明还没有排好序 i++;

cout<<\第\<<++num<<\趟排序结果为:\; for(int t=0;t

num=0; }

template

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

int k;

for(int i=0;i

k=i;

for(int j=i+1;j

k=j;//k 指示当前序列中最小者的位置 if(k!=i)//最小关键字的数据元素位置不等于i swap(arr[i],arr[k]);

cout<<\第\<<++num<<\趟排序结果为:\; for(int t=0;t

num=0; }

template //快速排序

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

int i=low,j=high;

type temp=arr[low];//取区间第一个位置为基准位置 if(i

{

while(i

while(i

if(i=arr[i])i++;

if(i

}

arr[i]=temp;//将基准元素就位

cout<<\第\<<++x<<\趟排序结果为:\; for(int t=0;t

quicksort(low,i-1);//在左子区间递归进行快速排序 quicksort(i+1,high);//在右子区间递归进行快速排序 } }

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

num=0;

currentsize=tablesize; }

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

cout<<\第\<<++num<<\趟排序结果为:\; for(int t=0;t

cout<

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; }

int main()//主函数 {

cout<<\

***********************************************************************\<

cout<<\<

int c=1; char ch,cc; int n1=0; while(c!=0) {cout<<

\<

\可供选择的排序方法==============================\<