《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計報告---排序算法的實現(xiàn)與比較

1、<p><b>　　設(shè)計內(nèi)容及要求</b></p><p>　　編程實現(xiàn)插入、希爾、快速、堆排序、歸并排序算法，并計算每種算法的比較、交換次數(shù)。將待排數(shù)據(jù)從磁盤文件讀入，實施排序后將數(shù)據(jù)寫入另一個文件中。</p><p><b>　　概述</b></p><p>　　在本設(shè)計課題中，我們將對常見的5中排序算法——

2、插入、希爾、快速、堆排序、歸并排序進(jìn)行各種情況下的比較，如待排數(shù)據(jù)為順序、逆序或隨機(jī)的情況下，各個算法對于特定數(shù)據(jù)的性能?；诖它c考慮，在程序中選擇采用以毫秒為單位的執(zhí)行時間來衡量算法對特定數(shù)據(jù)的性能高低。本文將主要介紹《排序之謎》程序（以下簡稱“程序”）的數(shù)據(jù)結(jié)構(gòu)的設(shè)計、功能設(shè)計以及相關(guān)技術(shù)討論等。本程序在Microsoft Windows Server 2003/Microsoft Visual C++ 2005的命令行編譯器cl.

3、exe環(huán)境編譯下通過。</p><p><b>　　分發(fā)包說明</b></p><p>　　程序分發(fā)包中將包含以下文件，其用途分別如表格1所示。</p><p><b>　　表格 1</b></p><p><b>　　數(shù)據(jù)結(jié)構(gòu)設(shè)計</b></p><p&g

4、t;<b>　　主程序數(shù)據(jù)結(jié)構(gòu)</b></p><p>　　主程序中采用兩個整型數(shù)組input_array和output_array，其長度均為10000，分別作為待排序數(shù)據(jù)和已排序數(shù)據(jù)的存放空間，并設(shè)置一整型數(shù)組sort_time用來存放5個算法的執(zhí)行時間。之所以這樣設(shè)計，是因為所有的用戶定義函數(shù)都完全按照既定的“標(biāo)準(zhǔn)”設(shè)計實現(xiàn)，使得整個程序的可伸縮性大大增強(qiáng)。</p>&l

5、t;p>　　#define LENGTH 10000</p><p>　　int length = LENGTH;</p><p>　　int input_array[LENGTH] = {0};</p><p>　　int output_array[LENGTH] = {0};</p><p>　　int sort_time[5] =

6、 {0};</p><p>　　// 0 InsertionSort, 1 QuickSort, 2 MergeSort,</p><p>　　// 3 HeapSort, 4 ShellSort</p><p><b>　　排序算法的設(shè)計實現(xiàn)</b></p><p>　　程序中的全部5中排序算法均按照標(biāo)準(zhǔn)化的函數(shù)名、返

7、回值和形參表設(shè)計，其形式為：</p><p>　　void SomeSortMethod(const int *array_to_sort, int *sorted_array, const int length);</p><p>　　算法的設(shè)計和實現(xiàn)參照了現(xiàn)有教科書上的算法描述，下面將逐一列出各個排序算法的C++實現(xiàn)。</p><p><b>　　插入

8、排序</b></p><p>　　插入排序是一種最簡單的排序方法，它的基本操作是將一個記錄插入到已經(jīng)排好序的有序表中，從而得到一個新的有序表。</p><p>　　void InsertionSort(const int *array_to_sort, int *sorted_array, const int length) {</p><p>　　fo

9、r (int i = 0; i < length; i++) {</p><p>　　sorted_array[i] = array_to_sort[i];</p><p><b>　　}</b></p><p>　　int i = 0, j = 0;</p><p>　　int key = 0;</p>

10、;<p>　　for (j = 1; j < length; j++) {</p><p>　　key = sorted_array[j];</p><p>　　i = j - 1;</p><p>　　while (i >= 0 && sorted_array[i] > key) {</p><p

11、>　　sorted_array[i + 1] = sorted_array[i];</p><p><b>　　i--;</b></p><p><b>　　}</b></p><p>　　sorted_array[i + 1] = key;</p><p><b>　　}</

12、b></p><p><b>　　}</b></p><p><b>　　快速排序</b></p><p>　　快速排序是對冒泡法排序的一種改進(jìn)。它的基本思想是，通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄均比另一部分記錄小，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個序列有序。</p>

