1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
| #include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ARRSIZE(arr) (sizeof(arr) / sizeof(arr[0]))
#define SEGMENT_COUNT 5 //划分成多少段
typedef struct Segment
{
int start; //当前段在序列中的起始位置
int end; //结束位置
int max; //当前段的最大值,这个也是排序关键字
} Segment;
//获取区间中的最大值
int getMaxInRange(int elements[], int start, int end)
{
int max = elements[start];
for (int i = start; i < end; i++)
{
if (max < elements[i])
max = elements[i];
}
return max;
}
//顺序查找
int SequentialSearch(int elements[], int len, int key)
{
for (int i = 0; i < len; i++)
if (key == elements[i])
{
return i;
}
return -1;
}
//折半查找(二分查找)
int BinarySearch(int elements[], int len, int key)
{
int mid = -1; //中间值
int low = 0; //下界
int high = len - 1; //上界
while (low <= high)
{
mid = (high + low) / 2;
if (elements[mid] == key)
{
return mid;
}
else if (elements[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
//分块查找
int SegmentSearch(int elements[], int len, int key)
{
int i, j, index = -1;
//生成SEGMENT_COUNT个段
Segment *segments = (Segment *)malloc(sizeof(Segment) * SEGMENT_COUNT);
int num = len / SEGMENT_COUNT; //每段多少个元素
for (i = 0; i < SEGMENT_COUNT; i++)
{
segments[i].start = i * num;
segments[i].end = segments[i].start + num;
segments[i].max = getMaxInRange(elements, segments[i].start, segments[i].end);
}
//插入排序，根据max对段进行排序
for (i = 1; i < SEGMENT_COUNT; i++)
{
Segment tmp = segments[i];
for (j = i; j > 0 && segments[j - 1].max > tmp.max; j--)
{
segments[j].max = segments[j - 1].max;
segments[j].start = segments[j - 1].start;
segments[j].end = segments[j - 1].end;
}
segments[j].max = tmp.max;
segments[j].start = tmp.start;
segments[j].end = tmp.end;
}
//查找key在哪个段中(查找max比key大的段)
for (i = 0; segments[i].max < key && i < SEGMENT_COUNT; i++)
{
}
//i不能越界，越界表示各个段中都不存在key
if (i < SEGMENT_COUNT)
{
//对目标段中的元素进行顺序查找
for (j = segments[i].start; j < segments[i].end; j++)
{
if (key == elements[j])
{
index = j;
break;
}
}
}
return index;
}
int main(int argc, char const *argv[])
{
int len = 100;
int elems[len];
int i, j;
//产生len个有序的数
for (i = 0; i < len; i++)
{
elems[i] = 10 + i * 3;
}
//随机选中一个数进行查找
srand((unsigned)time(NULL));
i = rand() % 100;
int v = elems[i];
printf("三种静态查找 : elements[%d]=%d 的元素\n", i, v);
j = SequentialSearch(elems, len, v);
printf("顺序查找 : elements[%d]=%d\n", j, elems[j]);
j = BinarySearch(elems, len, v);
printf("二分查找 : elements[%d]=%d\n", j, elems[j]);
j = SegmentSearch(elems, len, v);
printf("分块查找 : elements[%d]=%d\n", j, elems[j]);
return 0;
}
|