笔试面试中常常会要求应聘者用自己最擅长的语言实现一些基本算法，这种考基本功的问题还是需要认真对待的。很多基本算法虽然表面上思想很简单，但在实现为程序的时候却总是会有很多非常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>
18using namespace std;
19
20//冒泡
21void 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//插入排序
30void 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//选择排序
46void 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//快排(单向)
60void 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//快排(双向)
74void 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]中取随机数
92int 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，快排(双向)
101void 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//二叉搜索
120int 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//返回第一次出现的二叉搜索
138int 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
156void assign_array(int a1[], int a2[], int n)
157{
158 for(int i=0;i<n;i++)
159 a1[i] = a2[i];
160}
161
162void print_array(int a[], int n)
163{
164 for(int i=0;i<n;i++)
165 cout<<a[i]<<" ";
166 cout<<endl;
167}
168
169int 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啥的