汉扬编程 编程大纲 C语言学习|选择法排序及折半查找法查找

C语言学习|选择法排序及折半查找法查找

C语言学习|选择法排序及折半查找法查找

数组名作为函数参数示意图

C语言学习|选择法排序及折半查找法查找

交换法排序,读者只要仔细研究一下这个算法就不难发现,其排序效率较低。因为在第i轮(i=0,1,2……,n-2)比较中,第i+1个数和后面所有的数都要进行一次比较,每进行一次比较,若后面的数大就交换位置,这样每轮比较中最多需要n-1次交换操作,从而导致需要交换的次数太多。

C语言学习|选择法排序及折半查找法查找

事实上,完全可以在找出余下的数中的最大值再与第i+1个数交换位置,这样每轮比较中最多只有一次交换操作,整个算法最多有n-1次交换操作。虽然比较操作未能减少,但交换操作可以从总体上减少,这种改进的算法称为选择法排序。

C语言学习|选择法排序及折半查找法查找

按选择法进行排序的过程如图所示:

选择法排序示意图

设计一个函数对实型数组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;

}

本文来自网络,不代表汉扬编程立场,转载请注明出处:http://www.hyzlch.com/mianfei/6063.html

学C++是不是要先学C语言?

C语言是“高级语言”吗?为什么很多程序员叫它“中级语言”?

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

返回顶部