笔试面试中常常会要求应聘者用自己最擅长的语言实现一些基本算法,这种考基本功的问题还是需要认真对待的。很多基本算法虽然表面上思想很简单,但在实现为程序的时候却总是会有很多非常tricky的问题让你阴沟里翻船,要么死循环了,要么数组越界了,要么整数溢出了。所以平时多练练手,在笔试面试的时候可以短时间内正确地实现这些算法,就可以给面试官一个基本功扎实的好印象,还能增加自信心,绝对能给笔试面试加不少分。
下面是刚才花了点时间实现的一些笔试面试中经常会问到的算法,基本都是搜索啊,排序啊,也都非常简单,但是包括写测试代码,查错,修改在内差不多花了我1个小时的时间,中间好几个算法在第一遍写完的时候都出现了各种各样的问题,连选择排序这么简单的我都写错了两次,可见基本功还是不够扎实啊,以后得多练习练习。
下面的实现包括:
排序:冒泡,选择,插入,快排(3个版本)
搜索:二叉搜索(2个版本)
1
#include <iostream>
2
#include <fstream>
3
#include <sstream>
4
#include <string>
5
#include <cmath>
6
#include <iomanip>
7
#include <vector>
8
#include <deque>
9
#include <list>
10
#include <queue>
11
#include <stack>
12
#include <map>
13
#include <algorithm>
14
#include <limits>
15
#include <utility>
16
#include <ctime>
17
#include <bitset>
18
using namespace std;
19
20
//冒泡
21
void bubble_sort(int a[], int n)
22

{
23
for(int i=n-1;i>=0;--i)
24
for(int j=0;j<i;j++)
25
if(a[j]>a[j+1])
26
swap(a[j], a[j+1]);
27
}
28
29
//插入排序
30
void insert_sort(int a[], int n)
31

{
32
for(int i=1;i<n;++i)
33
{
34
int j,x = a[i];
35
for(j=i-1;j>=0;--j)
36
if(a[j]>x)
37
a[j+1]=a[j];
38
else
39
break;
40
41
a[j+1] = x;
42
}
43
}
44
45
//选择排序
46
void select_sort(int a[], int n)
47

{
48
for(int i=0;i<n;++i)
49
{
50
int min = i;
51
for(int j=i+1;j<n;++j)
52
if(a[j]<a[min])
53
min = j;
54
55
swap(a[i], a[min]);
56
}
57
}
58
59
//快排(单向)
60
void quick_sort_1(int a[], int l, int r)
61

{
62
if(l>=r)
63
return;
64
int m=l;
65
for(int i=l+1;i<=r;i++)
66
if(a[i]<a[l])
67
swap(a[++m], a[i]);
68
swap(a[l], a[m]);
69
quick_sort_1(a, l, m-1);
70
quick_sort_1(a, m+1, r);
71
}
72
73
//快排(双向)
74
void quick_sort_2(int a[], int l, int r)
75

{
76
if(l>=r)
77
return;
78
int i=l,j=r+1;
79
while(1)
80
{
81
do i++; while(i<=r && a[i]<a[l]);
82
do j--; while(a[j]>a[l]);
83
if(i>j) break;
84
swap(a[i], a[j]);
85
}
86
swap(a[l], a[j]);
87
quick_sort_2(a, l, j-1);
88
quick_sort_2(a, j+1, r);
89
}
90
91
//在[l,r]中取随机数
92
int rand_int(int l, int r)
93

{
94
srand((unsigned)time(NULL));
95
const float scale = rand()/float(RAND_MAX);//scale in [0,1)
96
int rnd = static_cast<int>(scale*(r-l) + 0.5);//rnd in [0, r-l]
97
return l+rnd;//[l,r]
98
}
99
100
//随机pivot,快排(双向)
101
void quick_sort_3(int a[], int l, int r)
102

{
103
if(l>=r)
104
return;
105
int i=l,j=r+1;
106
swap(a[l], a[rand_int(l,r)]);//randomized
107
while(1)
108
{
109
do i++; while(i<=r && a[i]<a[l]);
110
do j--; while(a[j]>a[l]);
111
if(i>j) break;
112
swap(a[i], a[j]);
113
}
114
swap(a[l], a[j]);
115
quick_sort_2(a, l, j-1);
116
quick_sort_2(a, j+1, r);
117
}
118
119
//二叉搜索
120
int binary_search_1(int a[], int n, int t)
121

