C++实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等

这篇文章主要介绍了C++如何实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序 、快速排序、归并排序、堆排序和LST基数排序,需要的朋友可以参考下

本文实现了八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序 、快速排序、归并排序、堆排序和LST基数排序

算法实现文件Sort.h

首先是，代码如下：

1. /*  
2. * 实现了八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序  
3. * 以及快速排序、归并排序、堆排序和LST基数排序  
4. * @author gkh178  
5. */ 
6. #include <iostream>  
7.  
8. template<class T>  
9. void swap_value(T &a, T &b)  
10. {  
11. T temp = a;  
12. a = b;  
13. b = temp;  
14. }  
15.  
16. //插入排序：时间复杂度o(n^2)  
17. template<class T>  
18. void insert_sort(T a[], int n)  
19. {  
20. for (int i = 1; i < n; ++i)  
21. {  
22. T temp = a[i];  
23. int j = i - 1;  
24. while (j >= 0 && a[j] > temp)  
25. {  
26. a[j + 1] = a[j];  
27. --j;  
28. }  
29. a[j + 1] = temp;  
30. }  
31. }  
32.  
33. //冒泡排序：时间复杂度o(n^2)  
34. template<class T>  
35. void bubble_sort(T a[], int n)  
36. {  
37. for (int i = n - 1; i > 0; --i)  
38. {  
39. for (int j = 0; j < i; ++j)  
40. {  
41. if (a[j] > a[j + 1])  
42. {  
43. swap_value(a[j], a[j + 1]);  
44. }  
45. }  
46. }  
47. }  
48.  
49. //选择排序：时间复杂度o(n^2)  
50. template<class T>  
51. void select_sort(T a[], int n)  
52. {  
53. for (int i = 0; i < n - 1; ++i)  
54. {  
55. T min = a[i];  
56. int index = i;  
57. for (int j = i + 1; j < n; ++j)  
58. {  
59. if (a[j] < min)  
60. {  
61. min = a[j];  
62. index = j;  
63. }  
64. }  
65. a[index] = a[i];  
66. a[i] = min;  
67. }  
68. }  
69.  
70. //希尔排序：时间复杂度介于o(n^2)和o(nlgn)之间  
71. template<class T>  
72. void shell_sort(T a[], int n)  
73. {  
74. for (int gap = n / 2; gap >= 1; gap /= 2)  
75. {  
76. for (int i = gap; i < n; ++i)  
77. {  
78. T temp = a[i];  
79. int j = i - gap;  
80. while (j >= 0 && a[j] > temp)  
81. {  
82. a[j + gap] = a[j];  
83. j -= gap;  
84. }  
85. a[j + gap] = temp;  
86. }  
87. }  
88. }  
89.  
90. //快速排序：时间复杂度o(nlgn)  
91. template<class T>  
92. void quick_sort(T a[], int n)  
93. {  
94. _quick_sort(a, 0, n - 1);  
95. }  
96. template<class T>  
97. void _quick_sort(T a[], int left, int right)  
98. {  
99. if (left < right)  
100. {  
101. int q = _partition(a, left, right);  
102. _quick_sort(a, left, q - 1);  
103. _quick_sort(a, q + 1, right);  
104. }  
105. }  
106. template<class T>  
107. int _partition(T a[], int left, int right)  
108. {  
109. T pivot = a[left];  
110. while (left < right)  
111. {  
112. while (left < right && a[right] >= pivot)  
113. {  
114. --right;  
115. }  
116. a[left] = a[right];  
117. while (left < right && a[left] <= pivot)  
118. {  
119. ++left;  
120. }  
121. a[right] = a[left];  
122. }  
123. a[left] = pivot;  
124. return left;  
125. }  
126.  
127. //归并排序：时间复杂度o(nlgn)  
128. template<class T>  
129. void merge_sort(T a[], int n)  
130. {  
131. _merge_sort(a, 0, n - 1);  
132. }  
133. template<class T>  
134. void _merge_sort(T a[], int left, int right)  
135. {  
136. if (left < right)  
137. {  
138. int mid = left + (right - left) / 2;  
139. _merge_sort(a, left, mid);  
140. _merge_sort(a, mid + 1, right);  
141. _merge(a, left, mid, right);  
142. }  
143. }  
144. template<class T>  
145. void _merge(T a[], int left, int mid, int right)  
146. {  
147. int length = right - left + 1;  
148. T *newA = new T[length];  
149. for (int i = 0, j = left; i <= length - 1; ++i, ++j)  
150. {  
151. *(newA + i) = a[j];  
152. }  
153. int i = 0;  
154. int j = mid - left + 1;  
155. int k = left;  
156. for (; i <= mid - left && j <= length - 1; ++k)  
157. {  
158. if (*(newA + i) < *(newA + j))  
159. {  
160. a[k] = *(newA + i);  
161. ++i;  
162. }  
163. else 
164. {  
165. a[k] = *(newA + j);  
166. ++j;  
167. }  
168. }  
169. while (i <= mid - left)  
170. {  
171. a[k++] = *(newA + i);  
172. ++i;  
173. }  
174. while (j <= right - left)  
175. {  
176. a[k++] = *(newA + j);  
177. ++j;  
178. }  
179. delete newA;  
180. }  
181.  
182. //堆排序：时间复杂度o(nlgn)  
183. template<class T>  
184. void heap_sort(T a[], int n)  
185. {  
186. built_max_heap(a, n);//建立初始大根堆  
187. //交换首尾元素，并对交换后排除尾元素的数组进行一次上调整  
188. for (int i = n - 1; i >= 1; --i)  
189. {  
190. swap_value(a[0], a[i]);  
191. up_adjust(a, i);  
192. }  
193. }  
194. //建立一个长度为n的大根堆  
195. template<class T>  
196. void built_max_heap(T a[], int n)  
197. {  
198. up_adjust(a, n);  
199. }  
200. //对长度为n的数组进行一次上调整  
201. template<class T>  
202. void up_adjust(T a[], int n)  
203. {  
204. //对每个带有子女节点的元素遍历处理，从后到根节点位置  
205. for (int i = n / 2; i >= 1; --i)  
206. {  
207. adjust_node(a, n, i);  
208. }  
209. }  
210. //调整序号为i的节点的值  
211. template<class T>  
212. void adjust_node(T a[], int n, int i)  
213. {  
214. //节点有左右孩子  
215. if (2 * i + 1 <= n)  
216. {  
217. //右孩子的值大于节点的值，交换它们  
218. if (a[2 * i] > a[i - 1])  
219. {  
220. swap_value(a[2 * i], a[i - 1]);  
221. }  
222. //左孩子的值大于节点的值，交换它们  
223. if (a[2 * i - 1] > a[i - 1])  
224. {  
225. swap_value(a[2 * i - 1], a[i - 1]);  
226. }  
227. //对节点的左右孩子的根节点进行调整  
228. adjust_node(a, n, 2 * i);  
229. adjust_node(a, n, 2 * i + 1);  
230. }  
231. //节点只有左孩子，为最后一个有左右孩子的节点  
232. else if (2 * i == n)  
233. {  
234. //左孩子的值大于节点的值，交换它们  
235. if (a[2 * i - 1] > a[i - 1])  
236. {  
237. swap_value(a[2 * i - 1], a[i - 1]);  
238. }  
239. }  
240. }  
241.  
242. //基数排序的时间复杂度为o(distance(n+radix)),distance为位数，n为数组个数，radix为基数  
243. //本方法是用LST方法进行基数排序，MST方法不包含在内  
244. //其中参数radix为基数，一般为10；distance表示待排序的数组的数字最长的位数；n为数组的长度  
245. template<class T>  
246. void lst_radix_sort(T a[], int n, int radix, int distance)  
247. {  
248. T* newA = new T[n];//用于暂存数组  
249. int* count = new int[radix];//用于计数排序，保存的是当前位的值为0 到 radix-1的元素出现的的个数  
250. int divide = 1;  
251. //从倒数第一位处理到第一位  
252. for (int i = 0; i < distance; ++i)  
253. {  
254. //待排数组拷贝到newA数组中  
255. for (int j = 0; j < n; ++j)  
256. {  
257. *(newA + j) = a[j];  
258. }  
259. //将计数数组置0  
260. for (int j = 0; j < radix; ++j)  
261. {  
262. *(count + j) = 0;  
263. }  
264. for (int j = 0; j < n; ++j)  
265. {  
266. int radixKey = (*(newA + j) / divide) % radix; //得到数组元素的当前处理位的值  
267. (*(count + radixKey))++;  
268. }  
269. //此时count[]中每个元素保存的是radixKey位出现的次数  
270. //计算每个radixKey在数组中的结束位置，位置序号范围为1-n  
271. for (int j = 1; j < radix; ++j)  
272. {  
273. *(count + j) = *(count + j) + *(count + j - 1);  
274. }  
275. //运用计数排序的原理实现一次排序，排序后的数组输出到a[]  
276. for (int j = n - 1; j >= 0; --j)  
277. {  
278. int radixKey = (*(newA + j) / divide) % radix;  
279. a[*(count + radixKey) - 1] = newA[j];  
280. --(*(count + radixKey));  
281. }  
282. divide = divide * radix;  
283. }  
284. }  

