5.2 排序与查找.doc

计算机由主要面向科学计算转向主要面向数据处理，60%的数据处理是关于排序与查找的。 计算机图灵奖获得者Knuth里程碑性的三卷书，其中一本就是《排序与查找算法》 一、排序: 1. 选择排序 //【例5.9】用选择法对数组中的n个整数按由小到大进行排序。 #include stdio.h void sele_sort(int arr[] , int n) { int i,j,p,t ; for(i=0;in-1;i++) { p=i; for(j=i+1;jn;j++) if(arr[j]arr[p]) p=j; t=arr[p];arr[p]=arr[i];arr[i]=t; } } void main() { int a[6],i; printf(Enter the array :\n); for(i=0; i6;i++) scanf(%d, a[i]); sele_sort(a,6); printf(The sorted array:\n); for(i=0;i6;i++) printf(%d ,a[i]); printf(\n); } 数组输入的三种方式： 初始化 循环 随机函数 //【例5.1】输入10个0～100的随机整数到定义的数组中。 #include stdlib.h #include stdio.h #include time.h void main() { int i,a[10]={0}; srand((unsigned)time(NULL)); /*初始化随机数序列*/ for(i=0;i10;i++) a[i]=rand()%100; /*产生100以内的随机整数*/ for(i=0;i10;i++) printf(%d\n,a[i]); } 2. 冒泡排序 void bubble_sort(int arr[], int n) { int i,j,t ; for(i=0;in-1;i++) for(j=0;jn-1-i;j++) if(arr[j]arr[j+1]) {t=arr[j];arr[j]=arr[j+1];arr[j+1]=t;} } 二、查找 1. 顺序查找 //【例5.8】编写一个函数可以查找任意数组中是否存在一个特定数据。 #include stdio.h int search(int s[10] , int x) { int i ; for(i=0;i10;i++) if(s[i]==x) break; if(i10) return 1; else return 0; } void main() { int a[10],i, e; printf(Enter the array :\n); for(i=0; i10;i++) scanf(%d, a[i]); printf(Enter the element :\n); scanf(%d,e); if(search(a,e)==1) printf(The element %d exists in the array.,e); else printf(Can not find the element %d.,e); } 2. 二分查找 #include stdio.h void main() { int a[15], l,r,m,x,I; for(i=0;i15;i++) scanf(“%d”,a[i]); l=0;r=14; printf(“Find what?”); scanf(“%d”,x); while(l=r) { m=(l+r)/2; if(a[m]==x) printf(“Having found, its seq no is %d\n”,m);break;} else if (a[m]x) l=m+1; else if(a[m]x) r=m-1; } if(lr) prinft(“Not find such number.”); }