{
122
int l=0,r=n-1,m;
123
while(l<=r)
124
{
125
m = (l+r)/2;
126
if(a[m]==t)
127
return m;
128
else if(a[m]<t)
129
l = m+1;
130
else
131
r = m-1;
132
}
133
134
return -1;
135
}
136
137
//返回第一次出现的二叉搜索
138
int binary_search_2(int a[], int n, int t)
139

{
140
int l=-1,r=n,m,res;
141
while(l+1!=r)
142
{
143
m = (l+r)/2;
144
if(a[m]<t)
145
l = m;
146
else
147
r = m;
148
}
149
res = r;
150
if(a[res]!=t || res>=n)
151
res = -1;
152
153
return res;
154
}
155
156
void assign_array(int a1[], int a2[], int n)
157

{
158
for(int i=0;i<n;i++)
159
a1[i] = a2[i];
160
}
161
162
void print_array(int a[], int n)
163

{
164
for(int i=0;i<n;i++)
165
cout<<a[i]<<" ";
166
cout<<endl;
167
}
168
169
int main()
170

{
171
int origin_array[] =
{3,2,6,9,11,2,3,8,4,5,3,8,19,1,11,7};
172
int len = sizeof(origin_array)/sizeof(origin_array[0]);
173
int *test_array = new int[len];
174
175
//测试冒泡
176
assign_array(test_array, origin_array, len);
177
print_array(test_array, len);
178
cout<<"bubble sort"<<endl;
179
bubble_sort(test_array, len);
180
print_array(test_array, len);
181
cout<<endl;
182
183
//测试插入排序
184
assign_array(test_array, origin_array, len);
185
print_array(test_array, len);
186
cout<<"insert sort"<<endl;
187
insert_sort(test_array, len);
188
print_array(test_array, len);
189
cout<<endl;
190
191
192
//测试选择排序
193
assign_array(test_array, origin_array, len);
194
print_array(test_array, len);
195
cout<<"select sort"<<endl;
196
select_sort(test_array, len);
197
print_array(test_array, len);
198
cout<<endl;
199
200
//测试快排(单向)
201
assign_array(test_array, origin_array, len);
202
print_array(test_array, len);
203
cout<<"quick sort 1"<<endl;
204
quick_sort_1(test_array, 0, len-1);
205
print_array(test_array, len);
206
cout<<endl;
207
208
//测试快排(双向)
209
assign_array(test_array, origin_array, len);
210
print_array(test_array, len);
211
cout<<"quick sort 2"<<endl;
212
quick_sort_2(test_array, 0, len-1);
213
print_array(test_array, len);
214
cout<<endl;
215
216
//测试随机快排(双向)
217
assign_array(test_array, origin_array, len);
218
print_array(test_array, len);
219
cout<<"quick sort 3"<<endl;
220
quick_sort_3(test_array, 0, len-1);
221
print_array(test_array, len);
222
cout<<endl;
223
224
int target, loc;
225
cout<<"请输入目标值(crtl-z退出): ";
226
while(cin>>target)
227
{
228
//测试二叉搜索
229
cout<<"binary search 1"<<endl;
230
if((loc=binary_search_1(test_array, len, target))>=0)
231
cout<<"find "<<target<<" at location: "<<loc<<endl;
232
else
233
cout<<target<<" is not in the array"<<endl;
234
235
cout<<"请输入目标值(crtl-z退出): ";
236
}
237
238
//测试返回第一次出现的二叉搜索
239
cin.clear();
240
cout<<"请输入目标值(crtl-z退出): ";
241
while(cin>>target)
242
{
243
cout<<"binary search 2"<<endl;
244
if((loc=binary_search_2(test_array, len, target))>=0)
245
cout<<"find first "<<target<<" at location: "<<loc<<endl;
246
else
247
cout<<target<<" is not in the array"<<endl;
248
249
cout<<"请输入目标值(crtl-z退出): ";
250
}
251
252
return 0;
253
}
下次有时间再练练归并,堆排序,基数排序,BFS,DFS啥的