筆試面試中常常會要求應聘者用自己最擅長的語言實現一些基本算法，這種考基本功的問題還是需要認真對待的。很多基本算法雖然表面上思想很簡單，但在實現為程序的時候卻總是會有很多非常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啥的