提起排序算法相信大家都不陌生，或許很多人已經把它們記得滾瓜爛熟，甚至隨時可以寫出來。是的，這些都是最基本的算法。這里就把各種內部排序算法總結歸納了一下，包括插入排序（直接插入排序，折半插入排序，希爾排序）、交換排序（冒泡排序，快速排序）、選擇排序（簡單選擇排序，堆排序）、2-路歸并排序。（另：至于堆排序算法，前面已經有一篇文章針對堆排序的算法實現做了詳細的描述）
C++實現代碼如下：
|
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
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
|
/************************************************************************* > File Name: sort.cpp > Author: SongLee ************************************************************************/#include<iostream>using namespace std;typedef int ElementType;/* *<<直接插入排序>> * 為了實現N個數的排序，將后面N-1個數依次插入到前面已排好的子序列中， *假定剛開始第1個數是一個已排好序的子序列。經過N-1趟就能得到一個有序序列。 *****時間復雜度：最好情況O(n)，最壞情況O(n^2)，平均情況O(n^2). *****空間復雜度：O(1) *****穩定性：穩定 */void InsertSort(ElementType A[], int n){ int i,j; ElementType temp; // 臨時變量 for(i=1; i<n; ++i) { temp = A[i]; for(j = i; j>0 && A[j-1]>temp; --j) A[j] = A[j-1]; A[j] = temp; }}/* *<<折半插入排序>> * 與直接插入排序不同的是，折半插入排序不是邊比較邊移動，而是將比較和移 *動操作分離出來，即先折半查找出元素的待插入位置，然后再統一地移動待插入位 *置之后的所有元素。不難看出折半插入排序僅僅是減少了比較的次數。 *****時間復雜度：O(n^2) *****空間復雜度：O(1) *****穩定性：穩定 */void BinaryInsertSort(ElementType A[], int n){ int i, j, low, high, mid; ElementType temp; for(i=1; i<n; ++i) { temp = A[i]; low = 0; high = i-1; // 設置折半查找的范圍 while(low <= high) { mid = (low+high)/2; // 取中間點 if(A[mid] > temp) high = mid-1; else low = mid+1; } for(j=i-1; j>=high+1; --j) // 統一后移 A[j+1] = A[j]; A[high+1] = temp; // 插入 }}/* *<<希爾排序>> * 希爾排序通過比較相距一定間隔的元素，即形如L[i,i+d,i+2d,...i+kd]的序列 *然后縮小間距，再對各分組序列進行排序。直到只比較相鄰元素的最后一趟排序為 *止，即最后的間距為1。希爾排序有時也叫做*縮小增量排序* *****時間復雜度：依賴于增量序列的選擇，但最壞情況才為O(N^2) *****空間復雜度：O(1) *****穩定性：不穩定 */void ShellSort(ElementType A[], int n){ int i, j, dk; // dk是增量 ElementType temp; for(dk=n/2; dk>0; dk/=2) // 增量變化 { for(i=dk; i<n; ++i) // 每個分組序列進行直接插入排序 { temp = A[i]; for(j=i-dk; j>=0 && A[j]>temp; j-=dk) A[j+dk] = A[j]; // 后移 A[j+dk] = temp; } }}/* *<<冒泡排序>> * 冒泡排序的基本思想是從后往前（或從前往后）兩兩比較相鄰元素的值，若為 *逆序，則交換它們，直到序列比較完。我們稱它為一趟冒泡。每一趟冒泡都會將一 *個元素放置到其最終位置上。 *****時間復雜度：最好情況O(n)，最壞情況O(n^2)，平均情況O(n^2) *****空間復雜度：O(1) *****穩定性：穩定 */void BubbleSort(ElementType A[], int n){ for(int i=0; i<n-1; ++i) { bool flag = false; // 表示本次冒泡是否發生交換的標志 for(int j=n-1; j>i; --j) // 從后往前 { if(A[j-1] > A[j]) { flag = true; // 交換 A[j-1] = A[j-1]^A[j]; A[j] = A[j-1]^A[j]; A[j-1] = A[j-1]^A[j]; } } if(flag == false) return; }}/* *<<快速排序>> * 快速排序是對冒泡排序的一種改進。其基本思想是基于分治法：在待排序表L[n] *中任取一個元素pivot作為基準，通過一趟排序將序列劃分為兩部分L[1...K-1]和 *L[k+1...n]，是的L[1...k-1]中的所有元素都小于pivot，而L[k+1...n]中所有元素 *都大于或等于pivot。則pivot放在了其最終位置L(k)上。然后，分別遞歸地對兩個子 *序列重復上述過程，直至每部分內只有一個元素或空為止，即所有元素放在了其最終 *位置上。 *****時間復雜度：快排的運行時間與劃分是否對稱有關，最壞情況O(n^2),最好情況 *O(nlogn),平均情況為O(nlogn) *****空間復雜度：由于需要遞歸工作棧，最壞情況為O(n)，平均情況為O(logn) *****穩定性：不穩定 */int Partition(ElementType A[], int low, int high){ // 劃分操作有很多版本，這里就總以當前表中第一個元素作為樞紐/基準 ElementType pivot = A[low]; while(low < high) { while(low<high && A[high]>=pivot) --high; A[low] = A[high]; // 將比樞紐值小的元素移到左端 while(low<high && A[low]<=pivot) ++low; A[high] = A[low]; // 將比樞紐值大的元素移到右端 } A[low] = pivot; // 樞紐元素放到最終位置 return low; // 返回樞紐元素的位置}void QuickSort(ElementType A[], int low, int high){ if(low < high) // 遞歸跳出的條件 { int pivotPos = Partition(A, low, high); // 劃分操作，返回基準元素的最終位置 QuickSort(A, low, pivotPos-1); // 遞歸 QuickSort(A, pivotPos+1, high); }}/* *<<簡單選擇排序>> * 選擇排序的算法思想很簡單，假設序列為L[n]，第i趟排序即從L[i...n]中選擇 *關鍵字最小的元素與L(i)交換，每一趟排序可以確定一個元素的最終位置。經過n-1 *趟排序就可以使得序列有序了。 *****時間復雜度：始終是O(n^2) *****空間復雜度：O(1) *****穩定性：不穩定 */void SelectedSort(ElementType A[], int n){ for(int i=0; i<n-1; ++i) // 一共進行n-1趟 { int minPos = i; // 記錄最小元素的位置 for(int j=i+1; j<n; ++j) if(A[j] < A[minPos]) minPos = j; if(minPos != i) // 與第i個位置交換 { A[i] = A[i]^A[minPos]; A[minPos] = A[i]^A[minPos]; A[i] = A[i]^A[minPos]; } }}/* *<<堆排序>> * 堆排序是一種樹形選擇排序方法，在排序過程中，將L[n]看成是一棵完全二叉 *樹的順序存儲結構，利用完全二叉樹中雙親節點和孩子節點之間的內在關系，在當 *前無序區中選擇關鍵字最大（或最小）的元素。堆排序的思路是：首先將序列L[n] *的n個元素建成初始堆，由于堆本身的特點（以大根堆為例），堆頂元素就是最大 *值。輸出堆頂元素后，通常將堆底元素送入堆頂，此時根結點已不滿足大根堆的性 *質，堆被破壞，將堆頂元素向下調整使其繼續保持大根堆的性質，再輸出堆頂元素。 *如此重復，直到堆中僅剩下一個元素為止。 *****時間復雜度：O(nlogn) *****空間復雜度：O(1) *****穩定性：不穩定 */void AdjustDown(ElementType A[], int i, int len){ ElementType temp = A[i]; // 暫存A[i] for(int largest=2*i+1; largest<len; largest=2*largest+1) { if(largest!=len-1 && A[largest+1]>A[largest]) ++largest; // 如果右子結點大 if(temp < A[largest]) { A[i] = A[largest]; i = largest; // 記錄交換后的位置 } else break; } A[i] = temp; // 被篩選結點的值放入最終位置}void BuildMaxHeap(ElementType A[], int len){ for(int i=len/2-1; i>=0; --i) // 從i=[n/2]~1，反復調整堆 AdjustDown(A, i, len);}void HeapSort(ElementType A[], int n){ BuildMaxHeap(A, n); // 初始建堆 for(int i=n-1; i>0; --i) // n-1趟的交換和建堆過程 { // 輸出最大的堆頂元素（和堆底元素交換） A[0] = A[0]^A[i]; A[i] = A[0]^A[i]; A[0] = A[0]^A[i]; // 調整，把剩余的n-1個元素整理成堆 AdjustDown(A, 0, i); }}/* *<<2-路歸并排序>> * 顧名思義，2-路歸并就是將2個有序表組合成一個新的有序表。假定待排序表 *有n個元素，則可以看成是n個有序的子表，每個子表長度為1，然后兩兩歸并...不 *停重復，直到合成一個長度為n的有序序列為止。Merge()函數是將前后相鄰的兩個 *有序表歸并為一個有序表，設A[low...mid]和A[mid+1...high]存放在同一順序表的 *相鄰位置上，先將它們復制到輔助數組B中。每次從對應B中的兩個段取出一個元素 *進行比較，將較小者放入A中。 *****時間復雜度：每一趟歸并為O(n),共log2n趟，所以時間為O(nlog2n) *****空間復雜度：O(n) *****穩定性：穩定 */ElementType *B = new ElementType[13]; // 和數組A一樣大void Merge(ElementType A[], int low, int mid, int high){ int i, j, k; for(k=low; k<=high; ++k) B[k] = A[k]; // 將A中所有元素復制到B for(i=low,j=mid+1,k=i; i<=mid&&j<=high; ++k) { if(B[i] <= B[j]) // 比較B的左右兩段序列中的元素 A[k] = B[i++]; // 將較小值復制到A中 else A[k] = B[j++]; } while(i<=mid) A[k++] = B[i++]; // 若第一個表未檢測完，復制 while(j<=high) A[k++] = B[j++]; // 若第二個表未檢測完，復制}void MergeSort(ElementType A[], int low, int high){ if(low < high) { int mid = (low + high)/2; MergeSort(A, low, mid); // 對左側子序列進行遞歸排序 MergeSort(A, mid+1, high); // 對右側子序列進行遞歸排序 Merge(A, low, mid, high); // 歸并 }}/* * 輸出函數 */void print(ElementType A[], int n){ for(int i=0; i<n; ++i) { cout << A[i] << " "; } cout << endl;}/* * 主函數 */int main(){ ElementType Arr[13] = {5,2,1,8,3,6,4,7,0,9,12,10,11}; //InsertSort(Arr, 13); //BinaryInsertSort(Arr, 13); //ShellSort(Arr, 13); //BubbleSort(Arr, 13); //QuickSort(Arr, 0, 12); //SelectedSort(Arr, 13); //HeapSort(Arr, 13); //MergeSort(Arr, 0, 12); print(Arr, 13); return 0;} |
相信本文所述實例代碼對大家復習和鞏固各類排序算法能起到一定的幫助作用。
