C语言排序源代码以及word实验报告

1、源程序：（程序结果可以运行出来）#include "st蟠校盯昂dio.h"#include 媪青怍牙"stdlib.h"#include "time.h"//计时#define ERROR 0#define OK 1#define OVERFLOW -2#define MAXSIZE 100000 //用户自己规定排序的数字的长度typedef int Status;typedef struct{ int *r; // r[0]闲置 int length; //顺序表的总长度}Sqlist;//构造一个空线性表Status InitSqlist(Sqlist &L){L.r=(int *)malloc(MAXSIZE*sizeof(int)); //分配存储空间if(!L.r) {printf("存储分配失败！");exit(0);} //存储分配失败L.length=0;//初始长度为0return OK;}//输入随机数并显示在界面上Status ScanfSqlist(int &N,Sqlist &L){int i;printf("请输入要排序的元素个数N: ");scanf("%d",&N);for(i=1;i<=N;i++)L.r[i]=rand(); //随机产生样本整数printf("\n\n");printf(" 随机产生了%d个随机数，它们是：\n",N);for(i=1;i<=N;i++){printf("%7.2d ",L.r[i]);}printf("\n");L.length=N; //存储线性表的长度return OK;}//输出排序之后的数据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; //插入点在高半区}}//whilefor(j=i-1;j>=high+1;j--) //插入点后的数据后移{L.r[j+1]=L.r[j]; }L.r[high+1]=L.r[0]; //将数据插入}//forreturn OK;}/******************************************************************************** 希尔排序*********************************************************************************/ //参考书P272算法10.4及10.5Status ShellInsert(Sqlist &L,int dk) //希尔插入排序{int i,j; //前后位置的增量是dkfor(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++;}elsem++;}}i=1;while(p!=NULL) //将链表转换为顺序表{L.r[i]=p->key;i++;p=p->next;}return OK;}//**************************************// 主函数//**************************************void main(){Sqlist L;Sqlist L0;InitSqlist(L); //初始化LInitSqlist(L0);int m,i; char choice='z';clock_t start, finish; //定义clock_t用于计时double duration;//向L中输入元素printf("\n *********************************************************************** \n");printf(" \n");printf(" 排序算法的比较系统 \n");printf(" \n");printf(" *********************************************************************** \n"); printf(" 以下是各个排序算法的代号：\n\n");printf(" 1、直接插入排序 \n");printf(" 2、折半插入排序 \n");printf(" 3、起泡排序 \n");printf(" 4、快速排序\n");printf(" 5、选择排序\n");printf(" 6、堆排序\n");printf(" 7、基数排序\n"); printf(" 8、退出该系统\n\n");ScanfSqlist(m,L0);printf("\n");printf(" 1、直接插入排序 \n");printf(" 2、折半插入排序 \n");printf(" 3、起泡排序 \n");printf(" 4、快速排序\n");printf(" 5、选择排序\n");printf(" 6、堆排序\n");printf(" 7、基数排序\n"); printf(" 8、退出该系统\n\n");printf("\n请选择排序的方式,数字1-7: ");scanf("%d",&choice); //选择排序方式赋值choice，用于后面的函数选择while(choice<1||choice>8){printf("输入方式有误。\n请输入1-7选择排序方式，或者选择8退出系统");scanf("%d",&choice);}while(choice!=8){for(i=1;i<=L0.length;i++)L.r[i]=L0.r[i];L.length=L0.length;switch(choice){case 1://直接插入排序start = clock();InsertSort(L);finish = clock();break;case 2://折半插入排序start = clock();BInsertSort(L); finish = clock();break;case 3://起泡排序start = clock();BubbleSort(L);finish = clock();break;case 4://快速排序start = clock();QuickSort(L); finish = clock();break;case 5://选择排序start = clock();ChooseSort(L);finish = clock();break;case 6://堆排序start = clock();HeapSort(L);finish = clock();break;case 7://基数排序start = clock();RadixSort(L);finish = clock();break;case 8://直接退出break;}PrintfSqlist(m,L); //输出数据和L的长度duration = (double)(finish - start) / CLOCKS_PER_SEC; //输出算术时间printf("\n本次排序运算所用的时间是：%lf seconds\n",duration); printf(" 本次排序结束。\n");printf(" ___________________________________________________________________\n"); printf(" 继续本系统吗？\n\n"); printf(" 以下是各个排序算法的代号：\n"); printf(" 1、直接插入排序\n"); printf(" 2、折半插入排序\n"); printf(" 3、起泡排序\n"); printf(" 4、快速排序\n"); printf(" 5、选择排序\n"); printf(" 6、堆排序\n"); printf(" 7、基数排序\n"); printf(" 8、退出该系统\n");printf("\n请请输入1-7选择排序方式，或者选择8退出系统:");scanf("%d",&choice);while(choice<1||choice>8){printf("输入方式有误。\n请输入1-7选择排序方式，或者选择8退出系统");scanf("%d",&choice);}}}

2、word文档的内容：一、实验目标：（1）几种排序算法在平均情况下哪一个更快。（2）加深对时间复杂度概念的理解。实验任务：（1）实现几种排序算法（selectionsort,insertionsort,bottomupsort,quicksort,堆排序）。对于快速分类，SPLIT中的划分元素采用三者A(low)，A(high)，A((low+high)/2)中其值居中者。（2）随机产生20组数据（比如n=5000i，1≤i≤20）。数据均属于范围（0，105）内的整数。对于同一组数据，运行以上几种排序算法，并记录各自的运行时间（以毫秒为单位）。（3）根据实验数据及其结果来比较这几种分类算法的平均时间和比较次数，并得出结论。实验设备及环境：PC；C/C++等编程语言。二、实验主要步骤：(1)明确实验目标和具体任务；(2)理解实验所涉及的几个分类算法；(3)编写程序实现上述分类算法；(4)设计实验数据并运行程序、记录运行的结果；(5)根据实验数据及其结果得出结论；(6)实验后的心得体会。

3、三、程序所用到的排序方法("1、直接插入排序\n");printf("2、折半插入排序\n"); printf("3、起泡排序\n"); printf("4、快速排序\n"); printf("5、选择排序\n"); printf("6、堆排序\n"); printf("7、基数排序\n");printf("8、退出该系统\n");

4、四、源代码#include"stdio.h"#include"stdlib.h媪青怍牙"#include"time.h"//计时printf("本次排序结束。\n");printf("___________________________________________________________________\n"); printf("继续本系统吗？\n\n"); printf("以下是各个排序算法的代号：\n");printf("1、直接插入排序\n");printf("2、折半插入排序\n"); printf("3、起泡排序\n"); printf("4、快速排序\n"); printf("5、选择排序\n"); printf("6、堆排序\n"); printf("7、基数排序\n");printf("8、退出该系统\n");printf("\n请请输入1-7选择排序方式，或者选择8退出系统:");scanf("%d",&choice);while(choice<1||choice>8){printf("输入方式有误。\n请输入1-7选择排序方式，或者选择8退出系统");scanf("%d",&choice);}}}

5、五、实验结果分析及结论：实验结果表明,选择排序用时普遍比其它算法大,自顶向上合并排序时间普遍较少,尤其是当数据量变得很大的时候,选择排序的速度变得远远不及自顶向上合并排序算法,大出好几百倍.另外,插入排序在当数据量变大时花费的时间也变得很长.快速排序和堆排序处于不确定的情况,不稳定性表现比较明显.但是还是一种比较快的C语言算法.