|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
利用随机函数产生 30000 个随机整数, 利用插入排序、 起泡排序、 选择排序、 快速排序、 堆排序、 归并排序等排序方法进行排序, 并统计每一种排序上机所花费的时间和次数。- Status PrintfSqlist(int N,Sqlist L)
- {
- int i;
-
- printf("数据个数:");//输出数据个数
- printf("%d\n",L.length);
-
- printf("排序后的数据:(从左向右依次增大)\n");//输出数据
- for(i=1;i<=N;i++)
- printf("%7.2d ",L.r[i]);
- printf("\n");
-
- return OK;
- }
- //***************************************************************
- // 直接插入排序
- //***************************************************************
- Status InsertSort(Sqlist &L) //参考书P265算法10.1
- {
- int i,j;
- if(L.length==0)
- {
- printf("要排序的数据为空!");
- return ERROR;
- }
- for(i=2;i<=L.length;i++)
- {
- if(L.r[i]<L.r[i-1]) //将L.r[i]插入有序子表
- {
- L.r[0]=L.r[i]; //复制为监视哨
- L.r[i]=L.r[i-1];
- for(j=i-2;L.r[0]<L.r[j];j--)
- {
- L.r[j+1]=L.r[j]; //记录后移
- }
-
- L.r[j+1]=L.r[0]; //插入到正确位置
- }
- }
- return OK;
- }
- //***************************************************************
- // 折半插入排序
- //***************************************************************
- Status BInsertSort(Sqlist &L) //参考书P267算法10.2
- {
- int i,j,mid,low,high;
- if(L.length==0)
- {
- printf("要排序的数据为空!");
- return ERROR;
- }
-
- for(i=2;i<=L.length;i++)
- {
- L.r[0]=L.r[i]; //将L.r[i]暂存在L.r[0]
- low=1;
- high=i-1;
-
- while(low<=high) //在r[low..high]中折半查找有序插入的位置
- {
- mid=(low+high)/2;
-
- if(L.r[0]<L.r[mid]) //插入点在低半区
- {
- high=mid-1;
- }
- else
- {
- low=mid+1; //插入点在高半区
- }
- }//while
- for(j=i-1;j>=high+1;j--) //插入点后的数据后移
- {
- L.r[j+1]=L.r[j];
- }
- L.r[high+1]=L.r[0]; //将数据插入
- }//for
- return OK;
- }
- /********************************************************************************
- 希尔排序
- *********************************************************************************/
- //参考书P272算法10.4及10.5
- /*Status ShellInsert(Sqlist &L,int dk) //希尔插入排序
- {
- int i,j; //前后位置的增量是dk
- for(i=dk+1;i<=L.length;i++) //r[0]只是暂存单元,不是哨兵,
- {
- if(L.r[i]<L.r[i-dk]) //将L.r[i]插入有序增量子表
- {
- L.r[0]=L.r[i]; //暂存L.r[0]
- for(j=i-dk;j>0 && L.r[0]<L.r[j];j-=dk)
- {
- L.r[j+dk]=L.r[j]; //记录后移,查找插入位置
- }
- L.r[j+dk]=L.r[0]; //插入
- }
- }
- return OK;
- }
- Status ShellSort(Sqlist &L,int dlta[5],int t) //希尔排序
- {
- int i;
- if(L.length==0)
- {
- printf("要排序的数据为空!");
- return ERROR;
- }
- for(i=0;i<t;i++)
- {
- ShellInsert(L,dlta[i]); //一趟增量为dlta[k]的插入排序
- }
- return OK;
- }
- */
- //**************************************************************
- // 起泡排序
- //**************************************************************
- Status BubbleSort(Sqlist &L)
- {
- int i,j,t;
- if(L.length==0)
- {
- printf("要排序的数据为空!");
- return ERROR;
- }
-
- for(i=1;i<=L.length-1;i++)
- {
- for(j=1;j<=L.length-i;j++)
- {
- if(L.r[j]>L.r[j+1]) //前面的数据>后面数据时
- {
- t=L.r[j+1];
- L.r[j+1]=L.r[j];
- L.r[j]=t; //将元素交换
- }
- }
- }
- return OK;
- }
- //****************************************************
- // 快速排序
- //****************************************************
- int Partition(Sqlist &L, int low, int high) //交换顺序表中子表L.r[low..high]的记录,使得枢轴记录到位,并返回其所在位置,此时在它之前(后)的记录均不大于它
- {
- int pivotkey; //记录关键字
- L.r[0]=L.r[low]; //用子表的第一个纪录作枢轴纪录
- pivotkey=L.r[low]; //用枢轴纪录关键字
- while (low<high)
- {
- while(low<high && L.r[high]>=pivotkey)
- {
- high--;
- }
- L.r[low]= L.r[high]; //将比枢轴记录小的记录移到低端
- while(low<high && L.r[low]<=pivotkey)
- {
- low++;
- }
- L.r[high]=L.r[low]; //将比枢轴记录大的数移到高端
- }
- L.r[low]=L.r[0]; //枢轴记录到位
- return low;
- }//Partition函数
- void Qsort (Sqlist &L,int low, int high)
- {
- int pivotloc;
- if (low<high) //长度大于1,可以进行
- {
- pivotloc=Partition(L, low ,high);
- Qsort(L,low,pivotloc-1); //对低子表递归排序,pivotloc是枢轴位置
- Qsort(L,pivotloc+1,high); //对高子表递归排序
- }
- }//Qsort函数
- Status QuickSort (Sqlist &L)
- {
- if(L.length==0)
- {
- printf("要排序的数据为空!");
- return ERROR;
- }
- Qsort(L,1,L.length);
- return OK;
- }//QuickSort
- //**********************************************
- // 选择排序
- //**********************************************
- Status ChooseSort(Sqlist &L)
- {
- int i,j,k,t;
- if(L.length==0)
- {
- printf("没有数据!");
- return ERROR;
- }
-
- for(i=1;i<=L.length;i++) //排序的趟数
- {
- k=i;
- for(j=i+1;j<=L.length;j++) //比较第i个元素以及其后的数据中最小的
- {
- if(L.r[j]<L.r[k])
- k=j;
- }
-
- if(i!=j) //将最小数据赋值给L.r[i]
- {
- t=L.r[i];
- L.r[i]=L.r[k];
- L.r[k]=t;
- }
- }
- return OK;
- }
- //****************************************
- // 堆排序
- //****************************************
- Status HeapAdjust(Sqlist &L,int s,int m) //调整L.r[s]的关键字,使L.r[s~m]成大顶堆
- {
- int i;
- L.r[0]=L.r[s];
- for(i=2*s;i+1<=m;i*=2) //沿数据较大的孩子结点向下筛选
- {
- if(i<m && L.r[i]<L.r[i+1]) //i为数据较大的记录下标
- i++;
-
- if(L.r[0]>=L.r[i]) //L.r[0]插入在S位置上
- break;
-
- L.r[s]=L.r[i];
- s=i;
- }
- L.r[s]=L.r[0]; //插入新数据
- return OK;
- }
- Status HeapSort(Sqlist &L) //堆排序
- {
- int i,t;
- if(L.length==0)
- {
- printf("没有数据!");
- return ERROR;
- }
- for(i=L.length/2;i>0;i--)
- HeapAdjust(L,i,L.length);
-
- for(i=L.length;i>1;i--)
- {
- t=L.r[1]; //将堆顶记录和当前未经排序的子序列L.r[1..i]中最后一个记录互换
- L.r[1]=L.r[i];
- L.r[i]=t;
-
- HeapAdjust(L,1,i-1); //将L.r[1..i-1]重新调整为大顶堆
- }
- return OK;
- }
- //**************************************************
- // 基数排序
- //**************************************************
- typedef struct node{
- int key;
- node *next;
- }RecType;
- Status RadixSort(Sqlist L)
- {
- int t,i,j,k,d,n=1,m;
- RecType *p,*s,*q,*head[10],*tail[10]; //定义各链队的首尾指针
-
- for(i=1;i<=L.length;i++) //将顺序表转化为链表
- {
- s=(RecType*)malloc(sizeof(RecType));
- s->key=L.r[i];
- if(i==1) //当为第一个元素时
- {
- q=s;
- p=s;
- t++;
- }
- else
- {
- q->next=s; //将链表连接起来
- q=s;
- t++;
- }
- q->next=NULL;
- }
-
- d=1;
-
- while(n>0) //将每个元素分配至各个链队
- {
- for(j=0;j<10;j++) //初始化各链队首、尾指针
- {
- head[j] = NULL;
- tail[j] = NULL;
- }
- while(p!=NULL) //对于原链表中的每个结点循环
- {
- k=p->key/d;
- k=k%10;
- if(head[k]==NULL) //进行分配
- {
- head[k]=p;
- tail[k]=p;
- }
- else
- {
- tail[k]->next=p;
- tail[k]=p;
- }
- p=p->next; //取下一个待排序的元素
- }
-
- p=NULL; //用于收集第一个元素时的判断
-
- for(j=0;j<10;j++) //对每一个链队循环, 搜集每一个元素
- {
- if(head[j]!=NULL) //进行搜集
- {
- if(p==NULL)
- {
- p=head[j];
- q=tail[j];
- }
- else
- {
- q->next=head[j];
- q=tail[j];
- }
- }
- }
- q->next=NULL; //最后一个结点的next置为空
- d=d*10;
-
- n=0;
- m=1;
- while(m<=L.length) //判断当L中的元素都除d后是不是都为零了
- {
- if((L.r[m]/d)!=0)
- {
- n++;
- m++;
- }
- else
- m++;
- }
- }
-
- i=1;
- while(p!=NULL) //将链表转换为顺序表
- {
- L.r[i]=p->key;
- i++;
- p=p->next;
- }
- return OK;
- }
复制代码
求助大佬 运行结果就是 算法名称 排序次数 运行时间 这种格式 请大佬帮帮忙 |
|