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