C 语言课件3 数组常用操作

用冒泡排序法对数组进行增序

（从小到大）的排序

排序的规则有两种：一种是增序（从小到大）；另一种是降序（从大到小）冒泡排序法是常见的排序算法，它模拟水中气泡的排放规则，使重量“较轻”（值较小）的气泡浮到上面，重量“较重”（值较大）的气泡沉到下面，对每一趟排序，从第1个元素开始，比较相邻元素的大小，按照规则对调两者的位置，最终确定一个最大（或最小）的气泡的位置。

请看对6个数进行冒泡排序法的过程：985420895420859420854920854290854209大数沉淀，小数起泡a[0]a[1]a[2]a[3]a[4]a[5]for(i=0;i<=4;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}第1趟排序854209584209548209542809542089a[0]a[1]a[2]a[3]a[4]a[5]for(i=0;i<=3;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}第2趟排序542089452089425089420589a[0]a[1]a[2]a[3]a[4]a[5]for(i=0;i<=2;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}第3趟排序420589240589204589a[0]a[1]a[2]a[3]a[4]a[5]for(i=0;i<=1;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}第4趟排序204589024589a[0]a[1]a[2]a[3]a[4]a[5]for(i=0;i<=0;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}第5趟排序for(i=0;i<=4;i++)if(a[i]>a[i+1]){……}for(i=0;i<=3;i++)if(a[i]>a[i+1]){……}for(i=0;i<=0;i++)if(a[i]>a[i+1]){……}……for(i=0;i<=6-pass-1;i++)if(a[i]>a[i+1]){……}for(pass=1;pass<=5;j++)

pass:趟数从1到5

size个元素时pass:趟数从1到size-1i从0到size-pass-16个元素时pass=1pass=2pass=5voidbubblesort(intvalues[],intsize){intpass,j,temp;for(pass=1;pass<=size-1;pass++){ for(j=0;j<=size-1-pass;j++) if(values[j]>values[j+1]){ temp=values[j]; values[j]=values[j+1]; values[j+1]=temp; }} }将冒泡排序法定义为一函数将冒泡排序法定义为一函数bubbleSort(intvalues[],intn)：形参是待排序的一维数组和一维数组元素的个数。等同于bubbleSort(int*values,intn)形参定义为intvalues[]或int*values，是一维数组指针，对应的实参可为任意的一维数组名。形参定义为intvalues[len1]，则对应的实参是长度为len1的一维数组名。将打印一维数组功能定义为一函数。

voidprint(intvalues[],intsize){ inti; for(i=0;i<size;i++) printf("%4",values[i]); printf("\n");}voidmain(){ intscore1[]={10,3,56,89,80,60}; intscore2[]={78,100,45,12,78,90,3,5}; bubblesort(score1,6); print(score1,6); bubblesort(score2,8); print(score2,8);}31056608089351245787880100用选择法排序用选择法对数组中10个整数按由小到大排序。解题思路：所谓选择法就是先将10个数中最小的数与a[0]对换；再将a[1]到a[9]中最小的数与a[1]对换……每比较一轮，找出一个未经排序的数中最小的一个共比较9轮a[0]a[1]a[2]a[3]a[4]36194

16394

1

3694

1

3

496

1

3

4

69小到大排序#include<stdio.h>intmain(){voidsort(intarray[],intn);inta[10],i;printf("enterarray:\n");for(i=0;i<10;i++)scanf("%d",&a[i]);

sort(a,10);printf("Thesortedarray:\n");for(i=0;i<10;i++)printf("%d",a[i]);printf("\n");return0;}voidsort(intarray[],intn){inti,j,k,t;for(i=0;i<n-1;i++){k=i;for(j=i+1;j<n;j++)if(array[j]<array[k])k=j; t=array[k];

array[k]=array[i];

array[i]=t; }}在sort[i]~sort[9]中，最小数与sort[i]对换冒泡法排序的基本思想是：将相邻两个数进行比较，若前面数大，则交换两数位置，这样，最大数就会逐渐沉到最下面，即在最后一个元素的位置。例如有4个数放在数组a中，经过第一轮3次两两比较、交换，最大数就会沉到最后，存放在a[3]中。第二轮再将前面的3个数经过2次这样的两两比较、交换后，其中的最大数就会被存放在a[2]中，第三轮将剩下的2个数比较1次，大的数被换到a[1],小的数存放在a[0]中。这样，经过三轮比较就完成了4个数的排序。方法一：冒泡法排序其排序过程如图6-4所示。方法一：冒泡法排序一般地，对n个数进行排序，共需进行n-1轮比较，在第i轮中要对n-i+1个数进行n-i次相邻元素的两两比较、交换。假设有n个数存放在一维数组a中，则n个数的冒泡排序算法可用for循环表示为：for(i=0;i<=n-2;i++)for(j=0;j<=n-2-i;j++)if(a[j]>a[j+1])

