言常用算法.ppt

* 共 100 页 第 * 页 3、插入法排序 即：有序序列的插入算法。就是将某数据插入到一个有序序列后，该序列仍然有序。 基本思想：n个有序数（从小到大）存放在数组a(1)~a(n)中，要插入的数x。首先确定x插在数组中的位置P，通过数组的移动腾挪，将x插入相应的位置。 插入法排序的要领就是每读入一个数立即插入到最终存放的数组中，每次插入都使得该数组有序。 共 100 页 第 * 页 例g-18、将任意读入的整数x插入一升序数列后，数列仍按升序排列。 #define N 10 main() { int a[N]={-1,3,6,9,13,22,27,32,49}, x, j, k; scanf(%d,x); if(xa[N-2]) a[N-1]=x ; else { j=0; while( j=N-2 xa[j]) j++; for(k=N-2; k=j; k--) a[k+1]=a[k]; a[j]=x; } for(j=0; j=N-1; j++) printf(%d ,a[j]); } 共 100 页 第 * 页 例g-19、任意读入10个整数，将其用插入法按降序排列后输出。 #define N 10 main() { int a[N],i,j,k,x; scanf(%d,a[0]); for(j=1; jN; j++) { scanf(%d,x); if (xa[j-1]) a[j]=x; else { i=0; while (xa[i]i=j-1) i++; for(k=j-1; k=i; k--) a[k+1] = a[k]; a[i] = x; } } for(i=0; iN; i++) printf(%d\n,a[i]); } 共 100 页 第 * 页 4、归并排序 即将两个有序（都升序或降序）数组A、B排列的数据序列合并成一个仍按原序排列的序列C。 【基本思想】 1）先在A、B数组中各取第一个元素进行比较，将小的元素放入C数组； 2）取小的元素所在数组的下一个元素与另一数组中上次比较后较大的元素比较，重复上述比较过程，直到某个数组被先排完； 3）将另一个数组剩余元素抄入C数组，合并排序完成。 共 100 页 第 * 页 【例g-20】有一个含有6个数据的升序序列和一个含有4个数据的升序序列，将二者合并成一个含有10个数据的升序序列。 #define M 6 #define N 4 main() { int a[M]={-3,6,19,26,68,100}, b[N]={8,10,12,22}; int i, j, k, c[M+N]; i=j=k=0; while(im jn) { if(a[i]b[j]) { c[k] = a[i]; i++; } else { c[k]=b[j]; j++; } k++; } while (i=m jn) { c[k]=b[j]; k++; j++; } while (j=n im) { c[k]=a[i]; k++; i++; } for (i=0; im+n; i++) printf(%d ,c[i]); } * * * * * * * * * * * * * * * * * * * * * * * * * * * C语言常用算法 共 100 页 第 * 页 一、数值计算 1、累加 2、累乘（阶乘） 3、交换 4、最大/最小值 5、数位拆解 6、数组移动 7、级数计算 8、素数判断 二、数据查找 1、顺序查找 2、穷举查找 三、排序算法 1、冒泡排序 2、选择排序 3、插入排序 4、归并排序 共 100 页 第 * 页 1、累加 累加算法的要领是形如“s=s+A”的累加式，此式必须出现在循环中才能被反复执行，从而实现累加功能。 “A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为0。 一、数值计算 共 100 页 第 * 页 例g-1、求1+2+3+……+100的和。 main() { int i,s; s=0; i=1; while (i=100) { s = s+i; i = i+1; } printf(“s=%d\n,s); } 【解析】程序中红字部分为累加式的典型形式，赋值号左右都出现的变量称为累加器，其中“i = i + 1”