#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ARRAYSIZE 50 /*数组长度 */
//顺序查找算法
int SeqSearch(int r[ ], int n, int k)
//数组r[1] ~ r[n]存放查找集合
{ int i;
r[0]=k; i=n;
while (r[i]!=k)
i --;
return i;
}
//希尔排序算法
void shellSort (int r[ ], int n)
{ int i,j,d;
for (d=n/2; d>=1; d=d/2)
{
for (i=d+1; i<=n; i++) //将r[i]插入到所属的子序列中
{
r[0]=r[i]; //暂存待插入记录
j=i-d; //j指向所属子序列的最后一个记录
while (j>0 && r[0]<r[j])
{
r[j+d]=r[j]; //记录后移d个位置
j=j-d; //比较同一子序列的前一个记录
}
r[j+d]=r[0];
}
displayArray(r,n); //调试用,便于查看中间结果
}
}
//折半查找——非递归算法
int BinSearch1(int r[], int n, int k)
//数组r[1] ~ r[n]存放查找集合
{ int low,high,mid;
low=1; high=n;
while (low<=high)
{
mid=(low+high)/2;
if (k<r[mid]) high=mid-1;
else if (k>r[mid]) low=mid+1;
else return mid;
}
return 0;
}
//折半查找——递归算法
int BinSearch2(int r[ ], int low, int high, int k)
//数组r[1] ~ r[n]存放查找集合
{ int mid;
if (low>high) return 0;
else {
mid=(low+high)/2;
if (k<r[mid])
return BinSearch2(r, low, mid-1, k);
else if (k>r[mid])
return BinSearch2(r, mid+1, high, k);
else return mid;
}
}