分块查找基本思想是什么 冒泡法把一维数组从小到大排序
如何用C++描述分块查找的算法？数据结构和计算机相关的问题，数组的冒泡排序和分块查找法，http://www.baidu .com/，分块查找的基本思想是什么？什么是折半查找法？
本文导航
c加加里面的算法
template<class Type>
int BinarySearch(Type a[],const Type& x,int n)
{
int left=0;
int right=n-1;
while(left<=right){
int middle=(left+right)/2;
if (x==a[middle]) return middle;
if (x>a[middle]) left=middle+1;
else right=middle-1;
}
return -1;
}
模板函数BinarySearch在a[0]<=a[1]<=...<=a[n-1]共n个升序排列的元素中搜索x,找到x时返回其在数组中的位置，否则返回-1。容易看出，每执行一次while循环，待搜索数组的大小减少一半,因此整个算法在最坏情况下的时间复杂度为O(log n)。在数据量很大的时候，它的线性查找在时间复杂度上的优劣一目了然。
选择排序
基本思想是：每次选出第i小的记录，放在第i个位置（i的起点是0，按此说法，第0小的记录实际上就是最小的，有点别扭，不管这么多了）。当i＝N－1时就排完了。
直接选择排序
直选排序简单的再现了选择排序的基本思想，第一次寻找最小元素的代价是O(n)，如果不做某种特殊处理，每次都使用最简单的寻找方法，自然的整个排序的时间复杂度就是O(n2)了。
冒泡法
为了在a[1]中得到最大值，我们将a[1]与它后面的元素a[2]，a[3]，...，a[10]进行比较。首先比较a[1]与a[2]，如果a[1]<a[2]，则将a[1]与a[2]交换，否则不交换。这样在a[1]中得到的是a[1]与a[2]中的大数。然后将a[1]与a[3]比较，如果a[1]<a[3]，则将a[1]与a[3]交换，否则不交换。这样在a[1]中得到的是a[1]，a[2]，a[3]中的最大值，...。如此继续，最后a[1]与a[10]比较，如果a[1]<a[10]，则将a[1]与a[10]交换，否则不交换。这样在a[1]中得到的数就是数组a的最大值（一共进行了9次比较）。
为了在a[2]中得到次大值，应将a[2]与它后面的元素a[3]，a[4]，...，a[10]进行比较。这样经过8次比较，在a[2]是将得到次大值。
如此继续，直到最后a[9]与a[10]比较，将大数放于a[9]，小数放于a[10]，全部排序到此结束。
从上面可以看出，对于10个数，需进行9趟比较，每一趟的比较次数是不一样的。第一趟需比较9次，第二趟比较8次，...，最后一趟比较1次。
以上数组元素的排序，用二重循环实现，外循环变量设为i，内循环变量设为j。外循环重复9次，内循环依次重复9，8，...，1次。每次进行比较的两个元素，第一个元素与外循环i有关的，用a[i]标识，第二个元素是与内循环j有关的，用a[j]标识，i的值依次为1,2,...,9，对于每一个i, j的值依次为i+1,i+2,...。
计算机的核心是算法和数据结构
1.数据元素：是数据的基本单位，它在计算机处理和程序设计中通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成。
2.栈（stack）在计算机科学中是限定仅在表尾进行插入或删除操作的线形表。
栈是一种数据结构，它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。
栈是只能在某一端插入和删除的特殊线性表。用桶堆积物品，先堆进来的压在底下，随后一件一件往堆。取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是不动的。
栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（PUSH），删除则称为退栈（POP）。 栈也称为后进先出表（LIFO表）。
3.线性表是由n（n≥0）个数据元素（结点）a[0]，a[1]，a[2]…，a[n-1]组成的有限序列。
4.队列的操作原则是先进先出
5.并发进程间的关系：并发进程相互之间可能是 无关的 ，也可能是 交往的 .如果一个进程的执行不影响其他进程的执行，且与其他进程的进展情况无关，即它们是各自独立的，则这些并发进程相互之间是无关的。如果一个进程的执行依赖其他进程的执行，则这些并发进程之间是有交往的。
6.算法设计的基本方法:列举法 枚举归纳法 递推法 递归法 减半递推技术 回溯法 数值法
7.数据结构分为哪几大类:通常有下列四类基本的结构：
⑴集合结构。该结构的数据元素间的关系是“属于同一个集合”。
⑵线性结构。该结构的数据元素之间存在着一对一的关系。
⑶树型结构。该结构的数据元素之间存在着一对多的关系。
⑷图形结构。该结构的数据元素之间存在着多对多的关系，也称网状结构。
8.对于一个顺寻战来说,战空 战满的条件:栈空的条件是st->top=0,栈满的条件是st->top==maxlen
9.N/2
10.进程死锁的4个表要条件
（1） 互斥条件：一个资源每次只能被一个进程使用。
（2） 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
（3） 不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。
（4） 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。
11.操作系统的典型类型 3个:
批处理操作系统
分时操作系统
实时操作系统
12.进程的3中基本:就绪，阻塞，运行
13.算法的概念和特征:
算法（Algorithm）是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。
一个算法应该具有以下五个重要的特征：
1、有穷性2、确切性3、输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；
4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
5、可行性
14.数据结构的概念:数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
15.什么是数据的存储结构:存储结构是指一个数据集合在计算机内存里是怎么样存储的.或者说在内存里怎么给一群数据分配内存.
16.查找的概念以及典型的算法:给定一个值K，在含有n个结点的表中找出关键字等于给定值K的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置;否则查找失败，返回相关的指示信息。顺序查找 二分查找
分块查找 哈希表查找
17.操作系统的功能:
作业管理(Job Management)
进程管理(Process Management)
存储管理(Memory Management)
设备管理(Device Management)
文件管理(File Management)
18.递归算法思路:一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。
19.数据的逻辑结构:简单说,数据的逻辑结构就是数据之间关系,如顺序关系,隶属关系等.
20.队列的概念:队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表
21.进程的概念:进程是一个具有独立功能的程序关于某个数据集合的一次运行活动。它可以申请和拥有系统资源，是一个动态的概念，是一个活动的实体。它不只是程序的代码，还包括当前的活动，通过程序计数器的值和处理寄存器的内容来表示。
22.二叉树的先序、中序和后续:NLR：前序遍历(PreorderTraversal亦称(先序遍历))访问结点的操作发生在遍历其左右子树之前。
② LNR：中序遍历(InorderTraversal)访问结点的操作发生在遍历其左右子树之中(间)。
③ LRN：后序遍历(PostorderTraversal)访问结点的操作发生在遍历其左右子树之后。
23.快速排序:快速排序对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
冒泡法把一维数组从小到大排序
#include<iostream.h>
const int N=12,M=3;
void numbers (int a[]) //输入数组元素
{
cout<<"请输入"<<N<<"个元素"<<endl;
for(int i=0;i<N;i++)
cin>>a;
}
void sort(int a[],int n) //冒泡法排序
{
int t;
for(int i=0;i<n-1;i++)
for(int j=0;j<n-1-i;j++)
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
void search(int a[]) //分块查找法
{
int x,j,i;
cout<<"请输入要查找的元素"<<endl;
cin>>x;
int b[N][2];
for(j=0,i=3;j<3,i<12;j++,i+=4)
b[j][0]=a;
for(j=0,i=0;j<3,i<12;j++,i+=4)
b[j][1]=i;
for(j=0;j<3;j++)
{
if(x<=b[j][0])
break;
}
if(x>a[N-1])
{
cout<<x<<" "<<"不在您要查找的数组中"<<endl;
return;
}
{
int top=b[j][1],bottom=b[j][1]+N/M-1,middle=(top+bottom)/2; //折半查找法
while(top<=bottom)
{
if(x==a[middle])
break;
else if(x>a[middle])
top=middle+1;
else
bottom=middle-1;
middle=(top+bottom)/2;
}
if(x==a[middle])
{
cout<<x<<" "<<"在您要查找的数组中"<<endl;
}
else
{
cout<<x<<" "<<"不在您要查找的数组中"<<endl;
}
}
}
百度账号的头像
们我现在有一个C++作业题不会做，特向你们求助，恳请你们能给我些帮助！！！下面是问题的题目及要求，谢谢你的帮助！
一、题目：用分块查找方法解决在数据库中查找与关键字相同记录的问题
1． 基本要求：
（1）要求用C++模块化设计的思想来完成程序的设计；
（2）要求各个功能分别使用函数来完成，主函数和各个函数分别存放在不同的.cpp文件中，要求使用头文件；
（3）程序调试通过后，完成程序文档的处理，加必要的注释。
三、设计方法和基本原理
1． 问题描述：
在一组无序数列中查找某个数据，找到则输出该数据，否则输出未找到信息。
2． 问题的解决方案：
根据问题的描述，可以按照要求的功能采用结构化的设计思想。
（1） 数列的赋值要求编写独立函数实现；
（2） 将无序数列排序为有序数列可以用“拉锯法”排序法也可以用其他方法实现，并编写独立函数；
（3） 分块查找的算法用独立函数实现
四、主要技术问题的描述
根据三的分析，主要问题在于：
1、排序算法的实现（不限方法）
2、分块查找方法的实现
分块查找又索引查找，它主要用于“分块有序”表的查找。所谓“分块有序”是指将线性表L（一维数组）分成m个子表（要求每个子表的长度相等），且第i+1个子表中的每一个项目均大于第i个子表中的所有项目。“分块有序”表应该包括线性表L本身和分块的索引表A。因此，分块查找的关键在于建立索引表A。
（1）建立索引表A（二维数组）
索引表包括两部分：关键字项（子表中的最大值）和指针项（子表的第一项在线性表L中位置）
索引表按关键字有序的。
例如：线性表L（有序）为：1 2 3 4 5 6 7 8 9 10 11 12
分成m=3个子表：{1 2 3 4} {5 6 7 8} {9 10 11 12}
索引表A：二维数组：第一列为每个子表的最大值 ，第二列为每个子表的起始地址
即： 4 0
8 4
12 8
分块查找技巧口诀
前提条件 块内无序块间有序
方法二分查找块间 顺序查找块内
折半查找算法经典例题及答案
折半查找法是效率较高的一种查找方法，假设有已经按照从小到大的顺序排列好的五个整数a0~a4，要查找的数是X，其基本思想是：
设查找数据的范围下限为l=0，上限为h=4，求中点m=（l+h）/2，用X与中点元素am比较，若X等于am，即找到，停止查找。
否则，若X大于am，替换下限l=m+1，到下半段继续查找。
若X小于am，换上限h=m-1，到上半段继续查找，如此重复前面的过程直到找到或者l>h为止。
如果l>h，说明没有此数，打印找不到信息，程序结束。
该方法是查找的范围不断缩小一半，所以查找效率较高。
扩展资料
折半查找法优缺点
Bentley在自己的著作《Writing Correct Programs》中写道，90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。
问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定，正确地归纳奇偶数的各种情况，其实整理后可以发现它的具体算法是很直观的。
折半查找法的优点是比较次数少，查找速度快，平均性能好。
其缺点是要求待查表为有序表，且插入删除困难，因此折半查找方法适用于不经常变动而查找频繁的有序列表。
参考资料来源：百度百科-折半查找法
