筆試面試中常常會(huì)要求應(yīng)聘者用自己最擅長(zhǎng)的語言實(shí)現(xiàn)一些基本算法，這種考基本功的問題還是需要認(rèn)真對(duì)待的。很多基本算法雖然表面上思想很簡(jiǎn)單，但在實(shí)現(xiàn)為程序的時(shí)候卻總是會(huì)有很多非常tricky的問題讓你陰溝里翻船，要么死循環(huán)了，要么數(shù)組越界了，要么整數(shù)溢出了。所以平時(shí)多練練手，在筆試面試的時(shí)候可以短時(shí)間內(nèi)正確地實(shí)現(xiàn)這些算法，就可以給面試官一個(gè)基本功扎實(shí)的好印象，還能增加自信心，絕對(duì)能給筆試面試加不少分。
下面是剛才花了點(diǎn)時(shí)間實(shí)現(xiàn)的一些筆試面試中經(jīng)常會(huì)問到的算法，基本都是搜索啊，排序啊，也都非常簡(jiǎn)單，但是包括寫測(cè)試代碼，查錯(cuò)，修改在內(nèi)差不多花了我1個(gè)小時(shí)的時(shí)間，中間好幾個(gè)算法在第一遍寫完的時(shí)候都出現(xiàn)了各種各樣的問題，連選擇排序這么簡(jiǎn)單的我都寫錯(cuò)了兩次，可見基本功還是不夠扎實(shí)啊，以后得多練習(xí)練習(xí)。
下面的實(shí)現(xiàn)包括：
排序：冒泡，選擇，插入，快排(3個(gè)版本)
搜索：二叉搜索(2個(gè)版本)
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]中取隨機(jī)數(shù)
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//隨機(jī)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//返回第一次出現(xiàn)的二叉搜索
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 //測(cè)試冒泡
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 //測(cè)試插入排序
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 //測(cè)試選擇排序
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 //測(cè)試快排(單向)
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 //測(cè)試快排(雙向)
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 //測(cè)試隨機(jī)快排(雙向)
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<<"請(qǐng)輸入目標(biāo)值(crtl-z退出): ";
226 while(cin>>target)
227 {
228 //測(cè)試二叉搜索
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<<"請(qǐng)輸入目標(biāo)值(crtl-z退出): ";
236 }
237
238 //測(cè)試返回第一次出現(xiàn)的二叉搜索
239 cin.clear();
240 cout<<"請(qǐng)輸入目標(biāo)值(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<<"請(qǐng)輸入目標(biāo)值(crtl-z退出): ";
250 }
251
252 return 0;
253}
下次有時(shí)間再練練歸并，堆排序，基數(shù)排序，BFS，DFS啥的