c语言常见基本算法程序段
c语言常见基本算法程序段
1、互换x,y的值
（１）利用中间变量t
t=x;x=y;y=t;
（２）自身相加减
x=x+y;y=x-y;x=x-y;
2、求m,n的最大公约数gys和最小公倍数gbs
（１）相除求余法：余数用r表示
if(m { 互换m,n的值 } gbs=m*n; /*为求最小公倍数*/ r=m%n; while(r!=0) {m=n; n=r; r=m%n; } gys=n; gbs=gbs/gys; （２）相减求差法：差数用c表示 if(m {互换m,n的值 } gbs=m*n; c=m-n; while(c!=0) {m=n; n=c; if(m {互换m,n的值 } c=m-n; } gys=m;/*或gys=n*/ gbs=gbs/gys; （３）穷举法 gbs=m*n; for(i=1;i<=n;i++) if(m%i==0&&n%i==0) gys=i; gbs=gbs/gys; （4）求多个整数的最大公约数和最小公倍数 方法一：穷举法 方法二：利用求余或相减法，先求其中前两个数的最大公约数，再用前两个数的最大公数与第三个数求最大公约数，以此类推，直到与最后一个数求最大公约数即可。 3、判断m是否是素数 （１）用标志变量flag=1假设m是素数 flag=1; for(i=2;i if(m%i= =0) {flag=0; break; } if(flag= =1) m是素数 else m不是素数 （２）用循环控制变量是否等于m for(i=2;i if(i= =m) m是素数 else m不是素数 4、累加累乘 注重发现累加项、累乘项的变化规律。（１）累加（或计数）：累加器初始化为0 如求：1+２+３+.......+１００ s=0; for(i=1;i<=100;i++) s=s+i; 或：s=0; i=1; while(i<=100) {s=s+i; i++; } （２）累乘：累乘器初始化为1 如求n！ p=1; for(i=1;i<=n;i++) p=p*i 或：p=1; i=1; while(i<=n) {p=p*i; i++; } （３）累加累乘同时进行 如求：1!+2!+3!+.......+n! s=0; p=1; for(i=1;i<=n;i++) {p=p*i; s=s+p; } 或：s=0; p=1; i=1; while(i<=n) {p=p*i; s=s+p; i++; } 5、文本作图 a、外循环控制行，内循环控制列。 b、每次输出一个或一组文本。 c、注意文本前或文本与文本之间的空格个数。 d、定义行号，并找出行号与该行文本个数之间的关系。 （１）中心对称图形（行号：-n~~~n） * *** ***** ******* ***** *** * for(i=-n;i<=n;i++) {for(j=1;j<=abs(i)+m;j++) printf(““); for(j=1;j<=2*n+1-2*abs(i);j++) printf(“*”); printf(“\n”); } 或： 1 1 2 1 1 2 3 2 1 1 2 1 1 for(i=-2;i<=2;i++) {for(j=1;j<=3*abs(i);j++) printf(““); for(k=abs(i)-2;k<=2-abs(i);k++) printf(“%3d”,3-abs(i)-abs(k)); printf(“\n”) } （２）三角形 如：* ** *** **** for(i=1;i<=4;i++) {for(j=1;j<=i;j++) printf(“%c”,’*’); printf(“\n”); } 6、穷举与递推 （１）穷举：如果解决的问题可列出不定方程式或不定方程组，用不定方程中的未知数的作为循环控制变量，一个未知数一层循环，循环控制变量的初值、终值为未知数的取值范围。 如：百钱买百鸡。方程组如下： x+y+z=100 5*x+3*y+z/3.0=100 （２）、递推：根据前一项推出后一项或根据后一项推出前一项。递推时注意发现变化规律。 7、排序：(对数组a中的n个元素按升序排序) 从左向右排： （１）顺序比较 从左向右排： for(i=0;i for(j=i+1;j if(a[i]>a[j]) {x=a[i]; a[i]=a[j]; a[j]=x;} 从右向左排： for(i=n-1;i>0;i--) for(j=i-1;j>=0;j--) if(a[i]>a[j]) {x=a[i]; a[i]=a[j]; a[j]=x;} （２）选择排序 从左向右排： for(i=0;i {p=i; for(j=i+1;j if(a[p]>a[j]) p=j; if(p!=i) { x=a[p]; a[p]=a[i]; a[i]=x; } } 从右向左排： for(i=n-1;i>0;i--) {p=i; for(j=i-1;j>=0;j--) if(a[p]>a[j]) p=j; if(p!=i) {x=a[p]; a[p]=a[i]; a[i]=x;} } （３）冒泡排序 从左向右排： for(i=1;i for(j=0;j<=n-1-i;j++) if(a[j]>a[j+1]) {x=a[j]; a[j]=a[j+1]; a[j+1]=x; } 从右向左排： for(i=n-1;i>0;i--) { for(j=n-1;j>=n-i;j--) if(a[j] {x=a[j]; a[j]=a[j-1]; a[j-1]=x;} （４）插入排序 从左向右排： for(i=1;i<=n-1;i++) {x=a[i]; j=i-1; while(j>=0 && x {a[j+1]=a[j]; j=j-1; } a[j+1]=x; } 从右向左排： for(i=n-2;i>=0;i--) {x=a[i]; j=i+1; while(j<=n-1 && x>a[j]) {a[j-1]=a[j]; j=j+1; } a[j-1]=x; } 8、数组在统计中的应用 （１）、统计数组中符合要求的 如：输出数组a中大于平均值的元素，并统计个数。 #include Viod main() {int i,n=0,a[10]={34,56,76,23,12,87,32,45,38,41}; float aver,s=0; for(i=0;i<10;i++) s=s+a[i]; aver=s/10; for(i=0;i<10;i++) if(a[i]>aver) {n++; printf(“%d\t”,a[i]); } Printf(“\n%d”,n); } （２）、将统计的结果保存到数组中 如：统计全校1000名学生体重分别为48~52、53~57、58~62、63~67、68~72、73~77的人数。 #include void main() {int x , a[6]={0} , i ; for(i=1;i<=1000;i++) {scanf(“%d”,&x); a[(x-48)/5]++; } for(i=0;i<6;i++) printf(“%d~~%d:%d”,48+i*5,48+i*5+4 ,a[i]); } 9、极值（在给定的数组a中求最大值或最小值） 在数组中求极值时，可求极值，也可求极值的位置。假设数组中的首元素为最大值或最小值。 （1）、一维数组a[10] max=a[0];i1=0; min=a[0];i2=0; for(i=1;i<10;i++) {if(max if(min>a[i]) {min=a[i];i2=i;} } printf(“max=%d i1=%d\n”,max,i1); printf(“min=%d i2=%d\n”,min,i2); （2）、二维数组a[4][5] max=a[0][0];i1=0;j1=0; min=a[0][0];i2=0;j2=0; for(i=0;i<4;i++) for(j=0;j<5;j++) {if(max if(min>a[i] [j]) {min=a[i] [j];i2=i;j2=j;} } printf(“max=%d \ti1=%d\tj1=%d\n”,max,i1,j1); printf(“min=%d\ti2=%d\tj2=%d\n”,min,i2,j2); 10、查找 （1）顺序查找 直接对数组扫描并比较是否相等即可。 （2）二分法查找 要求数组a[10]已排好序。 方法一、在升序数组中查找 #include void main() {int x,low,hig,mid,a[10]={1,2,3,4,5,6,7,8,9,10}; scanf(“%d”,&x); n=10; low=0; hig=n-1; mid=(low+hig)/2; while (a[mid]<>x && low<=hig) {if (x>a[mid]) low=mid+1; else hig=mid-1; mid=(low+hig)/s; } if(x==a[mid]) printf(“%d:\t%d”,x,mid) else printf(“no found”) } 方法二、在降序数组中查找 #include void main() {int x,low,hig,mid,a[10]={10,9,8,7,6,5,4,3,2,1}; scanf(“%d”,&x); n=10; low=0; hig=n-1; mid=(low+hig)/2; while (a[mid]<>x && low<=hig) {if (x>a[mid]) hig=mid-1; else low=mid+1; mid=(low+hig)/s; } if(x==a[mid]) printf(“%d:\t%d”,x,mid) else printf(“no found”) } 11、移动 要求移动前后相邻两数的位置关系不变。 如：a[10]={1,2,3,4,5,6,7,8,9,10} （1）一维数组左移 左移3位如下：4,5,6,7,8,9,10,1,2,3 for(i=1;i<=3;i++) {x=a[0]; for(j=0;j<9;j++) a[j]=a[j+1]; a[j]=x; } （2）一维数组右移 右移3位如下：8,9,10,1,2,3,4,5,6,7 for(i=1;i<=3;i++) {x=a[9]; for(j=9;j>0;j--) a[j]=a[j-1]; a[j]=x; } （3）二维数组按行向左移1列 #define m 4 #define n 5 ....... int a[m][n],i,j,x; ........... for(i=0;i {x=a[i][0]; for(j=0;j a[i][j]=a[i][j+1]; a[i][j]=x; } （4）二维数组按列向上移1行 #define m 4 #define n 5 ....... int a[m][n],i,j,x; ........... for(j=0;j {x=a[0][j]; for(i=0;i a[i][j]=a[i+1][j]; a[i][j]=x; } （5）移到指定位置 将N×N阶矩阵a的每列最大值移到主对角线上。 for(j=0;j {max=a[0][j]; /*找最大值*/ for(i=1;i if(a[i][j]>max) max=a[i][j]; while(max<>a[j][j]) /*按列向上平移*/ {x=a[0][j]; for(i=0;i a[i][j]=a[i+1][j]; a[N-1][j]=x; } } 12、插入、删除、复制 （1）插入x int a[11]={147,143,140,135,130,125,118,106,101,98} ………. scanf(“%d”,&x); j=9; while(j>=0 && x {a[j+1]=a[j]; j=j-1; } a[j+1]=x; （2）删除 x int a[10]={147,143,140,135,130,125,118,106,101,98} ………. k=0; for(i=0;i<10;i++) if( a[i]!=x) a[k++]=a[i]; （3）复制 ①、一维数组复制到二维数组 int a[9]={……},b[3][3],n=0; …… for(i=0;i<3;i++) for(j=0;j<3;j++) {b[i][j]=a[n]; n++; } ②、二维数组复制到一维数组 int a[9],b[3][3]={……},n=0; …… for(i=0;i<9;i++) a[i]=b[i/3][i%3]; 13、矩阵（二维数组）处理 （1）、相加 #define m 3 #define n 4 ....... int a[m][n],b[m][n],c[m][n]; .......... for(i=0;i for(j=0;j c[m][n]=a[m][n]+ [m][n]; （2）、相乘 #define m 3 #define n 4 #define l 5 ....... int a[m][n],b[n][l],c[m][l]; .......... for(i=0;i {for(j=0;j c[i][j]=0; for(k=0;k c[i][j]= c[i][j]+a[i][k]*b[k][j]; （3）、转置（行列互换） #define m 3 #define n 4 ........ int a[m][n],b[n][m]; .......... for(i=0;i for(j=0;j b[j][i]=a[i][j]; （4）、逆时针旋转90度 #define m 3 #define n 4 ........ int a[m][n],b[n][m]; .......... for(i=0;i for(j=0;j b[j][i]=a[i][n-1-j]; （5）、顺时针旋转90度 #define m 3 #define n 4 ........... int a[m][n],b[n][m]; .......... for(i=0;i for(j=0;j b[j][i]=a[m-1-i][j]; （6）、逆时针或顺时针旋转180度 #include void main() {int i,j,m,n; int a[3][4]={1,2,3,4,5,6,7,8,9,10,11,12},b[3][4]; m=3;n=4; clrscr(); for(i=0;i {for(j=0;j printf("%d\t",a[i][j]); printf("\n"); } for(i=0;i for(j=0;j b[i][j]=a[m-1-i][n-1-j]; for(i=0;i {for(j=0;j printf("%d\t",b[i][j]); printf("\n"); } } 14、数制转换(整数) 系统默认数值型数据以十进制形式输出，非十进制数的输出可作字符输出，也可将二进制以十进制形式输出。如：（10100011）2 10100011B （1）、十进制x转二进制y int x,r,n=0; long y=0; while(x!=0) x=x/2;n++ } 或： int x,r,n=0,I; char y[]={““}; while(x!=0) {r=x%2; y[n++]=r+48; x=x/2; } for(i=n-1;i>=0;i--) putchar(y[i]); （2）、二进制y转十进制x int x=0,r,n=0,i; char y[]={“10111001“}; n=strlen(y); for(i=0;i {r=y[i]-48; x=x+r*pow(2,n-i-1); } （3）、二进制y转八进制x #include #include void main() { char x[]={" "}; int r,n=0,m=0,t=0,i; char y[]={"10111001"}; clrscr(); n=strlen(y); for(i=n-1;i>=0;i--) { r=y[i]-'0'; t=t+r*pow(2,m); m++; if(m==3||i==0) {m=0; r=0; x[((i+1)/3)]=t+'0'; t=0;} } puts(x); } （4）、八进制x转二进制y #include #include void main() { char x[]={"645"},y[]={" "},t[3]; int z,r,n=0,m=0,i,j; for(i=0;i {z=x[i]-'0'; j=0; while(z!=0) {r=z%2; t[j++]=r+48; z=z/2; } while(j>0) {j--; y[m]=t[j]; m++; } } for(i=0;i putchar(y[i]); } 15、函数递归调用 是将任务转换成新任务，新任务与原任务处理方法相同，但范围比原任务范围小，直至最后一个任务，最后任务的结果为特定已知，即边界条件。如求n！。 1 当n=1时 n!= n*(n-1)! 当n>1时 long fact(int n) {long p; if(n= =1) p=1; else p=n*fact(n-1); return p; } 16、文件处理 （1）、文件打开 FILE *fp; /*fp为文件指针。*/ ……….. if((fp=fopen(“文件名”,”读写方式”))= =NULL) {printf(“\n error on open 文件名”); exit(1);} （2）、文件关闭 fclose(fp); （3）、文件读写方式 读： r 写： w 既读又写： + 文本：t 二进制： b （4）、文件位置指针 是指向文件内部数据的指针。rewind(fp) （5）、文件有关函数 fopen( ) fclose( ) fseek( ) rewind( ) ftell( ) fgetc( ) getc( ) fputc( ) putc( ) fgets( ) fputs( ) getw( ) putw( ) fread( ) fwrite( ) fscanf( ) fprintf( ) feof( ) ferror( ) clearr( ) 17、预处理命令及头文件 （1）、预处理命令 包含：#include 宏定义：#define 条件编译：#ifdef 标识符 程序段1 #else 程序段2 #endif 或： #if 表达式 程序段1 #else 程序段2 #endif （2）、头文件 数学：math.h 字符串：string.h 字符：ctype.h 输入输出：stdio.h 《数据结构与算法》期末复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i C语言几种常见的排序方法 2009-04-2219:55 插入排序是这样实现的： 首先新建一个空列表，用于保存已排序的有序数列（我们称之为"有序列表"）。 从原数列中取出一个数，将其插入"有序列表"中，使其仍旧保持有序状态。 重复2号步骤，直至原数列为空。 插入排序的平均时间复杂度为平方级的，效率不高，但是容易实现。它借助了"逐步扩大成果"的思想，使有序列表的长度逐渐增加，直至其长度等于原列表的长度。 冒泡排序 冒泡排序是这样实现的： 首先将所有待排序的数字放入工作列表中。 从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。 重复2号步骤，直至再也不能交换。 冒泡排序的平均时间复杂度与插入排序相同，也是平方级的，但也是非常容易实现的算法。 选择排序 选择排序是这样实现的： 设数组内存放了n个待排数字，数组下标从1开始，到n结束。 i=1 从数组的第i个元素开始到第n个元素，寻找最小的元素。 将上一步找到的最小元素和第i位元素交换。 如果i=n－1算法结束，否则回到第3步 选择排序的平均时间复杂度也是O(n²)的。 快速排序 现在开始，我们要接触高效排序算法了。实践证明，快速排序是所有排序算法中最高效的一种。它采用了分治的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。这是一种先进的思想，也是它高效的原因。因为在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了，大大减少了数字间不必要的比较。但查找数据得另当别论了。 堆排序 堆排序与前面的算法都不同，它是这样的： 首先新建一个空列表，作用与插入排序中的"有序列表"相同。 找到数列中最大的数字，将其加在"有序列表"的末尾，并将其从原数列中删除。 重复2号步骤，直至原数列为空。 堆排序的平均时间复杂度为nlogn,效率高（因为有堆这种数据结构以及它奇妙的特征，使得"找到数列中最大的数字"这样的操作只需要O(1)的时间复杂度，维护需要logn的时间复杂度），但是实现相对复杂（可以说是这里7种算法中比较难实现的）。 一、基本算法 1．交换（两量交换借助第三者） 例1、任意读入两个整数，将二者的值交换后输出。 main() {int a,b,t; scanf("%d%d",&a,&b); printf("%d,%d\n",a,b); t=a; a=b; b=t; printf("%d,%d\n",a,b);} 【解析】程序中加粗部分为算法的核心，如同交换两个杯子里的饮料，必须借助第三个空杯子。 假设输入的值分别为3、7，则第一行输出为3，7；第二行输出为7，3。 其中t为中间变量，起到“空杯子”的作用。 注意：三句赋值语句赋值号左右的各量之间的关系！ 【应用】 例2、任意读入三个整数，然后按从小到大的顺序输出。 main() {int a,b,c,t; scanf("%d%d%d",&a,&b,&c); /*以下两个if语句使得a中存放的数最小*/ if(a>b){ t=a; a=b; b=t; } if(a>c){ t=a; a=c; c=t; } /*以下if语句使得b中存放的数次小*/ if(b>c) { t=b; b=c; c=t; } printf("%d,%d,%d\n",a,b,c);} 2．累加 累加算法的要领是形如“s=s+A”的累加式，此式必须出现在循环中才能被反复执行，从而实现累加功能。“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为0。例1、求1+2+3+……+100的和。 main() {int i,s; s=0; i=1; while(i<=100) {s=s+i; /*累加式*/ i=i+1; /*特殊的累加式*/ } printf("1+2+3+...+100=%d\n",s);} 【解析】程序中加粗部分为累加式的典型形式，赋值号左右都出现的变量称为累加器，其中“i = i + 1”为特殊的累加式，每次累加的值为1，这样的累加器又称为计数器。 C语言9种常用排序法 1.冒泡排序 2.选择排序 3.插入排序 4.快速排序 5.希尔排序 6.归并排序 7.堆排序 8.带哨兵的直接插入排序 9.基数排序 例子：乱序输入n个数，输出从小到大排序后的结果1.冒泡排序 #include for(i=0;i int i, j, n, a[100], t, temp; while(scanf("%d",&n)!=EOF) { for(i=0;i 2008-02-18 18:48 【程序1】 题目：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？ 1.程序分析：可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去 掉不满足条件的排列。 2.程序源代码： main() { int i,j,k; printf("\n"); for(i=1;i<5;i++) ／*以下为三重循环*/ for(j=1;j<5;j++) for (k=1;k<5;k++) { if (i!=k&&i!=j&&j!=k) /*确保i、j、k三位互不相同*/ printf("%d,%d,%d\n",i,j,k); } } ============================================================== 【程序2】 题目：企业发放的奖金根据利润提成。利润(I)低于或等于10万元时，奖金可提10%；利润高 于10万元，低于20万元时，低于10万元的部分按10%提成，高于10万元的部分，可可提 成7.5%；20万到40万之间时，高于20万元的部分，可提成5%；40万到60万之间时高于 40万元的部分，可提成3%；60万到100万之间时，高于60万元的部分，可提成1.5%，高于 100万元时，超过100万元的部分按1%提成，从键盘输入当月利润I，求应发放奖金总数？ 1.程序分析：请利用数轴来分界，定位。注意定义时需把奖金定义成长整型。 2.程序源代码： main() { long int i; int bonus1,bonus2,bonus4,bonus6,bonus10,bonus; scanf("%ld",&i); bonus1=100000*0.1;bonus2=bonus1+100000*0.75; bonus4=bonus2+200000*0.5; bonus6=bonus4+200000*0.3; bonus10=bonus6+400000*0.15; if(i<=100000) 一、设计思想 插入排序：首先，我们定义我们需要排序的数组，得到数组的长度。如果数组只有一个数字，那么我们直接认为它已经是排好序的，就不需要再进行调整，直接就得到了我们的结果。否则，我们从数组中的第二个元素开始遍历。然后，启动主索引，我们用curr当做我们遍历的主索引，每次主索引的开始，我们都使得要插入的位置（insertIndex）等于-1，即我们认为主索引之前的元素没有比主索引指向的元素值大的元素，那么自然主索引位置的元素不需要挪动位置。然后，开始副索引，副索引遍历所有主索引之前的排好的元素，当发现主索引之前的某个元素比主索引指向的元素的值大时，我们就将要插入的位置（insertIndex）记为第一个比主索引指向元素的位置，跳出副索引；否则，等待副索引自然完成。副索引遍历结束后，我们判断当前要插入的位置（insertIndex）是否等于-1，如果等于-1，说明主索引之前元素的值没有一个比主索引指向的元素的值大，那么主索引位置的元素不要挪动位置，回到主索引，主索引向后走一位，进行下一次主索引的遍历；否则，说明主索引之前insertIndex位置元素的值比主索引指向的元素的值大，那么，我们记录当前主索引指向的元素的值，然后将主索引之前从insertIndex位置开始的所有元素依次向后挪一位，这里注意，要从后向前一位一位挪，否则，会使得数组成为一串相同的数字。最后，将记录下的当前索引指向的元素的值放在要插入的位置（insertIndex）处，进行下一次主索引的遍历。继续上面的工作，最终我们就可以得到我们的排序结果。插入排序的特点在于，我们每次遍历，主索引之前的元素都是已经排好序的，我们找到比主索引指向元素的值大的第一个元素的位置，然后将主索引指向位置的元素插入到该位置，将该位置之后一直到主索引位置的元素依次向后挪动。这样的方法，使得挪动的次数相对较多，如果对于排序数据量较大，挪动成本较高的情况时，这种排序算法显然成本较高，时间复杂度相对较差，是初等通用排序算法中的一种。 选择排序：选择排序相对插入排序，是插入排序的一个优化，优化的前提是我们认为数据是比较大的，挪动数据的代价比数据比较的代价大很多，所以我们选择排序是追求少挪动，以比较次数换取挪动次数。首先，我们定义我们需要排序的数组，得到数组的长度，定义一个结果数组，用来存放排好序的数组，定义一个最小值，定义一个最小值的位置。然后，进入我们的遍历，每次进入遍历的时候我们都使得当前的最小值为9999，即认为每次最小值都是最大的数，用来进行和其他元素比较得到最小值，每次认为最小值的位置都是0，用来重新记录最小值的位置。然后，进入第二层循环，进行数值的比较，如果数组中的某个元素的值比最小值小，那么将当前的最小值设为元素的值，然后记录下来元素的位置，这样，当跳出循环体的时候，我们会得到要排序数组中的最小值，然后将最小值位置的数值设置为9999，即我们得到了最小值之后，就让数组中的这个数成为最大值，然后将结果数组result[]第主索引值位置上的元素赋值为最小值，进行下一次外层循环重复上面的工作。最终我们就得到了排好序的结果数组result[]。选择排序的优势在于，我们挪动元素的次数很少，只是每次对要排序的数组进行整体遍历，找到其中的最小的元素，然后将改元素的值放到一个新的结果数组中去，这样大大减少了挪动的次序，即我们要排序的数组有多少元素，我们就挪动多少次，而因为每次都要对数组的所有元素进行遍历，那么比较的次数就比较多，达到了n2次，所以，我们使用选择排序的前提是，认为挪动元素要比比较元素的成本高出很多的时候。他相对与插入排序，他的比较次数大于插入排序的次数，而挪动次数就很少，元素有多少个，挪动次数就是多少个。 希尔排序：首先，我们定义一个要排序的数组，然后定义一个步长的数组，该步长数组是由一组特定的数字组成的，步长数组具体得到过程我们不去考虑，是由科学家经过很长时间计算得到的，已经根据时间复杂度的要求，得到了最适合希尔排序的一组步长值以及计算 1.定积分近似计算： /*梯形法*/ double integral(double a,double b,long n) { long i;double s,h,x; h=(b-a)/n; s=h*(f(a)+f(b))/2; x=a; for(i=1;i } 3.素数的判断： /*方法一*/ for (t=1,i=2;i //插入排序法 void InsertSort() { int s[100]; int n,m,j,i=0,temp1,temp2; printf("请输入待排序的元素个数："); scanf("%d",&n); printf("请输入原序列："); for (i=0; i //堆排序 static a[8] = {0,25,4,36,1,60,10,58,}; int count=1; void adjust(int i,int n) { int j,k,r,done=0; k = r = a[i]; j = 2*i; while((j<=n)&&(done==0)) { if(j C语言常用算法集合 1.定积分近似计算： /*梯形法*/ double integral(double a,double b,long n) { long i;double s,h,x; h=(b-a)/n; s=h*(f(a)+f(b))/2; x=a; for(i=1;i if(n==1||n==2) *s=1; else{ fib(n-1,&f1); fib(n-2,&f2); *s=f1+f2; } } 3.素数的判断： /*方法一*/ for (t=1,i=2;i 基于C语言地多种排序方法地实现 1 引言 1.1 课题背景 排序问题源远流长，一直是数学地重要组成部分.随着各种信息地快速更新，排序问题也走进了其他领域以及我们地日常生活.如何高效地排序一直困扰着我们. 1.2 课程设计目地 排序是数学地重要组成部分，工作量大是其存在地问题.如何高效地排序？本程序就是解决这个问题而设计.程序中，把数列储存在数组中，采用插入排序等十种排序方法对数组元素进行排序，高效地解决了排序问题.本软件开发地平台为最新地微软公司出版地市面最新系统Windows 2000，而且可以作为自身地运行平台非常广泛，包括 Windows 98/2000/XP/Vista等等. 1.3课程设计内容 本程序把对数列地排序转化为对数组元素地排序，用户可以根据自己地实际问题选择系统提供地七种排序方法地任意一种进行排序.程序通过自身地判断以及处理实现排序.程序最后输出每趟排序及初始排序结果. 2 系统分析与设计方案 2.1 系统分析 设计一个排序信息管理系统，使之能够操作实现以下功能： 1) 显示需要输入地排序长度及其各个关键字 2) 初始化输入地排序序列 3) 显示可供选择地操作菜单 4) 显示输出操作后地移动次数和比较次数 5) 显示操作后地新序列 5) 可实现循环继续操 2.2 设计思路 通过定义C语言顺序表来存储排序元素信息，构造相关函数，对输入地元素进行相应地处理. [2] 2.3 设计方案 设计方案如图2.1所示 图2.1 设计方案 具体流程见图2.2 图 2.2 程序流程图 3功能设计 3.1 SqList顺序表 其中包括顺序表长度，以及顺序表.源代码如下：[1] typedef struct { KeyType key。 //关键字项 InfoType otherinfo。 //其他数据项 }RedType。 typedef struct { RedType r[MaxSize+1]。 //r[0]作为监视哨 int length。 //顺序表长度 }SqList。 3.2 直接插入排序 直接插入排序是将一个记录插入到已排好序地有序表中，从而得到一个新地、记录数增1地有序表 图3.1 直接插入排序示意图 将第i个记录地关键字r[i].key顺序地与前面记录地关键字r[i-1].key,r[i-2].key,……，r[1].key进行比较，把所有关键字大于r[i].key地记录依次后移一位，直到关键字小于或者等于r[i].key地记录 /* ===================================================================== ======== 相关知识介绍（所有定义只为帮助读者理解相关概念，并非严格定义）： 1、稳定排序和非稳定排序 简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就 说这种排序方法是稳定的。反之，就是非稳定的。 比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为 a1,a2,a4,a3,a5， 则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4, a2,a3,a5就不是稳定的了。 2、内排序和外排序 在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序； 在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。 3、算法的时间复杂度和空间复杂度 所谓算法的时间复杂度，是指执行算法所需要的计算工作量。 一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。 ===================================================================== =========== */ /* ================================================ 功能：选择排序 输入：数组名称（也就是数组首地址）、数组中元素个数 ================================================ */ /* ==================================================== 算法思想简单描述： #include printf("\n请输入该序列元素的个数\n"); scanf("%d", &pvector->n); pvector->record = (RecordNode*)malloc((sizeof(RecordNode))*(pvector->n)); printf("\n你要以什么方式创建序列？\n方式1：自动创建请输入1，方式2：手动创建请输入0\n"); scanf("%d", &k); if (k) { srand((int)time(0)); for (i = 0; i < pvector->n; i++) { if(pvector->n<100) pvector->record[i].key = randx(100); else if((pvector->n<1000)) pvector->record[i].key = randx(1000); else pvector->record[i].key = randx(pvector->n); } } else { printf("\n请输入%d个大小不一样的整数\n", pvector->n); 60.题目:古典问题:有一对兔子,从出生后第3个月 起每个月都生一对兔子,小兔 子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总 数 为多少? _________________________________________________________________ _ 程序分析:兔子的规律为数列1,1,2,3,5,8,13,21.... _________________________________________________________________ __ 程序源代码: main() { long f1,f2; int i; f1=f2=1; for(i=1;i<=20;i++) { printf("%12ld %12ld",f1,f2); if(i%2==0) printf("\n");/*控制输出,每行四个*/ f1=f1+f2;/*前两个月加起来赋值给第三个月*/ f2=f1+f2;/*前两个月加起来赋值给第三个月*/ } } 上题还可用一维数组处理,you try! 61.题目:判断101-200之间有多少个素数,并输出所有素数。 _________________________________________________________________ _ 1 程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被 整 除,则表明此数不是素数,反之是素数。 _________________________________________________________________ __ 程序源代码: #include "math.h" main() { int m,i,k,h=0,leap=1; 1、稳定排序和非稳定排序 简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就说这种排序方法是稳定的。反之，就是非稳定的。 比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为a1,a2,a4,a3,a5，则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4,a2,a3,a5就不是稳定的了。 2、内排序和外排序在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序； 在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。 3、算法的时间复杂度和空间复杂度 所谓算法的时间复杂度，是指执行算法所需要的计算工作量。 一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。 ================================================ 功能：选择排序 输入：数组名称（也就是数组首地址）、数组中元素个数 ==================================================== 算法思想简单描述： 在要排序的一组数中，选出最小的一个数与第一个位置的数交换； 然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环 到倒数第二个数和最后一个数比较为止。 选择排序是不稳定的。算法复杂度O(n2)--[n的平方] ===================================================== void select_sort(int*x,int n) { int i,j,min,t; for(i=0;i 基于C语言的多种排序方法的实现 《基于C 语言的多种排序方法的实现》第 1 页共30页基于C语言的多种排序方法的实现 1 引言 1.1 课题背景 排序问题源远流长，一直是数学地重要组成部分。随着各种信息的快速更新，排序问题也走进了其他领域以及我们地日常生活。如何高效地排序一直困扰着我们。 1.2 课程设计目的 排序是数学的重要组成部分，工作量大是其存在的问题。如何高效地排序？本程序就是解决这个问题而设计。程序中，把数列储存在数组中，采用插入排序等十种排序方法对数组元素进行排序，高效地解决了排序问题。本软件开发的平台为最新的微软公司出版的市面最新系统Windows 2000，而且可以作为自身的运行平台非常广泛，包括Windows 98/2000/XP/Vista等等。 1.3课程设计内容 本程序把对数列的排序转化为对数组元素的排序，用户可以根据自己的实际问题选择系统提供的七种排序方法的任意一种进行排序。程序通过自身的判断以及处理实现排序。程序最后输出每趟排序及初始排序结果。 2 系统分析与设计方案 2.1 系统分析 设计一个排序信息管理系统，使之能够操作实现以下功能： 1) 显示需要输入的排序长度及其各个关键字 2) 初始化输入的排序序列 3) 显示可供选择的操作菜单 4) 显示输出操作后的移动次数和比较次数 5) 显示操作后的新序列 5) 可实现循环继续操 2.2 设计思路 通过定义C语言顺序表来存储排序元素信息，构造相关函数，对输入的元素进行相应的处理。[2] 2.3设计方案 设计方案如图2.1所示 图2.1 设计方案 具体流程见图2.2 C语言常用算法归纳 应当掌握的一般算法 一、基本算法： 交换、累加、累乘 二、非数值计算常用经典算法： 穷举、排序（冒泡，选择）、查找（顺序即线性） 三、数值计算常用经典算法： 级数计算（直接、简接即递推）、一元非线性方程求根（牛顿迭代法、二分法）、定积分计算（矩形法、梯形法） 四、其他： 迭代、进制转换、矩阵转置、字符处理（统计、数字串、字母大小写转换、加密等）、整数各数位上数字的获取、辗转相除法求最大公约数（最小公倍数）、求最值、判断素数（各种变形）、数组元素的插入（删除）、二维数组的其他典型问题（方阵的特点、杨辉三角形） 详细讲解 一、基本算法 1．交换（两量交换借助第三者） 例1、任意读入两个整数，将二者的值交换后输出。 main() { int a,b,t; scanf("%d%d",&a,&b); printf("%d,%d\n",a,b); t=a; a=b; b=t; printf("%d,%d\n",a,b); } 【解析】程序中加粗部分为算法的核心，如同交换两个杯子里的饮料，必须借助第三个空杯子。 假设输入的值分别为3、7，则第一行输出为3，7；第二行输出为7，3。 其中t为中间变量，起到“空杯子”的作用。 注意：三句赋值语句赋值号左右的各量之间的关系！ 【应用】 例2、任意读入三个整数，然后按从小到大的顺序输出。 main() { int a,b,c,t; scanf("%d%d%d",&a,&b,&c); /*以下两个if语句使得a中存放的数最小*/ if(a>b){ t=a; a=b; b=t; } if(a>c){ t=a; a=c; c=t; } /*以下if语句使得b中存放的数次小*/ if(b>c) { t=b; b=c; c=t; } printf("%d,%d,%d\n",a,b,c); } 2．累加 累加算法的要领是形如“s=s+A”的累加式，此式必须出现在循环中才能被反复执行，从而实现累加功能。“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为0。 例1、求1+2+3+……+100的和。 main() { int i,s; s=0; i=1; while(i<=100) { s=s+i; /*累加式*/ i=i+1; /*特殊的累加式*/ } printf("1+2+3+...+100=%d\n",s); } 【解析】程序中加粗部分为累加式的典型形式，赋值号左右都出现的变量称为累加器，其中“i = i + 1”为特殊的累加式，每次累加的值为1，这样的累加器又称为计数器。 3．累乘 十大经典排序算法（动图演示，收藏好文） 0、算法概述 0.1 算法分类 十种常见排序算法可以分为两大类： 非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。 线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。 0.2 算法复杂度 0.3 相关概念 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n 的函数。 1、冒泡排序（Bubble Sort） 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 1.1 算法描述 ?比较相邻的元素。如果第一个比第二个大，就交换它们两个； ?对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数； ?针对所有的元素重复以上的步骤，除了最后一个； ?重复步骤1~3，直到排序完成。 1.2 动图演示 1.3 代码实现 function bubbleSort(arr) { var len = arr.length; for (var i = 0; i < len - 1; i++) { for (var j = 0; j < len - 1 - i; j++) { if (arr[j] > arr[j+1]) { // 相邻元素两两对比var temp = arr[j+1]; // 元素交换 arr[j+1] = arr[j]; arr[j] = temp; } } } return arr; } C程序设计的常用算法 算法（Algorithm）：计算机解题的基本思想方法和步骤。算法的描述：是对要解决一个问题或要完成一项任务所采取的方法和步骤的描述，包括需要什么数据（输入什么数据、输出什么结果）、采用什么结构、使用什么语句以及如何安排这些语句等。通常使用自然语言、结构化流程图、伪代码等来描述算法。 一、简单数值类算法 此类问题都要使用循环，要注意根据问题确定循环变量的初值、终值或结束条件，更要注意用来表示计数、和、阶乘的变量的初值。 1、求阶乘：n!=1*2*384…..*n; n!= n*(n-1)!= 下列程序用于求n的阶乘.在累乘之前,一定要将用于存放乘积的变量的值初始化为1. long func(int n) { int i; long t=1; for(i=2;i<=n;i++) t*=i; return t; } printf("\n"); } main() { int n; scanf("%d", &n); printf("n!=%ld\n", fac(n)); } 2、整数拆分问题：把一个整数各个位上的数字存到数组中 #define N 4 /* N代表整数位数*/ viod split(int n, int a[ ]） /* 1478: a[ 3]=8, a[2 ]=7, a[1 ]=4…*/ {int i; for(i=N-1;i!=0; i--) { a[i]=n%10; n=n/10; } } main() {int i,m=1478,b[N-1]; split(m, b）; for(i=0;i<4; i++) printf(“%5d”, b[i]); 八、常用算法 （一）考核知识要点 1．交换、累加、累乘、求最大（小）值 2．穷举 3．排序（冒泡、插入、选择） 4．查找（顺序、折半） 5．级数计算（递推法） 6．一元方程求解（牛顿迭代法、二分法） 7．矩阵（转置） 8．定积分计算（矩形法、梯形法） 9．辗转相除法求最大公约数、判断素数 10．数制转换 （二）重点、难点精解 教材中给出的算法就不再赘述了。 1．基本操作：交换、累加、累乘 1）交换 交换算法的要领是“借助第三者”（如同交换两个杯子里的饮料，必须借助第三个空杯子）。例如，交换两个整型变量里的数值：int a=7,b=9,t; t=a; a=b; b=t; (不借助第三者，也能交换两个整型变量里的数值，但不通用，只是一个题目而已。 例如：int a=7,b=9; a=a+b; b=a-b; a=a-b;) 2）累加 累加算法的要领是形如“s=s+A”的累加式，此式必须出现在循环中才能被反复执行，从而实现累加功能。“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为0。 3）累乘 累乘算法的要领是形如“s=s*A”的累乘式，此式必须出现在循环中才能被反复执行，从而实现累乘功能。“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为1。 2．非数值计算常用经典算法 1）穷举法 也称为“枚举法”，即将可能出现的各种情况一一测试，判断是否满足条件，一般采用循环来实现。 例如，用穷举法输出“将1元人民币兑换成1分、2分、5分硬币”的所有方法。 main() {int y,e,w; for(y=0;y<=100;y++) for(e=0;e<=50;e++) for(w=0;w<=20;w++) 天行健，君子以自强不息 常见经典排序算法 1.希尔排序 2.二分插入法 3.直接插入法 4.带哨兵的直接排序法 5.冒泡排序 6.选择排序 7.快速排序 8.堆排序 一.希尔（Shell）排序法（又称宿小增量排序，是1959年由D.L.Shell提出来的） /* Shell 排序法 */ #include /* 二分插入法 */ void HalfInsertSort(int a[], int len) { int i, j,temp; int low, high, mid; for (i=1; i数据结构与算法C语言版期末复习题
C语言几种常见的排序方法
非常全的C语言常用算法
C语言9种常用排序法
C语言经典算法100例(1---30)
几种排序算法的分析与比较--C语言
C语言常用算法集合
数据结构经典算法 C语言版
最新C语言常用算法集合汇总
基于C语言的多种排序方法的实现
C语言常用排序算法
快速排序法(C语言)
c语言经典算法100例
C语言常用排序算法
基于C语言的多种排序方法的实现
最新C语言常用算法归纳
十大经典排序算法-C语言
C语言常用算法程序汇总
(整理)C语言常用算法.
c语言经典排序算法(8种-含源代码)