noj大作业参照内容

作业名称：算法演示程序学 院：航海学院班 级：03011403学 号：2013300951姓 名：苏和团队组成：西北工业大学2022年3月23日 1、问题与背景（描述程序所要解决的问题或应用背景）C语言经过几十年的发展已经发展出多种多样的的排序方法，网上的解释和 代码良莠不齐，许多具有严重的错误，给学习者打来极大的不便。因此，我将目前比较流行的7种排序法:1.冒泡排序 2.选择排序 3.插入排序4.快速排序 5堆排序 6归并排序7.基数排序加以总结，标明注释，成为这个演示程序，以供交流学习使用。 2、开发工具（列出所使用的开发工具和第3方开发库）Code:block3、主要功能（详细说明程序的功能）基本功能：本程序可实现对100个及以下的数据排列的功能。拓展功能：1.选择不同的排序法进行排序。 2.选择数据正序排列，还是逆序排列。4、设计内容（详细描述解决问题的原理和方法、算法、数据结构等）本程序的数据变换主要在数组中进行。1. 冒泡排序相邻两个记录之间进行比较和互换，使较小的记录逐渐从底部移向顶部。一次排序后最大的记录沉底，再比较前n-1个记录直到最后一次排列时只有两个记录。排列结束后最小的记录自然上浮至第一位。2. 选择排序第i趟选择排序通过n-i次关键码的比较，从n-i+1个记录中选出关键码最小的记录，并和记录i交换。3. 插入排序 把新插入记录的关键码与已排好序的逐个比较，但找到第一个比其大的记录时，该记录之前即为插入位置k。从序列最后开始到该记录，逐个后移一个单元，将新纪录插入k位置。如果新纪录比其他记录都大，则插入到最后。4. 快速排序 通过一趟排序将要排序的记录分为两部分，其中一部分比另一部分都要小。再按此方法对两组数据分别进行递归快速排序，从而使序列成为有序序列。5. 堆排序 先将初始文件R1.n建成一个大根堆，此堆为初始的无序区。再将关键字最大的记录R1(即堆顶)和无序区的最后一个记录Rn交换，由此得到新的无序区R1.n-1和有序区Rn。由于交换后新的根R1可能违反堆性质，故应将当前无序区R1.n-1调整为堆。然后再次将R1.n-1中关键字最大的记录R1和该区间的最后一个记录Rn-1交换，由此得到新的无序区R1.n-2和有序区Rn-1.n，同样要将R1.n-2调整为堆，直到无序区只有一个元素为止。6. 归并排序 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。首先申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。设定两个指针，最初位置分别为两个已经排序序列的起始位置。比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。重复直到某一指针超出序列尾。将另一序列剩下的所有元素直接复制到合并序列尾。7. 基数排序 基数排序法又称“桶子法”（bucketsort）或binsort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用。 对数据来说，首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中。接下来将这些桶子中的数值重新串接起来。接着再进行一次分配，这次是根据十位数来分配。接下来将这些桶子中的数值重新串接起来。重复以上过程直到最高位，这时候整个数列已经排序完毕。5、程序文件与工程名称（标出程序中所有文件名、工程名称及其说明）工程的名称：排序算法演示程序包含的程序原文件如下：1.sort.cpp 主函数、输入和输出数据、显示菜单、选择排序方法2. sort_fun.cpp 实现7种排序的函数3. myh.h 7种排序函数及其附属函数的声明6、函数模块（程序中各个函数的原型声明及其说明）void Bubble(int a,int n)； 冒泡排序void Selection(int a,int n)； 选择排序void Insertion(int a,int n)； 插入排序void Quick(int a,int n,int left,int right)； 快速排序void Shift(int a , int i , int m)； 建堆void Heap(int a , int n)； 堆排序void MergeSort(int R,int low,int high)； 归并排序void Merge(int *R,int low,int m,int high)； 元素比较void Bucket(int *p , int n)； 基数排序int getLoopTimes(int num)； 获取数字的位数int findMaxNum( int *p , int n)； 查询数组中的最大数void sort2(int *p , int n , int loop)；将数字分配到各自的桶中，然后按照桶的顺序输出排序结果7、使用说明（运行程序的小型说明书）1. 打开程序，出现欢迎界面2. 输入所要排序的数据个数（N=100）3. 输入所要排序的数据4. 选择一种排序方法：1.冒泡排序 2.选择排序 3.插入排序4.快速排序 5堆排序 6归并排序7.基数排序5. 选择排列方式：1.从小到大 2.从大到小6. 程序输出结果7. 按Q键并确认退出，其他任意键继续，再次回到欢迎界面8、程序开发总结（简要叙述编写本作业的收获与思考）通过本次编程我了解到C语言的博大精深和自己的不足，在思维的碰撞中提高了自己，同时也学习过到了新的知识，使自己的程序更加逻辑化、条理化。我也发现了利用身边的一切资源和进行自我学习的重要性，为以后的工作和学习积累了宝贵的经验。同时我也意识到老师上课强调的细节对我的帮助，有效的对所学知识进行了巩固和训练。9、运行截图（附上程序运行的截图画面，至少有1幅，截图越翔实得分越高）Windows中抓取当前活动窗口：Alt + Print Screen，抓取全屏：Print Screen。或者使用HyperSnap等软件（百度搜索）。10、源程序（附上程序源代码，若是多个文件，标出文件名）1.sort.cpp#include #include #include myh.hint main() int a100,n,i,k; while(1) printf(nttt 欢迎使用排序算法演示程序nnn); printf( 请输入所要排序的数据个数N(N100)=); scanf(%d,&n); printf(n); printf( 请输入所要排序的数据：); printf(nnt); for(i=0;in;i+) scanf(%d,&ai);/输入数据 printf(n); printf( 请选择一种排序方法：nn); printf(t1.冒泡排序t 2.选择排序t 3.插入排序n); printf(t4.快速排序t 5.堆排序t 6.归并排序t 7.基数排序nn); printf( 您的选择是:); scanf(%d,&k); switch(k) case 1: Bubble(a,n);break; case 2: Selection(a,n);break; case 3: Insertion(a,n);break; case 4: Quick(a,n,0,n-1);break; case 5: Heap(a,n);break; case 6: MergeSort(a,0,n-1);break; case 7: int *a_p = a;Bucket(a_p,n);break; printf(n); printf( 请选择排列方式：1.从小到大 2.从大到小nn); printf( 您的选择是:); scanf(%d,&k); printf(nn); printf( 结果是：nt); if(k=1) for(i=0;i=0;i-) printf(%d ,ai);/倒序输出 printf(nn 按Q键并确认退出，其他任意键继续：); getchar(); if(getchar()=q) break; printf(nnn); return 0;2.sort_fun.cpp#include myh.h#include #include void Bubble(int a,int n)/冒泡排序 int i,j,t; for(j=0;jn-1;j+) for(i=0;iai+1) t=ai; ai=ai+1; ai+1=t;/交换 void Selection(int a,int n)/选择排序 int i,j,k,t; for(i=0;in-1;i+) k=i; for(j=i+1;jn;j+) if(ajak)k=j;/找出最小数 if(i!=k) t=ai; ai=ak; ak=t;/如果不是本身则与相应的ai交换 void Insertion(int a,int n)/插入排序 int i,k,t; for(i=1;in;i+) t=ai; k=i-1; while(tak)/与前边的数依次比较 ak+1=ak;/逐个后移 k-; if(k=-1)break; ak+1=t;/插入原数据 void Quick(int a,int n,int left,int right) /快速排序，left、right分别为数组左右边界 int i,j,t; if(leftright) i=left; j=right+1; while(1) while(i+1n&a+i-1&a-jaleft);/向前搜索小于aleft的数 if(i=j)break; t=ai; ai=aj; aj=t;/交换 t=aleft; aleft=aj; aj=t; Quick(a,n,left,j-1); Quick(a,n,j+1,right);/左右半部分分别再次快速排序 void Shift(int a , int i , int m)/建堆 int k,t; t=ai; k=2*i+1; while(km) if(km-1)&(akak+1) k +; if(tak) ai=ak;/使数列成为一棵完全二叉树的存储结构 i=k; /即成为小根堆 k=2*i+1; /ki=k(2i）且ki=0;i-) Shift(a,i,n);/初始化操作：将an构造为初始堆 for(i=n-1;i=1;i-)/每一趟排序的基本操作：将当前无序区的 k=a0; /堆顶记录a1和该区间的最后一个记录交换， a0=ai; /然后将新的无序区调整为堆(亦称重建堆) ai=k; Shift(a,0,i); void MergeSort(int R,int low,int high)/归并排序 int mid; if(lowhigh) mid=(low+high)/2; MergeSort(R,low,mid); MergeSort(R,mid+1,high); Merge(R,low,mid,high);/重复运行 void Merge(int *R,int low,int m,int high) int i=low,j=m+1,p=0; int *R1; R1=(int *)malloc(high-low+1)*sizeof(int);/申请空间，用以放置合并后的序列 if(!R1) return; while(i=m&j=high) R1p+=(Ri=Rj)?Ri+:Rj+; while(i=m) R1p+=Ri+; while(j=high) R1p+=Rj+; for(p=0,i=low;i=high;p+,i+) Ri=R1p;/两两比较选择相对小的元素放入到合并空间 void Bucket(int *p , int n)/基数排序 int maxNum= findMaxNum( p , n );/获取数组中的最大数 int loopTimes = getLoopTimes(maxNum);/获取最大数的位数，次数也是再分配的次数。 int i; for( i = 1 ; i = loopTimes ; i+) /对每一位进行桶分配 sort2(p , n , i ); int getLoopTimes(int num)/获取数字的位数 int j = 1 ; int temp = num/10; while( temp != 0 ) j+; temp = temp / 10; return j;int findMaxNum( int *p , int n)/查询数组中的最大数 int i ; int m = 0; for( i = 0 ; i m) m = *(p+i); return m;void sort2(int *p , int n , int loop)/将数字分配到各自的桶中，然后按照桶的顺序输出排序结果 int buckets100100 ;/建立一组桶 int tempNum = (int) pow(10 , loop-1); int i , j ; for( i = 0 ; i n ; i+ ) /求桶的index的除数 int row_index = (*(p+i) / tempNum) % 10; for(j = 0 ; j 20 ; j+) if(bucketsrow_indexj =NULL) bucketsrow_index j = *(p+i) ; break; int k = 0 ;/将桶中的数，倒回到原有数组中 for(i = 0 ; i 10 ; i+) for(j = 0 ; j 20 ; j+) if(bucketsij != NULL) *(p + k ) = bucketsij ; bucketsij=NULL; k+; 3.myh.hvoid Bubble(int a,int n);void Selection(int a,int n);void Insertion(int a,int n);void Quick(int a,int n,int left,int right);void Heap(int a , int n);void MergeSort(int R,int low,int high);void Bucket(int *p , int n);void Merge(int *R,int low,int m,int high);int getLoopTimes(int num);int findMaxNum( int *p , int n);void sort2(int *p , int n , int loop);20材料a