本帖最后由 09927306 于 2011-1-8 18:50 编辑
【例5-7】 选择排序。假设有20个数，要求将它们按从小到大的顺序排列。 离开数组，任何排序算法都难以实现。因此，先将20个数存放在数组a中，然后进行选择排序。以20个元素从小到大排序为例，选择排序的基本思想是：第一轮从所有20个数中选出最小的数，即先将a[0]与其后的各个数a[j]进行比较，凡出现比a[0]小的数就记下它的位置j，经过一轮（共比较19次）后，最小的数就选择出来了，将它与a[0]交换位置。这样，经过第一轮比较，最小数被存放在a[0]中。第二轮从余下的19个数中选出最小的数存放在a[1]中，即将a[1]与其后的各个数a[j]进行比较，凡出现比a[1]小的数就记下它的位置j，经过这一轮（共比较18次）后，次小的数就选择出来了，把它交换到a[1]中。依次类推，到第19轮时，要从最后剩下的两个数中选出最小数存放在a[18]中，最大的数则落在a[19]中。至此，整个数组已经有序。程序实现时，要用两重循环，外层循环控制比较的轮数i（共19轮），内层循环控制该轮比较的次数j（j从i+1变化到20）。 要对n个数进行选择排序，总共要进行(n–1)+(n–2)+…+1=n(n–1)/2次比较和最多n–1次交换，是一种比较简单但效率较低的排序方法。程序如下：
- #include <stdio.h>
- #define N 20
- main()
- { int i,j,k;
- float a[N],t;
- for (i=0;i<N;i++)
- scanf("%f",&a[i]);
- for (i=0;i<N-1;i++)
- { k=i;
- for (j=i+1;j<N;j++)
- if (a[j]<a[k])
- k=j; /* 记录比a[i]小的元素的位置 */
- if (i!=k) /* 必要时进行交换 */
- { t=a[i]; a[i]=a[k]; a[k]=t; }
- }
- for (i=0;i<N;i++)
- printf("%6.2f%c",a[i],(i%10==9||i==N-1)?'':' ');
- /* 按每行10个元素输出排序结果 */
- }
程序运行结果如下：
2 3 6 1 7 5 10 8 15 20 4 9 19 11 18 16 17 12 14 13↙
1.00
2.00
3.00
4.00
5.00
6.00
7.00
8.00
9.00
10.00
11.00 12.00 13.00 14.00 15.00 16.00 17.00 18.00 19.00 20.00
如果要求从大到小排序，只要将内层循环中的if (a[j]<a[k])改为if (a[j]>a[k])即可。 【例5-8】 用冒泡排序算法对20个数按从小到大的顺序进行排序。 冒泡排序算法是另一种常用的排序算法。以20个元素从小到大排序为例，它的基本过程是：第一轮在所有的20个数中依次进行相邻两个数的比较，即先将a[0]与a[1]比较，若a[0]>a[1],则将二者交换；然后将a[1]与a[2]比较，若a[1]>a[2]，则将二者交换；否则再进行下面两个相邻元素的比较。经过这一轮19次比较后，最大数已沉到数组的底部，即a[19]存放的是最大值。第二轮在去除最大数后剩余的19个数中同样进行两个相邻数的比较和交换，即a[0]与a[1]、a[1]与a[2]比较，经18次比较和交换后，次大数沉底，存放在a[18]中。依次类推，到第19轮时，将数组最顶部的两个数进行比较和交换，使最小数上浮到数组的顶部，存放在a[0]中。至此，排序过程结束。在整个排序过程中，每轮比较都使当前数据集合中的最大数沉底，而最小数则像气泡一样不断上浮，直到气泡上浮到数组的最顶部，排序过程即告结束，因此称之为冒泡排序。 冒泡排序的比较次数和选择排序相同，但交换次数比选择排序大。程序如下：
- #include <stdio.h>
- #define N 20
- main()
- { int i,j,k;
- float a[N],t;
- for (i=0;i<N;i++)
- scanf("%f",&a[i]);
- for (i=0;i<N-1;i++)
- for (j=0;j<N-i-1;j++)
- if (a[j]>a[j+1])
- { t=a[j];
- a[j]=a[j+1];
- a[j+1]=t;
- }
- for(i=0;i<N;i++)
- printf("%6.2f%c",a[i],(i%10==9||i==N-1)?'':' ');
- }
程序运行结果如下：
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1↙
1.00
2.00
3.00
4.00
5.00
6.00
7.00
8.00
9.00 10.00
11.00 12.00 13.00 14.00 15.00 16.00 17.00 18.00 19.00 20.00
【例5-9】 假设有n个从小到大排好序的数，存放在数组v中，请编制程序实现二分检索（对分检索、折半检索）算法。 二分检索算法通过每次将搜索区间缩小一半的方法，很快将搜索区间缩小为1个元素，从而确定是否查找到待查的数据。先设立3个标记：low指向搜索区间顶部，high指向搜索区间底部，mid=(low+high)/2则指向搜索区间中部。开始时，令low=0，high=n–1，即将整个数组作为搜索区间。当要查找某个x是否在数组v中时，按下列步骤进行。 （1）求mid=(low+high)/2,判断v[mid]是否等于x，若v[mid]=x，则已搜索到，查找结束；若v[mid]<x，说明x在区间后半部分，可令low=mid+1，high保持不变，即将该区间后半部分作为新的搜索区间；若v[mid]>x，说明x在区间的前半部分，可令high=mid–1，low保持不变，即将该区间上半部分作为新的搜索区间。总之，经过这次处理，搜索区间已缩小为原来的一半。 （2）在新的搜索区间上求mid=(low+high)/2，重复与（1）中相同的操作，可继续将搜索区间进一步缩小。 （3） 经过有限次（最多log2n次）搜索后，最终结果是：或者x已找到，或者已出现low=high，即区间缩小为只有1个元素。如果是后一种情况，就可以肯定地得到x是否在数组中的结论。 程序如下：
- #include <stdio.h>
- #define N 20
- main()
- { int v[N],x,low,high,mid,i;
- printf("Enter data being sorted :\n");
- for (i=0;i<N;i++)
- scanf("%d",&v[i]);
- printf("Enter number to be searched :\n");
- scanf("%d",&x);
- low=0;
- high=N-1;
- mid=(low+high)/2;
- while (low<high&&x!=v[mid])
- { if(x<v[mid])
- high=mid-1;
- else
- low=mid+1;
- mid=(low+high)/2;
- }
- if (x==v[mid])
- printf("%d is at position %d.of array.",x,mid);
- else
- printf("%d is not in array.",x);
- }
程序运行时，先读入N个有序数，然后读入要查找的x，继而使用二分检索算法来进行查找。程序运行情况如下：
1 2 3 4 5 6 7 8 9 10↙
11 12 13 14 15 16 17 18 19 20↙
14↙
14 is at position 13 of array.
| 
楼主