用选择法排序，用折半法找数。详见说明，求大神解答！(用c++写）_百度知道
用选择法排序，用折半法找数。详见说明，求大神解答！(用c++写）
用选择法对 10 个整数按从大到小的顺序排序。10 个整数用cin 输入。排序完成后输入一个数，要求用折半查找法找出该数是数组中第几个元素的值。如果该数不在数组中，则输出“无此数”。1、把排序算法写成函数形式，用指针变量作为排序函数的参数，在排序算法中用指针法访问数组元素。2、把查找算法写成函数形式，用指针变量作为查找函数的参数，在查找算法中用指针法访问数组元素。
提问者采纳
#include&&stdio.h&#include&&stdlib.h&void&swap(int&&a,&int&&b){&int&tmp&=&a;&a&=&b;&b&=&&}void&select_sort(int*&arr,&int&n){&for&(int&i&=&0;&i&&&n;&i++)&{&&int&i_max&=&i;&&for&(int&j&=&i+1;&j&&&n;&j++)&{&&&if&(arr[j]&&&arr[i_max])&&&{&i_max&=&j;&}&&}&&swap(arr[i],&arr[i_max]);&}}int&binary_search(int*&arr,&int&n,&int&num)&{&int&l&=&0,&r&=&n;&while&(l&&&r)&{&&int&m&=&(l+r)&/&2;&&if&(arr[m]&==&num)&&{&return&m;&}&&if&(num&&&arr[m])&&{&r&=&m;&}&&else&&{&l&=&m+1;&}&}&return&-1;}int&main(int&argc,&char*&args[]){&const&int&count&=&10;&int&data[count];&printf(&Please&input&%d&number:&,&count);&for&(int&i&=&0;&i&&&&i++)&{&&scanf(&%d&,&&data[i]);&}&select_sort(data,&count);//&while&(true)&{&&printf(&Please&input&a&number&for&search:&);&&int&&&scanf(&%d&,&&num);&&int&pos&=&binary_search(data,&count,&num);&&if&(pos&==&-1)&{&&&printf(&No&such&number&%d&in&data!&,&num);&&}&else&{&&&printf(&Number&%d&is&at&pos&%d.&,&num,&pos);&&}&}&::system(&pause&);&return&0;}
提问者评价
其他类似问题
选择法的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁2400人阅读
转载请注明出处：前言& & 本来想将所有的内部排序总结为一篇博文，但是随着研究的深入，还是放弃了这个念头，斟前酌后，还是觉得分开来写比较好，具体原因，看完本篇博文也就自然明了了。& & 本篇文章主要探讨插入排序和希尔排序，之所将二者放在一起，很明显，是因为希尔排序是建立在插入排序的基础之上的。& & 注：以下各排序算法的N种实现方法大部分都是我根据算法思想，自己写出来的，或者是参考其本身的经典实现，我自己都已测试通过，但不敢保证一定都没问题，如果有疑问，欢迎指出。插入排序& & 插入排序的思想很简单，它的基本操作就是将一个数据插入到已经排好序的序列中，从而得到一个新的有序序列。根据查找插入位置的实现思路不同，它又可以分为：直接插入排序、折半插入排序、2-路插入排序。。。这里，我们主要探讨下直接插入排序和折半插入排序。& & 直接插入排序& & 直接插入排序是最基本的插入排序方法，也是一种最简单的排序方法。其基本实现思想如下：& & 1、首先把第一个元素单独看做一个有序序列，依次将后面的元素插入到该有序序列中；& & 2、插入的时候，将该元素逐个与前面有序序列中的元素进行比较，找到合适的插入位置，形成新的有序序列；& & 3、当有序序列扩大为整个原始序列的大小时，排序结束。& & & 第一种实现方法& & 按照该思想，我第一次写出来的实现代码如下：/*
第一种代码形式
插入排序后的顺序为从小到大
void Insert_Sort1(int *arr,int len)
//从第1个元素开始循环执行插入排序
for(i=1;i&i++)
{ //将第i个元素分别与前面的元素比较，插入适当的位置
if(arr[i]&arr[i-1])
{ //一直向左进行比较，直到插入到适当的位置
int key = arr[i];
int count = 0; //用来记录key在与前面元素时向左移动的位置
while(i&0 && key&arr[i-1])
arr[i] = arr[i-1];
arr[i-1] =
//将待插入的数定位到下一个元素，
//因为后面还要执行i++，所以这里不再加1
}& & & 第二种实现方法& & &很明显，上面的代码有些冗杂，如果面试的时候让你手写插入排序的代码，很难一下子写出来。于是，我考虑将while循环去掉，直接在后面再来一个for循环，每次比较，遇到比自己大的就交换，直到遇到比自己小的，才退出for循环。这样代码改成了如下形式：/*
第二种代码形式
插入排序后的顺序为从小到大
void Insert_Sort2(int *arr,int len)
for(i=1;i&i++)
for(j=i-1;j&=0 && arr[j]&arr[j+1];j--)
//交换元素数值
//由于不会出现自己与自己交换的情况，
//因此可以安全地用该交换方法
arr[j]^=arr[j+1];
arr[j+1]^=arr[j];
arr[j]^=arr[j+1];
}& & & 第三种实现方法& & 上面的代码要用到数据的交换，即每次要插入的元素要逐个地与前面比它大的元素互换位置，而数据交换需要三步赋值操作，我们完全可以避免进行如此多的操作（排序算法中一般都会尽量避免数据的交换操作），为了提高执行效率（虽然该执行效率的提高可能并没有那么显著），我们再回过头来看第一种实现方法，我们可以通过key变量先将待插入的数据保存起来，在比较时只将元素右移一位即可，最后再将key放到要插入的位置，这样可以减少两个赋值操作的执行时间。这样我们可以把代码改成如下实现形式：/*
第三种代码形式
插入排序后的顺序为从小到大
void Insert_Sort3(int *arr,int len)
for(i=1;i&i++)
if(arr[i] & arr[i-1])
{ //向前逐个比较，直到需要插入的地方
int key = arr[i];
for(j=i-1;j&=0 && arr[j]&j--)
arr[j+1] = arr[j];
arr[j+1] =
}& &&这也是最常见的实现形式，如果在面试中要手写插入排序的话，直接把这种实现代码写出来就可以了。& & 另外，很明显可以看出来，对于长度为n的待排序咧，直接插入排序的平均时间复杂度为O（n*n），而且直接插入排序的比较次数与原始序列的中各元素的位置密切相关，待排序的序列越接近于有序，需要比较的次数就越小，时间复杂度也就越小。& & 折半插入排序& & &直接插入排序算法简单，且容易实现，当待排序的长度n很小时，是一种很好的排序方法，尤其当原始序列接近有序时，效率更好。如果待排序的长度n很大，则不适宜采用直接排序。这时我们可以考虑对其做些改进，我们可以从减少比较和移动的次数入手，因此可以采用折半插入排序，其思想类似于折半查找，这里不再详细说明，直接给出实现代码：/*
插入排序后的顺序为从小到大
void BInsert_Sort(int *arr,int len)
//从第1个元素开始循环执行插入排序
for(i=1;i&i++)
int low =0;
int high = i-1;
int key = arr[i];
//循环至要插入的两个点之间
while(low&=high)
int mid = (low+high)/2;
if(key&arr[mid])
high = mid-1;
low = mid+1;
//循环结束后low=high+1，并且low位置即为key要插入的位置
//从low到i的元素依次后移一位
for(j=i;j&j--)
arr[j] = arr[j-1];
//将key插入到low位置处
arr[low] =
}& & 从代码中可以看出，折半插入排序所需附加的存储空间与直接插入排序相等，时间上来看，折半插入排序减少了比较的次数，但是元素的移动次数并没有减少。因此，折半插入排序的平均时间复杂度仍为O（n*n）。希尔排序& & 希尔排序（shell排序），又称缩小增量排序。上面我们提到，直接插入排序在原始序列越接近有序的情况下，排序效率越高，希尔排序正是利用了直接插入排序的这个优势。希尔排序的基本思想如下：& & 它将序列按照某个增量间隔分为几个子序列，分别对子序列进行插入排序，而后再取另一增量间隔，对划分的子序列进行插入排序，依次往后。。。待序列已经大致有序，最后再对整个序列进行插入排序（即增量间隔为），从而得到有序序列。& & 本文的重点放在排序算法的各种代码实现上，因此不再对具体的实现思想做过多的阐述，读者可以查阅相关资料或书籍来熟悉希尔排序的具体思想。由于希尔排序要用到插入排序，因此，我们依次根据上面基本插入排序的三种不同实现方法来书写希尔排序的代码。& & 第一种实现方法& & 仔细分析希尔排序的实现思想，会发现，如果要循环对各个子序列依次进行插入排序，我们需要在直接插入排序代码的外面再加一层for循环，用来循环所有的子序列。我们根据插入排序的第一种实现方法写出的代码如下：/*
第一种形式的代码
对长为len的数组进行一趟增量为ader的插入排序
本算法在插入排序算法的第一种实现形式上进行修改得到
void Shell_Insert1(int *arr,int len,int ader)
//循环对ader个子序列进行插入排序操作
for(k=0;k&k++)
for(i=ader+k;i&i+=ader)
//对一个子序列进行插入排序操作
{ //将第i个元素分别与前面的每隔ader个位置的元素比较，插入适当的位置
if(arr[i]&arr[i-ader])
{ //一直向左进行比较，直到插入到适当的位置
int key = arr[i];
int count = 0; //用来记录key在与前面元素比较时向左移动了几个ader长度
while(i&k && key&arr[i-ader])
arr[i] = arr[i-ader];
arr[i-ader] =
//将待插入的数定位到下一个元素，执行下一次插入排序
//因为后面还要执行i+=ader，所以这里回到原位置即可
i += count*
}& & 第二种实现方法& & 很明显，与上面插入排序的第一种实现方法一样，更加冗杂，现在我们用插入排序的第二种实现方法来实现希尔排序，同样采用添加外层for循环的方式，来循环对每个子序列进行插入排序。代码如下：/*
第二种形式的代码
对长为len的数组进行一趟增量为ader的插入排序
本算法在插入排序算法的第三种实现形式上进行修改得到
void Shell_Insert2(int *arr,int len,int ader)
int i,j,k;
//循环对ader个子序列各自进行插入排序
for(k=0;k&k++)
for(i=ader+k;i&i+=ader)
for(j=i-j&=k && arr[j]&arr[j+ader];j-=ader)
//交换元素数值
arr[j]^=arr[j+ader];
arr[j+ader]^=arr[j];
arr[j]^=arr[j+ader];
}& & 第二种实现方法的改进& & 上面的代码中需要三个for循环，因为我们是循环对每个子序列进行插入排序的，实际上我们还可以这样做：对每个子序列交叉进行排序。比如，第1个子序列中的第2个元素A5（A5表示它在总序列A中的位置序号是5，下同）刚进行完插入排序操作，便接着对第2个子序列中的第2个元素A6进行插入排序操作。这样我们就可以少写一个for循环，但实际比较的次数还是相同的，只是代码更加简洁。如下：/*
在第二种代码的形式上继续精简代码
交叉进行各个子序列的插入排序
void Shell_Insert2_1(int *arr,int len,int ader)
//交叉对ader个子序列进行插入排序
for(i=i&i++)
for(j=i-j&=0 && arr[j]&arr[j+ader];j-=ader)
//交换元素数值
//由于不会出现自己与自己交换的情况
//因此可以安全地用该交换方法
arr[j]^=arr[j+ader];
arr[j+ader]^=arr[j];
arr[j]^=arr[j+ader];
}& & 第三种实现方法& & 同样，根据插入排序的第三种实现方法，循环逐个对每个子序列进行插入排序操作，我们可以得到希尔排序的实现方法，如下：/*
第三种形式的代码
对长为len的数组进行一趟增量为ader的插入排序
本算法在插入排序算法的第二种实现形式上进行修改得到
void Shell_Insert3(int *arr,int len,int ader)
int i,j,k;
//循环对ader个子序列各自进行插入排序
for(k=0;k&k++)
for(i=ader+k;i&i+=ader)
if(arr[i] & arr[i-ader])
int key = arr[i];
for(j=i-j&=k && arr[j]&j-=ader)
arr[j+ader] = arr[j];
arr[j+ader] =
}& & 第三种实现方法的改进& & 我们可以对该方法做出同样的改进，对各个子序列进行交叉排序，代码如下：/*
在第三种代码的形式上继续精简代码
交叉进行各个子序列的插入排序
void Shell_Insert3_1(int *arr,int len,int ader)
//对ader子序列交叉进行插入排序
for(i=i&i++)
if(arr[i] & arr[i-ader])
int key = arr[i];
for(j=i-j&=0 && arr[j]&j-=ader)
arr[j+ader] = arr[j];
arr[j+ader] =
}& & 同样，如果在面试中要手写希尔排序的代码，推荐这种方法实现的代码。& & 希尔排序的时间复杂度根据选择的增量序列不同会有所不同，但一般都会比n*n小（序列长度为n）。& & 在选择增量序列时，应使增量序列中的值没有除1之外的公因子，并且最后一个增量值必须为1.& & 看如下两个增量序列：n/2、n/4、n/8...11、3、7...2^k-1& & 第一个序列称为希尔增量序列，使用希尔增量时，希尔排序在最坏情况下的时间复杂度为O(n*n)。& & 第二个序列称为Hibbard增量序列，使用Hibbard增量时，希尔排序在最坏情况下的时间复杂度为O(n^3/2)。&& & 经验研究表明，在实践中使用这些增量序列要比使用上面两个增量序列的效果好的多，其中最好的序列是{1、5、9、41、109...}& & 该序列中的项或是9*4^i-9*2^i+1，或是4^i-3*2^i+1。& & 希尔排序的性能是完全可以接受的，即时是对数以万计的n来说也是如此。编程的简单特点使得它成为对适度的大量输入数据进行排序时经常选用的算法。完整代码下载& & 各种实现方式的完整的代码打包下载地址：
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：465176次
积分：9922
积分：9922
排名：第503名
原创：217篇
转载：21篇
评论：1258条
阅读：20627
文章：14篇
阅读：17985
文章：20篇
阅读：16465
文章：56篇
阅读：40767
文章：23篇
阅读：61770
阅读：40090
文章：24篇
阅读：69787
文章：13篇
阅读：49618
(1)(6)(28)(51)(5)(29)(5)(8)(33)(21)(11)(20)(2)(19)查找算法实现与性能分析 (数据结构课程设计)_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
25页免费14页免费21页4下载券26页2下载券15页1下载券 38页4下载券30页1下载券22页4下载券11页2下载券15页2下载券
喜欢此文档的还喜欢20页免费2页免费18页1下载券5页免费9页2下载券
查找算法实现与性能分析 (数据结构课程设计)|二​、​ ​静​态​查​找​算​法​实​现​
​
.​顺​序​查​找​：​是​从​数​组​的​最​后​一​个​元​素​开​始​查​找​,​直​到​找​到​待​查​找​元​素​的​位​置​,​直​到​查​找​到​结​果​。​
​
.​折​半​查​找​：​折​半​查​找​是​将​待​查​找​的​数​组​元​素​不​断​的​分​为​两​部​分​,​每​次​淘​汰​二​分​之​一​,​但​是​有​个​大​前​提​是​,​元​素​必​须​是​有​序​的​,​如​果​是​无​序​的​则​要​先​进​行​排​序​操​作​
​
​
​
​三​、​动​态​查​找​算​法​实​现​
​
​ ​二​叉​排​序​树​建​立​、​查​找​：
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
你可能喜欢求数据结构大神们帮我做看下这个查找和排序题目、_百度知道
求数据结构大神们帮我做看下这个查找和排序题目、
5.1 问题描述对附件中的”RFCdoc.txt”统计单词出现的频率。注意：单词”The”和”the”算同一个单词（也就是不区分大小写）。统计好后，输出出现频率最高的5个单词和它对应的频率。单词的定义为：只包含英文字母的连续字符串。如：“This is RFC document.”，则共包含四个单词，注意，最后一个单词“document”不要把点号包含在内。5.2 问题分析为了做统计操作，每个单词必须保存一个和它相关的频率。算法可以为：扫描一遍文件，对每个单词逐一处理。当扫描到某个单词时，则查看已经统计的该单词出现的频率，将频率加一，再赋给该单词。如果该单词还未出现过，则频率为1。为了保存出现的单词和它的频率，可以采用两种方式保存：线性表和Hash表。如果采用顺序存储的线性表，则线性表的每个元素存储一个单词和对应的频率。对文件扫描时，每扫描到一个单词，可以对该线性表做二分查找（前提是线性表里的单词有序），然后对频率加1。为了加快查找速度，可以考虑使用Hash表存储单词的信息，则Hash表的key为该单词，而value为对应的频率。对文件扫描时，每扫描到一个单词，则在Hash表中查看该单词是否存在，如果存在，更改其value（频率），如果不存在，则在Hash表中增加一个key-value对。为了能输出出现频率最高的5个单词，则需要进行排序。可以使用简单选择法，选择出频率最高的5个单词，但最好用堆排序的方法完成此操作。5.3 实现提示如果Hash表的随机函数自行构造，则应首先调整好随机函数使其尽可能分布均匀。字符串到整型值的转换方法可直接利用C语言中的toascii函数
提问者采纳
#include &stdio.h&#include &string.h&#include &stdlib.h&#define N 100//散列表长度struct Node{ char* char* Node*}*heads[N];//散列表，用链处理冲突int hash(char* key)//散列函数{ unsigned long h=0; while(*key) {
h=(h&&4)+*key++;
unsigned long g=h & 0xF0000000L;
h&=~g; } return h&N;}Node* find(char* key)//查找{ Node* cur=heads[hash(key)]; while(cur) {
if(!strcmp(cur-&key,key))
cur=cur-& } return NULL;}void insert(char* key,char* val)//插入{ int i=hash(key); Node* head=heads[i]; if(find(key)==NULL) { Node* tmp=(Node*)malloc(sizeof(Node)); tmp-&key=(char*)malloc(strlen(key)+1); tmp-&val=(char*)malloc(strlen(val)+1); strcpy(tmp-&key,key); strcpy(tmp-&val,val);
tmp-&next= heads[i]= }}main(){ char tmp[100],*key,* Node* FILE *fp=fopen(&abc.txt&,&r&); if(fp==NULL) {
printf(&打开文件有问题\n&);
exit(1); } while(fgets(tmp,100,fp)!=NULL) {
if(tmp[strlen(tmp)-1]=='\n')
tmp[strlen(tmp)-1]='\0';
key=strtok(tmp,&\t&);
val=strtok(NULL,&\t&);
insert(key,val); } printf(&输入你要查找的单词:\n&); while(gets(tmp)) {
cur=find(tmp);
if(cur==NULL)
printf(&没找到\n&);
printf(&%s\n&,cur-&val);
其他类似问题
按默认排序
其他2条回答
代表它的域名是目录是main文件名叫news.asp用的是asp技术
char b[30], int i=0,m=1,j=0,k=0,t=0,flag=0; fp=fopen(&case1.in&,&r&); while((ch=fgetc(fp))!=EOF){
if('A'&=ch && ch&='Z') ch=ch+32;
if('a'&=ch && ch&='z'){
不会，帮不了你
数据结构的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁冒泡排序和折半查找的程序的准确写法
冒泡排序和折半查找的程序的准确写法 70
最好把几种算法的C语言表达全部写给我，共五大种七小种，呵呵上机时总是写不对，谢谢各位大大了
补充：能不能写上注释啊，我邮箱：tuxiao@
发给你吧！都是我学数据结构时编的；
我相信对你有用
你邮箱号？
其他回答 (1)
一、选择法对数组中10个数由小到大排序：
void sort(int array[ ],int )
{int i,j,k,t;
for(i=0;i&=n-1;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;}
printf(&enter the array\n&);
for(i=0;i&10;i++)
scanf(&%d&,&a[i]);
sort(a,10);
printf(&the sorted array:\n&);
for(i=0;i&10;i++)
printf(&%d&,a[i]);
printf(&\n&);
}
二、冒泡法对10个数排序（由小到大）：
printf(&input 10numbers:\n&);
for(i=1;i&=9;i++)
scanf(&%d&,&a[i]);
printf(&\n&);
for(j=1;j&=9;j++)
for(i=1;i&=10-j;i++)
if(a[i]&a[i+1])
{t=a[i];a[i]=a[i+1];a[i+1]=t;}
printf(&the sorted numbres:\n&);
for(i=1;i&11;i++)
printf(&%d&,a[i]);
}
三、用选择法对10个整数按由大到小顺序排列（指针变量运用）。
main(
)
{int *p,i,a[10];
p=a;
for(i=0;i&10;i++)
scanf(&%d&,p++);
p=a;
sort(p,10);
for(p=a,i=0;i&10;i++)
{printf(&%d&,*p)p++;}
}
sort(int(int x[ ],int n)
{int i,j,k,t;
for(i=0;i&n-1;i++)
for(j=i+1;j&n;j++)
if(x[j]&x[k])k=j;
{t=x[i];x[i]=x[k];x[k]=t;}
我每次写的编译后都会有个Warning，说founction must return a value是什么意思
这不会影响运行结果吧。
可是一运行就进入死循环或空循环
不是空循环，有的是在等你数入数据，
我是说输入数据以后啊
你要注意数据输入的方法，有的是在数据之间用&,&有的是用空格，十个数据输入完后才按回车，有的可以输入一个就按回车。
相关知识等待您来回答
编程领域专家