C第六章数组查找排序算法

1C程序设计数组——常用算法2常用算法冒泡排序算法选择排序算法插入排序算法顺序查找技术二分查找技术31.冒泡排序算法基本原理：每轮让最小的元素冒泡到左边。或每轮让最大的元素冒泡到右边。4102030404550607080901050602030407080459010205060304045708090…………………………506020104070803090455voidmain()/*每轮让最小的元素冒泡到左边*/{ints[10],i,j,t;for(i=0;i10;scanf(“%d”,&s[i++]));for(i=0;i10;i++)/*i为一轮冒泡比较的终点*/for(j=9;ji;j--)if(s[j]s[j-1]){t=s[j];s[j]=s[j-1];s[j-1]=t;}for(i=0;i10;printf(“%d”,s[i++]));printf(“\n”);}650602010407080309045102030404550607080905020104060703080459020104050603070458090…………………………voidmain()/*每轮让最大的元素冒泡到右边*/{ints[10],i,j,t;for(i=0;i10;scanf(“%d”,&s[i++]));for(i=9;i0;i--)/*i为一轮冒泡比较的终点*/for(j=0;ji;j++)if(s[j]s[j+1]){t=s[j];s[j]=s[j+1];s[j+1]=t;}for(i=0;i10;printf(“%d”,s[i++]));printf(“\n”);}for(j=0;j9;j++)for(i=0;i9-j;i++)if(a[i]a[i+1])a[i]-a[i+1];82.选择排序算法将被排序的数据存放到数组中，先找到第1小的数据，将它与第1个元素交换位置；再找到第2小的数据，将它与第2个元素交换位置；依此类推，直到第n-1小的数据交换到第n-1号位置为止。每次都在后面的数据中选择一个较小的数据交换到其正确的位置，故称为选择排序法。950602010407080309045106020504070803090451020605040708030904510203040455060708090…………………………#includestdio.h#includestdlib.h#includetime.hvoidmain(){inti,j,n,t,p,d[101];printf(numberofdatas:);scanf(%d,&n);srand((unsigned)time(NULL));for(i=1;in+1;i++)d[i]=rand()%100;printf(\nbeforesort:\n);for(i=1;in+1;i++)printf(%d,d[i]);for(i=1;in;i++){p=i;for(j=i+1;jn+1;j++)if(d[j]d[p])p=j;if(p!=i){t=d[i];d[i]=d[p];d[p]=t;}}printf(\n\naftersort:\n);for(i=1;in+1;i++)printf(%d,d[i]);}113.插入排序算法假设待排序的数据存放在数组中。从第2个元素开始，将每个元素与位于它前面的元素（其前面的元素是有序的）进行比较，将它插入到合适的位置，使插入后它们仍然有序。显然，经过n-1次插入操作后，n个元素将成为有序的。1237122067311237206731122037673112203767311220313767#includestdio.h#includestdlib.h#includetime.hvoidmain(){inti,j,n,t,p,d[101];printf(numberofdatas:);scanf(%d,&n);srand((unsigned)time(NULL));for(i=1;in+1;i++)d[i]=rand()%100;printf(\nbeforesort:\n);for(i=1;in+1;i++)printf(%d,d[i]);for(i=2;in+1;i++){t=d[i];for(p=1;pi;p++)if(d[p]t)break;if(p==i)continue;for(j=i;jp;j--)d[j]=d[j-1];d[p]=t;}printf(\n\naftersort:\n);for(i=1;in+1;i++)printf(%d,d[i]);}144.顺序查找技术从数组的第1个元素开始，顺序扫描数组中的每一个元素，将它与要查找的值k相比较，若相等，则查找成功；若扫描结束后，仍为找到等于k的元素，则查找失败。#includestdio.h#includetime.h#includestdlib.hvoidmain(){inti,n,x,data[100];printf(nubmberofdatas:);scanf(%d,&n);srand((unsigned)time(NULL));for(i=1;in+1;i++){data[i]=rand()%80;printf(%d,data[i]);}printf(\n);while(1){printf(inputdatafound:);scanf(%d,&x);if(x0)break;for(i=1;in+1;i++)if(data[i]==x)break;if(in)printf(nofind%d\n,x);elseprintf(find%dinposition%d\n,x,i);}}165.二分查找技术又称折半查找，效率非常高。要求数据是有序的。步骤：为数组的头、尾和中点设标记将键入数与中点数相比较，抛弃一半区间设立新的头或尾，直至获得结果。#includestdio.h#includestdlib.hvoidmain(){chars[41];inti,j,n,p,t,t1,t2,d[101];srand((unsigned)time(NULL));n=100;for(i=1;in+1;i++)d[i]=rand()%100;for(i=2;in+1;i++){t=d[i];for(j=i-1;j0;j--){if(t=d[j])break;d[j+1]=d[j];}d[j+1]=t;}for(i=1;in+1;i++){printf(%-3d,d[i]);if(i%10==0)printf(\n);}gets(s);p=atoi(s);t1=1;t2=n;while(t1=t2){t=(t1+t2)/2;if(d[t]==p)break;if(d[t]p)t2=t-1;elset1=t+1;}if(t1t2){printf(查无此数);return;}for(i=t-1;i0;i--)if(d[i]!=p)break;i++;printf(开始位置：%d,i);}