测试文件main.cpp

然后是，代码如下：

1. #include "Sort.h"  
2. using namespace std;  
3.  
4. template<class T>  
5. void printArray(T a[], int n)  
6. {  
7. for (int i = 0; i < n; ++i)  
8. {  
9. cout << a[i] << " ";  
10. }  
11. cout << endl;  
12. }  
13.  
14. int main()  
15. {  
16. for (int i = 1; i <= 8; ++i)  
17. {  
18. int arr[] = { 45, 38, 26, 77, 128, 38, 25, 444, 61, 153, 9999, 1012, 43, 128 };  
19. switch (i)  
20. {  
21. case 1:  
22. insert_sort(arr, sizeof(arr) / sizeof(arr[0]));  
23. break;  
24. case 2:  
25. bubble_sort(arr, sizeof(arr) / sizeof(arr[0]));  
26. break;  
27. case 3:  
28. select_sort(arr, sizeof(arr) / sizeof(arr[0]));  
29. break;  
30. case 4:  
31. shell_sort(arr, sizeof(arr) / sizeof(arr[0]));  
32. break;  
33. case 5:  
34. quick_sort(arr, sizeof(arr) / sizeof(arr[0]));  
35. break;  
36. case 6:  
37. merge_sort(arr, sizeof(arr) / sizeof(arr[0]));  
38. break;  
39. case 7:  
40. heap_sort(arr, sizeof(arr) / sizeof(arr[0]));  
41. break;  
42. case 8:  
43. lst_radix_sort(arr, sizeof(arr) / sizeof(arr[0]), 10, 4);  
44. break;  
45. default:  
46. break;  
47. }  
48. printArray(arr, sizeof(arr) / sizeof(arr[0]));  
49. }  
50. return 0;  
51. }  

最后是运行结果图，如下：

以上就是C++实现八个常用的排序算法的全部代码，希望大家对C++排序算法有更进一步的了解。