需要的頭文件可以在我以前的文章里找到，排序的測試結果是非常有趣的，最有趣的就是冒泡了，冒泡的結果告訴我們，你們把數據排好序了再讓我給你排吧！其余的大家自己看測試結果吧！（可能不是非常準確，但是給大家一個參考，希望對大家有用，測試結果在下篇文章）
1 #include <iostream>
2 #include "d_timer.h"
3 #include "d_random.h"
4
5 using namespace std;
6
7 inline void my_swap(int arr[], int i, int j)
8 {
9 int temp;
10 temp = arr[i];
11 arr[i] = arr[j];
12 arr[j] = temp;
13 }
14
15 void bubbleSort(int arr[], int n)
16 {
17 int i, j;
18 bool exchanged = true;
19 for (i = n - 1; i > 0 && exchanged; --i)
20 {
21 exchanged = false;
22 for (j = 1; j <= i; ++j)
23 if (arr[j] < arr[j - 1])
24 {
25 my_swap(arr, j, j - 1);
26
27 exchanged = true;
28 }
29 }
30 }
31
32 void exchangeSort(int arr[], int n)
33 {
34 int i, j;
35 for (i = 0; i < n -1; ++i)
36 for (j = i + 1; j < n; ++j)
37 if (arr[j] < arr[i])
38 my_swap(arr, j, i);
39 }
40
41 void selectionSort(int arr[], int n)
42 {
43 int i, j;
44 int min;
45 for (i = 0; i < n - 1; ++i)
46 {
47 min = i;
48 for (j = i + 1; j < n; ++j)
49 if (arr[j] < arr[min])
50 min = j;
51 if (min != i)
52 my_swap(arr, min, i);
53 }
54 }
55
56 void insertionSort(int arr[], int n)
57 {
58 int i, j;
59 int temp;
60 for (i = 1; i < n; ++i)
61 {
62 temp = arr[i];
63 for (j = i; j > 0 && arr[j - 1] > temp; --j)
64 arr[j] = arr[j - 1];
65 arr[j] = temp;
66 }
67 }
68 int Sedgewick[17] = { 587521, 260609, 146305, 64769, 36289, 16001, 8929, 3905, 2161, 929, 505, 209, 109, 41, 19, 5, 1};
69 void shellSort(int arr[], int n)
70 {
71
72 int seq;
73 for (seq = 0; seq < 17; ++seq)
74 {
75 if (Sedgewick[seq] < n)
76 break;
77 }
78
79 int i, j;
80 int temp;
81 for ( ; seq < 17; ++seq)
82 for (i = Sedgewick[seq]; i < n; ++i)
83 {
84 temp = arr[i];
85 // different from insertion sort e: j >= Sedgewick[seq]
86 for (j = i; j >= Sedgewick[seq] && arr[j - Sedgewick[seq]] > temp; j -= Sedgewick[seq])
87 arr[j] = arr[j - Sedgewick[seq]];
88 arr[j] = temp;
89 }
90 }
91
92 void merge(int arr[], int tmpArr[], int lPos, int rPos, int rEnd)
93 {
94 int i, lEnd, num, tmpPos;
95 lEnd = rPos - 1;
96 tmpPos = lPos;
97 num = rEnd - lPos + 1;
98
99 while (lPos <= lEnd && rPos <= rEnd)
100 if (arr[lPos] <= arr[rPos])
101 tmpArr[tmpPos++] = arr[lPos++];
102 else
103 tmpArr[tmpPos++] = arr[rPos++];
104
105 while (lPos <= lEnd)
106 tmpArr[tmpPos++] = arr[lPos++];
107 while (rPos <= rEnd)
108 tmpArr[tmpPos++] = arr[rPos++];
109
110 for (i = 0; i < num; i++, rEnd--)
111 arr[rEnd] = tmpArr[rEnd];
112 }
113 void msort(int arr[], int tmpArr[], int left, int right)
114 {
115 int center;
116
117 if (left < right)
118 {
119 center = (left + right) / 2;
120 msort(arr, tmpArr, left, center);
121 msort(arr, tmpArr, center + 1, right);
122 merge(arr, tmpArr, left, center + 1, right);
123 }
124 }
125 void mergeSort(int arr[], int n)
126 {
127 int *tmpArr;
128
129 tmpArr = new int[n];
130 if (tmpArr != NULL)
131 {
132 msort(arr, tmpArr, 0, n - 1);
133 delete [] tmpArr;
134 }
135 else
136 cerr << "No space for tmp array!!!" << endl;
137 }
138
139 inline int leftChild(int i)
140 {
141 return 2 * i + 1;
142 }
143 void percDown(int arr[], int i, int n)
144 {
145 int child;
146 int temp;
147
148 for (temp = arr[i]; leftChild(i) < n; i = child)
149 {
150 child = leftChild(i);
151 if (child != n - 1 && arr[child + 1] > arr[child])
152 child++;
153 if (temp < arr[child])
154 arr[i] = arr[child];
155 else
156 break;
157 }
158 arr[i] = temp;
159 }
160 void heapSort(int arr[], int n)
161 {
162 int i;
163 for (i = n / 2; i >= 0; --i)
164 percDown(arr, i, n);
165 for (i = n - 1; i > 0; --i)
166 {
167 my_swap(arr, 0, i);
168 percDown(arr, 0, i);
169 }
170 }
171
172 int median3(int arr[], int left, int right)
173 {
174 int center = (left + right) / 2;
175
176 if (arr[left] > arr[center])
177 my_swap(arr, left, center);
178 if (arr[left] > arr[right])
179 my_swap(arr, left, right);
180 if (arr[center] > arr[right])
181 my_swap(arr, center, right);
182
183 my_swap(arr, center, right - 1);
184 return arr[right - 1];
185 }
186 const int CUTOFF = 30;
187 void QTrueSort(int arr[], int left, int right)
188 {
189 int i, j;
190 int pivot;
191
192 if (left + CUTOFF <= right)
193 {
194 pivot = median3(arr, left, right);
195 i = left;
196 j = right - 1;
197 for ( ; ; )
198 {
199 while (arr[++i] < pivot) { }
200 while (arr[--j] > pivot) { }
201 if (i < j)
202 my_swap(arr, i, j);
203 else
204 break;
205 }
206 my_swap(arr, i, right - 1);
207
208 QTrueSort(arr, left, i - 1);
209 QTrueSort(arr, i + 1, right);
210 }
211 else
212 insertionSort(arr + left, right - left + 1);
213 }
214 inline void QSort(int arr[], int n)
215 {
216 QTrueSort(arr, 0, n - 1);
217 }
218
219
220 int main()
221 {
222 const int SIZE = 10000000;
223 int *arrAscend = new int[SIZE],
224 *arrDescend = new int[SIZE],
225 *arrBubble = new int[SIZE],
226 *arrExchange = new int[SIZE],
227 *arrSelection = new int[SIZE],
228 *arrInsertion = new int[SIZE],
229 *arrShell = new int[SIZE],
230 *arrMergeSort = new int[SIZE],
231 *arrHeapSort = new int[SIZE],
232 *arrQSort = new int[SIZE];
233 for (int i = 0; i < SIZE; ++i)
234 {
235 arrAscend[i] = i;
236 arrDescend[i] = SIZE - i;
237 }
238 randomNumber rnd;
239 for (int i = 0; i < SIZE; ++i)
240 arrBubble[i] = arrExchange[i] = arrSelection[i] =
241 arrInsertion[i] = arrShell[i] = arrMergeSort[i] = arrHeapSort[i] = arrQSort[i] = rnd.random(SIZE);
242 timer t;
243
244 t.start();
245 bubbleSort(arrAscend, SIZE);
246 t.stop();
247 cout << "Bubble Sort Ascend: " << t.time() << endl;
248 t.start();
249 bubbleSort(arrDescend, SIZE);
250 t.stop();
251 cout << "Bubble Sort Descend: " << t.time() << endl;
252 t.start();
253 bubbleSort(arrBubble, SIZE);
254 t.stop();
255 cout << "Bubble Sort Normal: " << t.time() << endl;
256
257 for (int i = 0; i < SIZE; ++i)
258 {
259 arrDescend[i] = SIZE - i;
260 }
261 t.start();
262 exchangeSort(arrAscend, SIZE);
263 t.stop();
264 cout << "Exchange Sort Ascend: " << t.time() << endl;
265 t.start();
266 exchangeSort(arrDescend, SIZE);
267 t.stop();
268 cout << "Exchange Sort Descend: " << t.time() << endl;
269 t.start();
270 exchangeSort(arrExchange, SIZE);
271 t.stop();
272 cout << "Exchange Sort Normal: " << t.time() << endl;
273
274 for (int i = 0; i < SIZE; ++i)
275 {
276 arrDescend[i] = SIZE - i;
277 }
278 t.start();
279 selectionSort(arrAscend, SIZE);
280 t.stop();
281 cout << "Selection Sort Ascend: " << t.time() << endl;
282 t.start();
283 selectionSort(arrDescend, SIZE);
284 t.stop();
285 cout << "Selection Sort Descend: " << t.time() << endl;
286 t.start();
287 selectionSort(arrSelection, SIZE);
288 t.stop();
289 cout << "Selection Sort Normal: " << t.time() << endl;
290
291 for (int i = 0; i < SIZE; ++i)
292 {
293 arrDescend[i] = SIZE - i;
294 }
295 t.start();
296 insertionSort(arrAscend, SIZE);
297 t.stop();
298 cout << "Insertion Sort Ascend: " << t.time() << endl;
299 t.start();
300 insertionSort(arrDescend, SIZE);
301 t.stop();
302 cout << "Insertion Sort Descend: " << t.time() << endl;
303 t.start();
304 insertionSort(arrInsertion, SIZE);
305 t.stop();
306 cout << "Insertion Sort Normal: " << t.time() << endl;
307
308 for (int i = 0; i < SIZE; ++i)
309 {
310 arrDescend[i] = SIZE - i;
311 }
312 t.start();
313 shellSort(arrAscend, SIZE);
314 t.stop();
315 cout << "Shell Sort Ascend: " << t.time() << endl;
316 t.start();
317 shellSort(arrDescend, SIZE);
318 t.stop();
319 cout << "Shell Sort Descend: " << t.time() << endl;
320 t.start();
321 shellSort(arrShell, SIZE);
322 t.stop();
323 cout << "Shell Sort Normal: " << t.time() << endl;
324
325 for (int i = 0; i < SIZE; ++i)
326 {
327 arrDescend[i] = SIZE - i;
328 }
329 t.start();
330 mergeSort(arrAscend, SIZE);
331 t.stop();
332 cout << "MergeSort Ascend: " << t.time() << endl;
333 t.start();
334 mergeSort(arrDescend, SIZE);
335 t.stop();
336 cout << "Merge Sort Descend: " << t.time() << endl;
337 t.start();
338 mergeSort(arrMergeSort, SIZE);
339 t.stop();
340 cout << "Merge Sort Normal: " << t.time() << endl;
341
342 for (int i = 0; i < SIZE; ++i)
343 {
344 arrDescend[i] = SIZE - i;
345 }
346 t.start();
347 heapSort(arrAscend, SIZE);
348 t.stop();
349 cout << "Heap Sort Ascend: " << t.time() << endl;
350 t.start();
351 heapSort(arrDescend, SIZE);
352 t.stop();
353 cout << "Heap Sort Descend: " << t.time() << endl;
354 t.start();
355 heapSort(arrHeapSort, SIZE);
356 t.stop();
357 cout << "Heap Sort Normal: " << t.time() << endl;
358
359 for (int i = 0; i < SIZE; ++i)
360 {
361 arrDescend[i] = SIZE - i;
362 }
363 t.start();
364 QSort(arrAscend, SIZE);
365 t.stop();
366 cout << "Quick Sort Ascend: " << t.time() << endl;
367 t.start();
368 QSort(arrDescend, SIZE);
369 t.stop();
370 cout << "Quick Sort Descend: " << t.time() << endl;
371 t.start();
372 QSort(arrQSort, SIZE);
373 t.stop();
374 cout << "Quick Sort Normal: " << t.time() << endl;
375
376 delete [] arrAscend;
377 delete [] arrDescend;
378 delete [] arrBubble;
379 delete [] arrExchange;
380 delete [] arrSelection;
381 delete [] arrInsertion;
382 delete [] arrShell;
383 delete [] arrMergeSort;
384 delete [] arrHeapSort;
385 delete [] arrQSort;
386 return 0;
387 }
posted on 2009-08-31 21:35
diwayou 閱讀(1773)
評論(4) 編輯 收藏 引用 所屬分類:
數據結構與算法