提起排序算法相信大家都不陌生，或許很多人已經(jīng)把它們記得滾瓜爛熟，甚至隨時(shí)可以寫(xiě)出來(lái)。是的，這些都是最基本的算法。這里就把各種內(nèi)部排序算法總結(jié)歸納了一下，包括插入排序（直接插入排序，折半插入排序，希爾排序）、交換排序（冒泡排序，快速排序）、選擇排序（簡(jiǎn)單選擇排序，堆排序）、2-路歸并排序。（另：至于堆排序算法，前面已經(jīng)有一篇文章針對(duì)堆排序的算法實(shí)現(xiàn)做了詳細(xì)的描述）
C++實(shí)現(xiàn)代碼如下：
|
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;/* *<<直接插入排序>> * 為了實(shí)現(xiàn)N個(gè)數(shù)的排序，將后面N-1個(gè)數(shù)依次插入到前面已排好的子序列中， *假定剛開(kāi)始第1個(gè)數(shù)是一個(gè)已排好序的子序列。經(jīng)過(guò)N-1趟就能得到一個(gè)有序序列。 *****時(shí)間復(fù)雜度：最好情況O(n)，最壞情況O(n^2)，平均情況O(n^2). *****空間復(fù)雜度：O(1) *****穩(wěn)定性：穩(wěn)定 */void InsertSort(ElementType A[], int n){ int i,j; ElementType temp; // 臨時(shí)變量 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; }}/* *<<折半插入排序>> * 與直接插入排序不同的是，折半插入排序不是邊比較邊移動(dòng)，而是將比較和移 *動(dòng)操作分離出來(lái)，即先折半查找出元素的待插入位置，然后再統(tǒng)一地移動(dòng)待插入位 *置之后的所有元素。不難看出折半插入排序僅僅是減少了比較的次數(shù)。 *****時(shí)間復(fù)雜度：O(n^2) *****空間復(fù)雜度：O(1) *****穩(wěn)定性：穩(wěn)定 */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; // 設(shè)置折半查找的范圍 while(low <= high) { mid = (low+high)/2; // 取中間點(diǎn) if(A[mid] > temp) high = mid-1; else low = mid+1; } for(j=i-1; j>=high+1; --j) // 統(tǒng)一后移 A[j+1] = A[j]; A[high+1] = temp; // 插入 }}/* *<<希爾排序>> * 希爾排序通過(guò)比較相距一定間隔的元素，即形如L[i,i+d,i+2d,...i+kd]的序列 *然后縮小間距，再對(duì)各分組序列進(jìn)行排序。直到只比較相鄰元素的最后一趟排序?yàn)?/code> *止，即最后的間距為1。希爾排序有時(shí)也叫做*縮小增量排序* *****時(shí)間復(fù)雜度：依賴于增量序列的選擇，但最壞情況才為O(N^2) *****空間復(fù)雜度：O(1) *****穩(wěn)定性：不穩(wěn)定 */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) // 每個(gè)分組序列進(jìn)行直接插入排序 { temp = A[i]; for(j=i-dk; j>=0 && A[j]>temp; j-=dk) A[j+dk] = A[j]; // 后移 A[j+dk] = temp; } }}/* *<<冒泡排序>> * 冒泡排序的基本思想是從后往前（或從前往后）兩兩比較相鄰元素的值，若為 *逆序，則交換它們，直到序列比較完。我們稱它為一趟冒泡。每一趟冒泡都會(huì)將一 *個(gè)元素放置到其最終位置上。 *****時(shí)間復(fù)雜度：最好情況O(n)，最壞情況O(n^2)，平均情況O(n^2) *****空間復(fù)雜度：O(1) *****穩(wěn)定性：穩(wěn)定 */void BubbleSort(ElementType A[], int n){ for(int i=0; i<n-1; ++i) { bool flag = false; // 表示本次冒泡是否發(fā)生交換的標(biāo)志 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; }}/* *<<快速排序>> * 快速排序是對(duì)冒泡排序的一種改進(jìn)。其基本思想是基于分治法：在待排序表L[n] *中任取一個(gè)元素pivot作為基準(zhǔn)，通過(guò)一趟排序?qū)⑿蛄袆澐譃閮刹糠諰[1...K-1]和 *L[k+1...n]，是的L[1...k-1]中的所有元素都小于pivot，而L[k+1...n]中所有元素 *都大于或等于pivot。則pivot放在了其最終位置L(k)上。然后，分別遞歸地對(duì)兩個(gè)子 *序列重復(fù)上述過(guò)程，直至每部分內(nèi)只有一個(gè)元素或空為止，即所有元素放在了其最終 *位置上。 *****時(shí)間復(fù)雜度：快排的運(yùn)行時(shí)間與劃分是否對(duì)稱有關(guān)，最壞情況O(n^2),最好情況 *O(nlogn),平均情況為O(nlogn) *****空間復(fù)雜度：由于需要遞歸工作棧，最壞情況為O(n)，平均情況為O(logn) *****穩(wěn)定性：不穩(wěn)定 */int Partition(ElementType A[], int low, int high){ // 劃分操作有很多版本，這里就總以當(dāng)前表中第一個(gè)元素作為樞紐/基準(zhǔn) 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); // 劃分操作，返回基準(zhǔn)元素的最終位置 QuickSort(A, low, pivotPos-1); // 遞歸 QuickSort(A, pivotPos+1, high); }}/* *<<簡(jiǎn)單選擇排序>> * 選擇排序的算法思想很簡(jiǎn)單，假設(shè)序列為L(zhǎng)[n]，第i趟排序即從L[i...n]中選擇 *關(guān)鍵字最小的元素與L(i)交換，每一趟排序可以確定一個(gè)元素的最終位置。經(jīng)過(guò)n-1 *趟排序就可以使得序列有序了。 *****時(shí)間復(fù)雜度：始終是O(n^2) *****空間復(fù)雜度：O(1) *****穩(wěn)定性：不穩(wěn)定 */void SelectedSort(ElementType A[], int n){ for(int i=0; i<n-1; ++i) // 一共進(jìn)行n-1趟 { int minPos = i; // 記錄最小元素的位置 for(int j=i+1; j<n; ++j) if(A[j] < A[minPos]) minPos = j; if(minPos != i) // 與第i個(gè)位置交換 { A[i] = A[i]^A[minPos]; A[minPos] = A[i]^A[minPos]; A[i] = A[i]^A[minPos]; } }}/* *<<堆排序>> * 堆排序是一種樹(shù)形選擇排序方法，在排序過(guò)程中，將L[n]看成是一棵完全二叉 *樹(shù)的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹(shù)中雙親節(jié)點(diǎn)和孩子節(jié)點(diǎn)之間的內(nèi)在關(guān)系，在當(dāng) *前無(wú)序區(qū)中選擇關(guān)鍵字最大（或最小）的元素。堆排序的思路是：首先將序列L[n] *的n個(gè)元素建成初始堆，由于堆本身的特點(diǎn)（以大根堆為例），堆頂元素就是最大 *值。輸出堆頂元素后，通常將堆底元素送入堆頂，此時(shí)根結(jié)點(diǎn)已不滿足大根堆的性 *質(zhì)，堆被破壞，將堆頂元素向下調(diào)整使其繼續(xù)保持大根堆的性質(zhì)，再輸出堆頂元素。 *如此重復(fù)，直到堆中僅剩下一個(gè)元素為止。 *****時(shí)間復(fù)雜度：O(nlogn) *****空間復(fù)雜度：O(1) *****穩(wěn)定性：不穩(wěn)定 */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; // 如果右子結(jié)點(diǎn)大 if(temp < A[largest]) { A[i] = A[largest]; i = largest; // 記錄交換后的位置 } else break; } A[i] = temp; // 被篩選結(jié)點(diǎn)的值放入最終位置}void BuildMaxHeap(ElementType A[], int len){ for(int i=len/2-1; i>=0; --i) // 從i=[n/2]~1，反復(fù)調(diào)整堆 AdjustDown(A, i, len);}void HeapSort(ElementType A[], int n){ BuildMaxHeap(A, n); // 初始建堆 for(int i=n-1; i>0; --i) // n-1趟的交換和建堆過(guò)程 { // 輸出最大的堆頂元素（和堆底元素交換） A[0] = A[0]^A[i]; A[i] = A[0]^A[i]; A[0] = A[0]^A[i]; // 調(diào)整，把剩余的n-1個(gè)元素整理成堆 AdjustDown(A, 0, i); }}/* *<<2-路歸并排序>> * 顧名思義，2-路歸并就是將2個(gè)有序表組合成一個(gè)新的有序表。假定待排序表 *有n個(gè)元素，則可以看成是n個(gè)有序的子表，每個(gè)子表長(zhǎng)度為1，然后兩兩歸并...不 *停重復(fù)，直到合成一個(gè)長(zhǎng)度為n的有序序列為止。Merge()函數(shù)是將前后相鄰的兩個(gè) *有序表歸并為一個(gè)有序表，設(shè)A[low...mid]和A[mid+1...high]存放在同一順序表的 *相鄰位置上，先將它們復(fù)制到輔助數(shù)組B中。每次從對(duì)應(yīng)B中的兩個(gè)段取出一個(gè)元素 *進(jìn)行比較，將較小者放入A中。 *****時(shí)間復(fù)雜度：每一趟歸并為O(n),共log2n趟，所以時(shí)間為O(nlog2n) *****空間復(fù)雜度：O(n) *****穩(wěn)定性：穩(wěn)定 */ElementType *B = new ElementType[13]; // 和數(shù)組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中所有元素復(fù)制到B for(i=low,j=mid+1,k=i; i<=mid&&j<=high; ++k) { if(B[i] <= B[j]) // 比較B的左右兩段序列中的元素 A[k] = B[i++]; // 將較小值復(fù)制到A中 else A[k] = B[j++]; } while(i<=mid) A[k++] = B[i++]; // 若第一個(gè)表未檢測(cè)完，復(fù)制 while(j<=high) A[k++] = B[j++]; // 若第二個(gè)表未檢測(cè)完，復(fù)制}void MergeSort(ElementType A[], int low, int high){ if(low < high) { int mid = (low + high)/2; MergeSort(A, low, mid); // 對(duì)左側(cè)子序列進(jìn)行遞歸排序 MergeSort(A, mid+1, high); // 對(duì)右側(cè)子序列進(jìn)行遞歸排序 Merge(A, low, mid, high); // 歸并 }}/* * 輸出函數(shù) */void print(ElementType A[], int n){ for(int i=0; i<n; ++i) { cout << A[i] << " "; } cout << endl;}/* * 主函數(shù) */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;} |
相信本文所述實(shí)例代碼對(duì)大家復(fù)習(xí)和鞏固各類排序算法能起到一定的幫助作用。
