急!Pascal顺序和二分法查找的程序
顺序查找的程序简单,用于未经排序的数组也只能用这个办法。
二分法用于已经过排序的数组,速度会快些(平均而言),程序略微复杂,原理是把待查数据和数组的中间的元素做比较,如果小于数组目前的元素,则排除后半部的元素,只留下钱半部的元素继续用二分法来查找,如果大于,则相反,只查找后半部的元素,这是升序的情况,如果数组时反序,则前后排除原则正好相反
直接插入排序、二分法插入排序、希尔排序、直接选择排序、堆排序、交换排序、快速排序英文怎么说?
直接插入排序:Straight Insertion Sort
二分法插入排序: Binary Sort
希尔排序:Shell Sort
直接选择排序:Straight Select Sort
堆排序:Heap Sort
交换排序:Swap Sort
快速排序:Quick Sort
基数排序:Radix Sort
归并排序:Merge sort
excel中lookup,关于二分法。
二分法查找
算法:当数据量很大适宜采用该方法。
采用二分法查找时,数据需是排好序的。
基本思想:假设数据是按升序排序的,对于给定值x,从序列的中间位置开始比较,如果当前位置值等于x,则查找成功;若x小于当前位置值,则在数列的前半段中查找;若x大于当前位置值则在数列的后半段中继续查找,直到找到为止。
本例中2,8,4,5,6未排序,因此给出了末位的6;如果写成=LOOKUP(9,{2,4,5,6,8}),结果是8。
二分法排序的程序填空
/*magipan正解*/
/*其实这就是折半插入排序,只是未新开辟空间的插入排序
起始认为第一个元素是有序的(一个元素当然是有序的。
。
。
)
然后一个一个的折半插入已经排序好的有序序列。
low指向的是已排序好的序列的第一个元素,high指向的是已排序好的序列最后一个元素*/
#include <stdio.h>
int a[]={15,7,15,6,4,3,4,6,7};
main()
{
int i,j,k,low,high,mid,t;
for(i=k=1;i<sizeof a/sizeof a[0];i++)//起始认为第一个元素是有序的,high=low=k-1=0,所以k=1,
{
low=0;
high=k-1;
while(low<=high)////折半查找时,low与high相遇,则找到插入位置
{
mid=(low+high)/2;
if(a[mid]>=a[i])high=mid-1;///////元素比mid小,因此在low到mid-1范围内搜索位置
else low=mid+1;
}
if(high<i|| a[low]!=a[i]) ///////////
{
t=a[i];
for(j=k-1;j>=low;j--) //////插入位置是low,所以low到high=k-1范围内的元素都要向后移动
a[j+1]=a[j];
a[low]=t; //////////////low被赋值为已经被覆盖掉的a[i]
k++;
}
}
for(j=0;j<k;j++)
printf("%4d",a[j]);
printf("
");
}
c++对9,1,8,2,7,3,6,4,5用二分法 排序成升序!求写法!求高人指教!~
快速排序法(即是二分排序)的思想是,找到一个值,要求这个值的左边都是小于等于这个值的,右边则大于等于这个值。
例如: int a[9]={9,1,8,2,7,3,6,4,5}
一步步演示如下:
设3个变量,i=0,j=8,fence=8 (都是下标)
i表示左边开始的元素9的下标,j表示最右边的元素5的下标,fence表示中间值的下标,初始为最右,即8。
运作的时候i会往右靠,j会往左靠。
我们的目标是给数值5找一个合适的位置,让它满足上述条件。
1.i从0开始递增,每个数都和5比较,如果找到一个比5大的数,则和5交换位置。
同时更新fence和i
执行后:a[9]={5,1,8,2,7,3,6,4,9} i = 1; fence = 0; (记住fence总是指示5所指的位置。
)
2.j从8开始递减,每个数都和5比较,如果找到一个比5小的数,则和5交换位置。
更新fence 和j
执行后:a[9]={4,1,8,2,7,3,6,5,9} j = 6; fence =7;
3.执行1的步骤:
执行后:a[9]={4,1,5,2,7,3,6,8,9} i =3 ; fence =2;
4.执行2的步骤
执行后:a[9]={4,1,3,2,7,5,6,8,9} j = 4 fence =5;
5.执行后a[9]={4,1,3,2,5,7,6,8,9} i = 5 fence =4;
至此判断 i已经大于j 中断循环 返回 fence的值,
那么经过一次排序后的结果就是a[9]={4,1,3,2,5,7,6,8,9}
5是选择的中间值,排在下标为4的位置
那么用递归对 下标为0到3,下标为5 到8 分别执行同样的排序就可以了。
这就是二分法的思想,即是快速排序。
代码如下:
#include
#include
int partition(int *a, int l, int r){
int fence = r;
--r;
while(l<=r)
{
while(l<=r)
{
if(a[l]>a[fence])
{
std::swap(a[l],a[fence]);
fence = l;
++l;
break;
}
++l;
}
while(l<=r)
{
if(a[r]请问怎么用二分法查找一个数,数组已排序int binarysearch(int a[],int x,int n)
{
int left,right,middle;
left=0;
right=n-1;
while(left<=right)
{
middle=(left+right)/2;
if(x==a[middle])
return middle;
if(x>a[middle])
left=middle+1;
else right=middle-1;
}
return -1;
}
引自:/blogview.asp?logID=77