本文實現了八個常用的排序算法：插入排序、冒泡排序、選擇排序、希爾排序 、快速排序、歸并排序、堆排序和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++排序算法有更進一步的了解。