13、<p>　　void quicksort(int v[], int left, int right)</p><p><b>　　{</b></p><p>　　int i, last;</p><p>　　void swap(int v[], int i, int j);</p><p>　　if (left

14、 >= right)</p><p><b>　　return;</b></p><p>　　swap(v, left, (left + right)/2);</p><p>　　last = left;</p><p>　　for (i = left + 1; i <= right; i++)</p&

15、gt;<p>　　if (v[i] < v[left])</p><p>　　swap(v, ++last, i);</p><p>　　swap(v, left, last);</p><p>　　quicksort(v, left, last-1);</p><p>　　quicksort(v, last+1, rig

16、ht);</p><p><b>　　}</b></p><p>　　void QuickSort(const int *array_to_sort, int *sorted_array, const int length) {</p><p>　　for (int i = 0; i < length; i++)</p>&

17、lt;p><b>　　{</b></p><p>　　sorted_array[i] = array_to_sort[i];</p><p><b>　　}</b></p><p>　　quicksort(sorted_array, 0, length - 1);</p><p><b&

18、gt;　　}</b></p><p><b>　　歸并排序</b></p><p>　　歸并排序的核心操作是將一位數(shù)組中前后兩個相鄰的有序序列歸并為一個有序序列，其實現(xiàn)如下：</p><p>　　void merge(int *src, int *dest, int lo, int mid, int hi) {</p>

19、<p>　　int j = 0, k = 0;</p><p>　　for (j = mid + 1, k = lo; lo <= mid && j <= hi; k++) {</p><p>　　if (src[lo] <= src[j])</p><p>　　dest[k] = src[lo++];</p>

20、;<p><b>　　else</b></p><p>　　dest[k] = src[j++];</p><p><b>　　}</b></p><p>　　if (lo <= mid) {</p><p>　　while (k <= hi) {</p>&

21、lt;p>　　dest[k] = src[lo];</p><p><b>　　k++;</b></p><p><b>　　lo++;</b></p><p><b>　　}</b></p><p><b>　　}</b></p>&

22、lt;p>　　if (j <= hi) {</p><p>　　while (k <= hi) {</p><p>　　dest[k] = src[j];</p><p><b>　　k++;</b></p><p><b>　　j++;</b></p><p&

23、gt;<b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　而歸并排序則是遞歸的調(diào)用上述歸并算法，將整個無序序列拆分成n個單個元素后兩兩歸并為相鄰的有序序列，依次遞歸的執(zhí)行下去，最終歸并為一個有序序列。其實現(xiàn)如下：</p>

24、;<p>　　void MSort(int *src, int *dest, int start, int end) {</p><p>　　int dest2[10000] = {0};</p><p>　　if (start == end)</p><p>　　dest[start] = src[start];</p><p&g

25、t;<b>　　else {</b></p><p>　　int mid = (start + end) / 2;</p><p>　　MSort(src, dest2, start, mid);</p><p>　　MSort(src, dest2, mid + 1, end);</p><p>　　merge(des

26、t2, dest, start, mid, end);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void MergeSort(const int *array_to_sort, int *sorted_array, const int length) {</

27、p><p>　　for (int i = 0; i < length; i++) {</p><p>　　sorted_array[i] = array_to_sort[i];</p><p><b>　　}</b></p><p>　　MSort(sorted_array, sorted_array, 0, leng

28、th - 1);</p><p><b>　　}</b></p><p><b>　　希爾排序</b></p><p>　　希爾排序是一種插入排序類的方法，但在時間效率上較傳統(tǒng)的插入排序方法有較大的改進(jìn)。其主要特點是，子序列的構(gòu)成不再是簡單的“逐段分割”，而是將相隔某個“增量”的記錄組成一個子序列。其實現(xiàn)如下：</p

29、><p>　　void shellsort (int *a, int n) {</p><p>　　int i, j, k, h, v;</p><p>　　int cols[] = {1391376, 463792, 198768, 86961, 33936, 13776, 4592,</p><p>　　1968, 861, 336, 112

30、, 48, 21, 7, 3, 1};</p><p>　　for (k = 0; k < 16; k++) {</p><p>　　h = cols[k];</p><p>　　for (i = h; i < n; i++) {</p><p><b>　　v = a[i];</b></p>

31、<p><b>　　j = i;</b></p><p>　　while (j >= h && a[j - h] > v) {</p><p>　　a[j] = a[j - h];</p><p><b>　　j -= h;</b></p><p><b&

32、gt;　　}</b></p><p><b>　　a[j] = v;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　v

33、oid ShellSort(const int *array_to_sort, int *sorted_array, const int length) {</p><p>　　for (int i = 0; i < length; i++) {</p><p>　　sorted_array[i] = array_to_sort[i];</p><p><

34、;b>　　}</b></p><p>　　shellsort(sorted_array, length);</p><p><b>　　}</b></p><p><b>　　堆排序</b></p><p>　　堆排序主要包括兩個步驟，即建堆；取出堆頂?shù)淖畲笤?，重新調(diào)整為堆。不斷

35、重復(fù)這兩個過程，直到堆為空。堆排序也不依賴于原是數(shù)組的有序情況，在最佳、最差、平均情況下的時間代價均相同。其實現(xiàn)如下：</p><p>　　void adjust_heap(int *heap, int root, int length) {</p><p><b>　　int done;</b></p><p><b>　　int

36、j;</b></p><p><b>　　int temp;</b></p><p>　　j = 2 * root;</p><p>　　temp = heap[root];</p><p><b>　　done = 0;</b></p><p>　　while

37、(j <= length && !done) {</p><p>　　if (j < length)</p><p>　　if (heap[j] < heap[j+1])</p><p><b>　　j++;</b></p><p>　　if (temp >= heap[j])&l

38、t;/p><p><b>　　done = 1;</b></p><p><b>　　else {</b></p><p>　　heap[j/2] = heap[j];</p><p>　　j = 2 * j;</p><p><b>　　}</b><

39、/p><p><b>　　}</b></p><p>　　heap[j/2] = temp;</p><p><b>　　}</b></p><p>　　void heap(int *heap, int length)</p><p><b>　　{</b>

40、</p><p>　　int i, j, temp;</p><p>　　for (i = (length / 2); i >= 1; i--)</p><p>　　adjust_heap(heap, i, length);</p><p>　　for (i = length - 1; i >= 1; i--) {</p&g

41、t;<p>　　temp = heap[i + 1];</p><p>　　heap[i + 1] = heap[1];</p><p>　　heap[1] = temp;</p><p>　　adjust_heap(heap, 1, i);</p><p><b>　　}</b></p>&

42、lt;p><b>　　}</b></p><p>　　void HeapSort(const int *array_to_sort, int *sorted_array, const int length) {</p><p>　　for (int i = 0; i < length; i++) {</p><p>　　sorted

43、_array[i] = array_to_sort[i];</p><p><b>　　}</b></p><p>　　heap(sorted_array, length - 1);</p><p><b>　　}</b></p><p><b>　　計時函數(shù)</b></

44、p><p>　　計時函數(shù)使用了Windows API 函數(shù)QueryPerformanceFrequency和QueryPerformanceCounter來實現(xiàn)毫秒級的計時功能。該函數(shù)接受一個指向函數(shù)的指針參數(shù)，用于在兩次查詢機(jī)器內(nèi)部計時器的計數(shù)之間插入所需要被計時的代碼，再降兩次查詢之差除以CPU時鐘頻率即可得到事件經(jīng)歷的精確時間。其實現(xiàn)如下：</p><p>　　int timing(v

45、oid (*fpt)(const int *array_to_sort, int *sorted_array, const int length), const int *array_to_sort, int *sorted_array, const int length) {</p><p>　　LARGE_INTEGER iLarge;</p><p>　　QueryPerforman

46、ceFrequency( &iLarge );</p><p>　　double dbFreq = (double) iLarge.QuadPart;</p><p>　　QueryPerformanceCounter( &iLarge );</p><p>　　double dbBegin = (double) iLarge.QuadPart;&l

47、t;/p><p>　　// Insert code to be timed below</p><p>　　fpt(array_to_sort, sorted_array, length);</p><p>　　// Insert code to be timed above</p><p>　　QueryPerformanceCounter(

48、&iLarge );</p><p>　　double dbEnd = (double) iLarge.QuadPart;</p><p>　　int nms = (int) (( dbEnd - dbBegin ) * 1000.0 / dbFreq );</p><p>　　return nms;</p><p><b>

49、;　　}</b></p><p><b>　　統(tǒng)計數(shù)據(jù)顯示函數(shù)</b></p><p>　　對同一組數(shù)據(jù)執(zhí)行了5種算法之后，產(chǎn)生了一組時間值，該函數(shù)用以在字符界面繪制一個時間長短的柱狀圖表。其實現(xiàn)如下：</p><p>　　void showStat(int array_to_show[], const int length) {&

50、lt;/p><p>　　char *alg_name[5] = {"Insertion Sort", "Quick Sort", "Merge Sort", "Heap Sort", "Shell Sort"};</p><p>　　int max = 0;</p><p&g

51、t;　　for (int i = 1; i < length; i++) {</p><p>　　if (array_to_show[i] > array_to_show[max])</p><p><b>　　max = i;</b></p><p><b>　　}</b></p><p&

52、gt;　　int *disp_value = new int[length];</p><p>　　for (int i = 0; i < length; i++) {</p><p>　　if (array_to_show[max] != 0) {</p><p>　　disp_value[i] = array_to_show[i] * 40 / array

53、_to_show[max]; // 40 is the max number of "|"</p><p><b>　　}</b></p><p><b>　　else {</b></p><p>　　disp_value[i] = 0;</p><p><b>

54、　　}</b></p><p>　　cout << alg_name[i] << "\t" << array_to_show[i] << " ms\t: ";</p><p>　　for (int j = 0; j < disp_value[i]; j++) {</p>

55、<p>　　cout << '|';</p><p><b>　　}</b></p><p>　　cout << endl;</p><p><b>　　}</b></p><p>　　cout << "(The short

56、er the bar is, the quicker the algorithm performs.)" << endl;</p><p>　　delete disp_value;</p><p><b>　　}</b></p><p><b>　　使用說明</b></p><p&

57、gt;　　運(yùn)行程序sort.exe后，可以看到在歡迎信息出現(xiàn)5秒之后，下方會顯示程序主菜單，如下所示：</p><p>　　========== Main Menu ==========</p><p>　　(R) Read input from file</p><p>　　(G) Generate a random sequence</p><

58、;p>　　(V) Generate a reversed sequence</p><p>　　(B) Begin sorting process</p><p>　　(S) Show statistics and charts</p><p>　　(E) Save results and exit</p><p>　　(D) Disc

59、ard changes and exit</p><p>　　(A) About this program</p><p>　　Please type in your option:</p><p>　　其中選擇R將會從程序所在目錄讀取名為src.dat的數(shù)據(jù)文件（如果存在的話）；選擇G將會在內(nèi)存中生成一隨機(jī)數(shù)序列用于排序；選擇V將會在內(nèi)存中生成一逆序數(shù)序列用于排序

60、；選擇B將上述待排序數(shù)據(jù)送給5個排序算法分別進(jìn)行排序，并記錄下排序所花費(fèi)的時間（單位：毫秒）；選擇S將顯示統(tǒng)計數(shù)據(jù)和圖表，典型的輸出如下所示；選擇E、D或A分別將保存已排序數(shù)據(jù)并退出、丟棄已排序數(shù)據(jù)并退出，和顯示“關(guān)于”信息。</p><p>　　Insertion Sort 358 ms : ||||||||||||||||||||||||||||||||||||||||</p><p&

61、gt;　　Quick Sort 1 ms :</p><p>　　Merge Sort 72 ms : ||||||||</p><p>　　Heap Sort 2 ms :</p><p>　　Shell Sort 1 ms :</p><p>　　(The shorter t

62、he bar is, the quicker the algorithm performs.)</p><p><b>　　缺陷與改進(jìn)</b></p><p>　　由于時間和能力有限，故在整個設(shè)計過程中存在以下幾點設(shè)計缺陷，如1）沒能使用MFC實現(xiàn)圖形化的人機(jī)交互界面；2）沒有使用交換次數(shù)來衡量算法的好壞等。</p><p>　　第1個問題主要

63、原因是由于MFC中的一個很簡單問題導(dǎo)致很多涉及到字符串的代碼編譯錯誤，延誤了很多時間，在時間緊張的情況下最終沒能實現(xiàn)圖形化界面。</p><p>　　第2個問題是由于考慮到5種算法并不相似，很多情況下不能僅僅通過交換次數(shù)來衡量一個算法的好壞，而是同時需要考慮到諸如數(shù)據(jù)的復(fù)制、移動，甚至是自增自減操作所帶來的時間開銷，所以最終選擇了采用直接計時后相互比較的方法來評價算法。</p><p>&

64、lt;b>　　討論與總結(jié)</b></p><p>　　本次課程設(shè)計在實際的編譯器、操作系統(tǒng)環(huán)境中實現(xiàn)了5種常見的排序算法。通過多次不同數(shù)據(jù)的測試發(fā)現(xiàn)，對于同一組測試數(shù)據(jù)，各種算法每次執(zhí)行的結(jié)果基本相同，在同樣的硬件條件下誤差不超過10毫秒，故可以通過該時間來比較算法的優(yōu)劣。</p><p>　　特別的，當(dāng)待排序的數(shù)據(jù)為一有序序列時，其典型的測試結(jié)果為：</p>

65、<p>　　Insertion Sort 0 ms :</p><p>　　Quick Sort 1 ms :</p><p>　　Merge Sort 72 ms : ||||||||||||||||||||||||||||||||||||||||</p><p>　　Heap Sort 2 ms

66、 : |</p><p>　　Shell Sort 1 ms :</p><p>　　(The shorter the bar is, the quicker the algorithm performs.)</p><p>　　而當(dāng)待排數(shù)據(jù)為一逆序序列時，其典型的測試結(jié)果為：</p><p>　　Insertion Sor

67、t 358 ms : ||||||||||||||||||||||||||||||||||||||||</p><p>　　Quick Sort 1 ms :</p><p>　　Merge Sort 72 ms : ||||||||</p><p>　　Heap Sort 2 ms :</p>&l

68、t;p>　　Shell Sort 1 ms :</p><p>　　(The shorter the bar is, the quicker the algorithm performs.)</p><p>　　當(dāng)待排數(shù)據(jù)為一組隨機(jī)序列時，其典型的測試結(jié)果為：</p><p>　　Insertion Sort 179 ms : ||||||

69、||||||||||||||||||||||||||||||||||</p><p>　　Quick Sort 2 ms :</p><p>　　Merge Sort 72 ms : ||||||||||||||||</p><p>　　Heap Sort 2 ms :</p><p>　　Sh

70、ell Sort 3 ms :</p><p>　　(The shorter the bar is, the quicker the algorithm performs.)</p><p>　　由此可見，插入排序在絕大多數(shù)情況下的時間效率都比較低，快速排序和希爾排序在絕大多數(shù)情況下時間效率都比較高。但是與教科書上不相符的是歸并排序和堆排序在數(shù)據(jù)量較大情況下的比較，個人認(rèn)為

71、可能存在某些與機(jī)器相關(guān)的代碼導(dǎo)致編譯器的優(yōu)化造成的，至于此假設(shè)是否正確尚待考證。</p><p>　　其他方面，如函數(shù)結(jié)構(gòu)的設(shè)計都遵循“統(tǒng)一”的原則，以便將來可以擴(kuò)展更多的算法進(jìn)行比較。所有CPP源代碼采用Makefile進(jìn)行依存關(guān)系的組織和自動化編譯的實現(xiàn)，以便修改后重新編譯整個程序。</p><p><b>　　參考文獻(xiàn)</b></p><p&

72、gt;　　[1] Stanley B. Lippman, Josée Lajoie, Barbara E. Moo -- C++ Primer, Fourth Edition -- Addison Wesley Professional, 2005</p><p>　　[2] Thomas H. Cormen, Charles E. Leiserson,

73、 Ronald L. Rivest and Clifford Stein -- Introduction to Algorithms, Second Edition -- The MIT Press, 2001</p><p>　　[3] 嚴(yán)蔚敏、吳偉民 -- 《數(shù)據(jù)結(jié)構(gòu)（C語言版）》 – 清華大學(xué)出版社，2006</p><p>　　[4] MSDN Library