c语言折半法排序如何理解（C语言学习选择法排序及折半查找法查找）
c语言折半法排序如何理解（C语言学习选择法排序及折半查找法查找）void sort(float score[] long num[] int n);#define ARR 100选择法排序示意图设计一个函数对实型数组score中的n个学生成绩降序排序：#include<stdio.h>
数组名作为函数参数示意图
交换法排序，读者只要仔细研究一下这个算法就不难发现，其排序效率较低。因为在第i轮（i=0，1，2……，n-2）比较中，第i 1个数和后面所有的数都要进行一次比较，每进行一次比较，若后面的数大就交换位置，这样每轮比较中最多需要n-1次交换操作，从而导致需要交换的次数太多。
事实上，完全可以在找出余下的数中的最大值再与第i 1个数交换位置，这样每轮比较中最多只有一次交换操作，整个算法最多有n-1次交换操作。虽然比较操作未能减少，但交换操作可以从总体上减少，这种改进的算法称为选择法排序。
按选择法进行排序的过程如图所示：
选择法排序示意图
设计一个函数对实型数组score中的n个学生成绩降序排序：
#include<stdio.h>
#define ARR 100
void sort(float score[] long num[] int n);
int main()
{
float score[ARR];
long num[ARR];
int n i;
printf("Pleace enter total number:");
scanf("%d" &n);
printf("Pleace enter the number and score:");
for(i=0;i<n;i )
{
scanf("%ld%f" &num[i] &score[i]);
}
sort(score num n);
return 0;
}
void sort(float score[] long num[] int n)
{
int i j k;
float temp1;
long temp2;
for(i=0;i<n-1;i )
{
k=i;
for(j=i 1;j<n;j )
{
if(score[j]>score[k])//这样比较按降序排序
{
k=j;
}
if(k!=i)//若k中记录的最大数序号不等于i，即找到的最大数不在位置i上
{
temp1=score[k];
score[k]=score[i];
score[i]=temp1;
temp2=num[k];
num[k]=num[i];
num[i]=temp2;
}
}
}
printf("sorted results:\n");
for(i=0;i<n;i )
{
printf("%ld\t4.0f\n" num[i] score[i]);
}
}
折半查找的基本思想：使用分而治之的方法。首先选取位于数组中间的元素，将其与查找键进行比较。如果二者相等，则查找键被找到，返回数组中间元素的下标；否则，将其与查找范围缩小为原来的一半，即在一半的数组元素中查找。在数组元素按升序排序的情况下，如果查找键小于数组的中间元素，则在前一半数组元素中继续查找，否则在后一半数组元素中继续查找。如果在该子数组中仍未找到查找键，则在原数组的1/4大小的子数组中继续查找。不断重复上述查找过程，直到查找键等于某个子数组中间元素的值（找到查找键），或者子数组只包含一个不等于查找键的元素（即没有找到查找键）时为止。
编写程序如下：
#include<stdio.h>
#define ARR 100
int binsearch(long a[] int n longx)
{
int mid;
int low=0;//数据区间左端点置为0
int high=n-1;//数据区间右端点置为n-1
while(low<=high)//如果左端点小于等于右端点，则继续查找
{
mid=(high low)/2;//取数据区间的中点
if(x>a[mid])//若x>a[mid] 则修改区间的左端点
{
low=mid 1;
}
else if(x<a[mid])//若x<a[mid] 则修改区间的右端点
{
high=mid-1;
}
else//若x=a[mid] 则返回找到的下标值mid
{
return mid;
}
}
return -1;//若循环结束还是没找到，则返回值-1
}
int main()
{
float score[ARR];
long num[ARR] x;
int n i pos;
printf("Pleace enter total number:");
scanf("%d" &n);//从键盘输入学生人数n
printf("Pleace enter the number and score:");
for(i=0;i<n;i )//按学号由大到小的顺序输入n个学生的学号和成绩
{
scanf("%ld%f" &num[i] &score[i]);
}
printf("Pleace enter the searching number:");
scanf("%ld" &x);//以长整型格式从键盘输入待查着的学号x
pos=binsearch(num n x);//调用search查找x在数组num中的下标位置
if(pos!=-1)//若返回的学号不为-1，则输出该学生的成绩
{
printf("score=%4.0f\n" score[pos]);
}
else//否则，说明未找到，输出“Not found！”的提示信息
{
printf("Not found!\n");
}
return 0;
}