将a[j]的值与a[j+1]的值互换；方法一：冒泡法排序#include<stdio.h>voidmain(){inti,j,n,a[100];inttemp;printf("Inputthenumberofdata:");

scanf("%d",&n);/*从键盘输入排序数据的个数*/printf("Input%ddata:",n);for(i=0;i<n;i++) scanf("%d",&a[i]);冒泡法排序源程序：printf("\nOutputtheoriginalarray:");for(i=0;i<n;i++)printf("%3d",a[i]);for(i=0;i<=n-2;i++)for(j=0;j<=n-2-i;j++)if(a[j]>a[j+1]) { temp=a[j]; a[j]=a[j+1];

a[j+1]=temp; }冒泡法排序源程序：冒泡排序算法printf("Outputthesortedarray:");for(i=0;i<n;i++)printf("%3d",a[i]);/*输出排序后的一维数组序列*/printf("\n");}冒泡法排序源程序：运行结果为：Inputthenumberofdata:4↙Input4data:23564312↙Outputtheoriginalarray:23564312Outputthesortedarray:12234356选择排序法的基本思想是：

对存放在数组中待排序的数首先找出其中的最小值，与第一个元素进行交换，然后找出从第二个元素开始至最后一个元素中的最小值与第二个元素交换，以此类推，直到整个数组中的数有序。方法二：选择排序法假设有存放在数组中待排序的6个数a[0]、a[1]、a[2]、a[3]、a[4]和a[5]先找出其中的最小数与a[0]交换；然后在a[1]、a[2]、a[3]、a[4]和a[5]中找出最小数与a[1]进行交换；在a[2]、a[3]、a[4]和a[5]中找出最小数与a[2]进行交换；在a[3]、a[4]和a[5]中找出最小数与a[3]进行交换；在a[4]和a[5]中找出最小数与a[4]进行交换，完成排序。方法二：选择排序法其排序过程如图6-5所示。方法二：选择排序法#include<stdio.h>#defineN10/*设定待排序数据的个数*/main(){inta[N];

inti,j,k,t;printf("Input%dnumbers:",N);for(i=0;i<=N-1;i++)scanf("%d",&a[i]);/*输入原始的一维数组

序列*/选择法排序源程序：for(i=0;i<=N-2;i++)

{k=i;for(j=i+1;j<=N-1;j++)if(a[j]<a[k])k=j;if(i!=k)

{t=a[i];a[i]=a[k];a[k]=t; } }选择法排序源程序：变量k用于记录最小值的下标，假定第i次中最小数的位置是ia[k]是每次比较后当前的最小数若最小数不是默认的a[i],则将a[i]与a[k]的值交换选择排序算法printf("thesortednumbers:");for(i=0;i<=N-1;i++)printf("%d",a[i]);printf("\n");}选择法排序源程序：输出排序后的一维数组序列Input10numbers:65839102471↙thesortednumbers:12345678910运行结果:在有序的数组中，用折半查找法查找一个特定的值。在有序的数组中，二分查找法是一种比较快捷的查找方法。折半查找法基本思路：先将整个数组作为查找区间，用给定的值与查找区间的中间元素的值相比较，若相等，则查找成功；若不等，则缩小范围，判断该值落在区间的前一部分还是后一部分，再将其所在的部分作为新的查找区间，继续上述过程，一直到找到该值或区间长度小于0表明查找不成功为止。例如：用折半查找法查找key=80元素31056608085a[0]a[1]a[2]a[3]a[4]a[5]low=3mid=(low+hight)/2hight=5a[mid]<80low=0hight=5mid=4a[mid]=80仅比较2次即找到关键字。折半查找法是快速查找法。inta[size]，查找是否含有关键字key的元素，折半查找法的算法描述过程：1.设置查找的最初区间[low，high]，low=0，high=size-1，mid=(low+high)/2；found是否找到key的标志，初值0。2.判断a[mid]和key之间的关系:若key=a[mid]，则成功找到，置found=1,查找结束。若key<a[mid]，设定下一查找范围是左半区间[low，mid-1]。若key>a[mid]，设定查找范围是右半区间[mid+1，high]。

重复步骤2条件：(low<=high)且found==03.循环结束时，若found==1则找