分块查找(C语言)

i=idx[low1].low是块中第一个元素的起始位置的值

int blksearch(sqlist r,index idx,find=0,hb) // bn为块个数 //

{ int i,low=1,high1=bn,midl,find=0,hb

while(low1<=high1&&!find)

{mid=(low1+high1)/2

if(k<idx[mid1].key)high1=mid-1

else if(k>idx[mid1],key)low1=mid1+1

else{

low=mid1

find=1

}

到这里是初步锁定要查的元素在那个块，找到大的方向后 在块里进行进一步的搜索

if(low1<bn)//如果low1的值没有超过块的总个数

i=idx[low1].low//i赋值为该块内第一个元素的起始位置

然后进一步查到元素

索引表里存放相应块的最大关键字，比如放了5,13,56,98，你要查找42,从左开始，先是5，5<42，所以42肯定不在这块，再是13，13<42，也不在这块，再是56,56>42，所以42可能就在56这块了。

一.冒泡

1

Void Bubble Sort (int* pData,int Count)

{

Int iTemp

for(int i=1i<Counti++)

{

For (int j=Count-1j>=ij--)

{

if(pData[j]<pData[j-1])

{

iTemp = pData[j-1]

pData[j-1] = pData[j]

pData[j] = iTemp

}

}

}

}

优化

void Bubble2Sort(int* pData,int Count)

{

int iTemp

int left = 1

int right =Count -1

int t

do

{

//正向的部分

for(int i=righti>=lefti--)

{

if(pData[i]<pData[i-1])

{

iTemp = pData[i]

pData[i] = pData[i-1]

pData[i-1] = iTemp

t = i

}

}

left = t+1

//反向的部分

for(i=lefti<right+1i++)

{

if(pData[i]<pData[i-1])

{

iTemp = pData[i]

pData[i] = pData[i-1]

pData[i-1] = iTemp

t = i

}

}

right = t-1

}while(left<=right)

}

二。C

1

//分块查找的前提是,数组有序

#include<stdio.h>

int A[10]={1,2,3,4,5,6,7,8,9,10}

int BinSearchHigh( int *array, int key, int low, int high)

{

int mid = 0

while(low < high)

{

mid = (low + high) / 2 /*取数组的中间*/

if(array[mid] == key) /*若找到则返回8?

{

return mid

}

if(array[mid]> key) /*若中间的数比key大,则从low--mid间找*/

{

high=mid

}

if(array[mid] < key) /*若中间的数比key小,则从mid--high间找*/

{

low=mid

}

}

return (-1) /*若没有找到，返回-1 */

}

int main()

{

int j=0

j=BinSearchHigh(A,3,0,9) /*在数组范围0--9间找3*/

if(j!=-1) /*若找到*/

printf("%d",j)

return 0

}

2

#include<stdio.h>

int A[10]={1,2,3,4,5,6,7,8,9,10}

int BinSearchHigh( int *array, int key, int low, int high)

{

int mid = 0

while(low < high)

{

mid = (low + high) / 2 /*取数组的中间*/

if(array[mid] == key) /*若找到则返回*/

{

return mid+1

}

else if(array[mid]> key) /*若中间的数比key大,则从low--mid间找*/

{

high=mid+1

}

else /*若中间的数比key小,则从mid--high间找*/

{

low=mid-1

}

}

return (-1) /*若没有找到，返回-1 */

}

int main()

{

int i,j=0

printf("please input the num you want to find(1-10):")

scanf("%d",&i)

j=BinSearchHigh(A,i-1,0,9) /*在数组范围0--9间找3*/

if(j!=-1) /*若找到*/

printf("the num you find in position %d\n.",j)

return 0

}

---