1、目 錄摘 要 .2前 言.3正 文.4一、采用類 C語言定義相關的數據類型.4二、程序操作過程圖.6三、程序流程圖.7四、程序調試分析和結果.9五、源程序（帶注釋）.11六、各種排序算法的性能分析.20總 結.21心 得 體 會.23參 考 文 獻.24致 謝.26附件 I 部分源程序代碼.27摘 要排序（sorting）是計算機程序設計的一種重要操作，他的功能是將一個數據元素（或記錄）的任意序列，重新排列一個按關鍵字有序的序列。由于待排序的記錄數量不同，使得排序過程中涉及的儲存器不同，可將排序方法分為兩大類：一類是內部排序，指的是待排序記錄存放在計算機隨機儲存器中進行的排序過程；另一類是外部

2、排序，指的是待排序記錄的數量很大，以致內存一次不能容納全部記錄，在排序過程中尚需對外存進行訪問的排序過程。內部排序又分為：插入排序、快速排序、選擇排序、歸并排序和基數排序。其中插入排序又分為：直接插入排序、其他插入排序和希爾排序；選擇排序分為：簡單選擇排序、樹形選擇排序和堆排序；基數排序又分為：多關鍵字的排序和鏈式基數排序。本次課程設計就是內部排序中的幾個排序方法。關鍵字： 內部排序關鍵字重新排列前 言“天之道，損有余而補不足”，自然萬物發展的規律， 都是傾向于消除差異。無獨有偶，熱力學第二定律也指出：任意封閉的系統，都會朝著熵增加的方向發展。從信息論的角度來看，也就是傾向于更加無序。然而，“

3、 人之道，則不然，損不足以奉有余”，人總是偏好有序。就數據處理而言，有序性的確十分有用。所謂排序， 就是按照某種次序，重新排列某一序列中的所有元素。為此，任意一對元素之間 都應該能比較大小，即在所有元素之間可以定義一個全序關系。排序不僅可以作為查找等操作的預處理計算，而且也是實際應用中需要反復進行的一項基本操作。前言很多涉及計算器程序的算法都是以棧的相關操作為基礎，通過對計算器算法的設計，有利于在學習中更好的理解棧及其相關的操作。但是，這款計算器主要是通過數組進行的。沒有直接使用棧，但用到棧的思想。我們在寫程序時，大框架已成的情況下，仍然發現有些錯誤很難找到，對于這樣的問題，可以利用計算機糾錯

4、功能，先運行，再根據題提示修改和完善程序。在計算器用到的算法中，c 語言算法可讀性很強，一方面，是因為 c 語言是高級語言，是面向程序員的語言，二是 c 語言的功能是很完備的，可以達到事半功倍的效果，和其他語言相比量是比較少。正 文一、采用類 C 語言定義相關的數據類型（11、輸入2、選擇3、輸出（21、輸入模塊的功能：利用隨機函數產生N 個數（超過20000確，所以在本程序中只隨機產生100個數。create(a,b,&n) 是一個隨機函數，它可以隨機產生 100個隨機數 。2、選擇模塊的功能：選擇數字則進行對應的排序；選擇字母則進行重新產生隨機數和退出的操作。1插入排序insertsort

5、(a,n)2希爾排序xiersort(a,n)3快速排序quicksort(a,1,n)4堆排序duisort(a,n)C(c)重新產生20個隨機數create(a,b,&n)N(n)退出程序3、輸出模塊的功能：把利用各種排序方法排好順序的數輸出到一個文件夾中。writefile1(a,n)向指定的文件中寫入排序前的數writefile2(a,n)向指定的文件中寫入用各種排序方法排好序的數二、程序操作過程圖開始123456插 入排 序希 爾排 序冒 泡排序快 速排序簡單排序堆排序把利用排序方法排好序的數輸出到指定的文件夾N(n)C（c）重新產生隨機數三、程序流程圖開始N(n)退插 入排 序希

6、爾排 序冒 泡排序快 速排序簡單排序堆（c）重 新產 生隨 機排序把用各種排序方法排好的數的順序輸出到指定的文件夾中四、程序調試分析和結果（1 100 個數，選擇“1序；在選擇“2（3）選擇“34下：（45五、源程序（帶注釋）#include#include#include#include#define SIZE 20000struct elementint key;listSIZE;/創建一個數組/int creat()int i,n;int num;n=0;printf(請輸入元素個數:);scanf(%d,&num);for( i = 0;i num; i+ )listn.key = r

7、and() % 10000;n+;return(n);/輸出數組/void print(struct element aSIZE,int n)int i;for(i=0;in;i+)printf(%5d,ai .key);printf(n);/保存到文件/void save(struct element aSIZE,int n, char fileName )int m_wr=0; / 寫入 TXT文件變量FILE *fp;if ( ( fp = fopen ( fileName, w ) ) = NULL )printf(File writer errorn);for (int m=0; m

8、n; m+ )m_wr = am.key;fprintf ( fp, %d , m_wr );/ 寫入 TXT中fclose ( fp );/ 直接插入排序/void insert_sort(element a, int n)int i, j;element next;for(i=1; i=0 & next.key =1;i-)ai.key=ai-1.key;k=n/2;while(k=1)for(i=k+1;ia0.key)&(j=0)aj+k.key=aj.key;j=j-k;aj+k=a0;k=k/2;for(i=0;in;i+)ai.key=ai+1.key;printf(輸出希爾排序

9、的結果:n);/快速排序/int hoare(struct element aSIZE,int l,int h)/分區處理函數int i,j;struct element x;i=l;j=h;x.key=ai.key;dowhile(i=x.key)j-;if(ij)ai.key=aj.key;i+;while(ij)&(ai.key=x.key)i+;if(ij)aj.key=ai.key;j-;while(ij);ai.key=x.key;return(i);/堆排序函數/調整堆的函數void heap(struct element aSIZE,int i,int m)/*i是根結點編號,

10、m是以 i為根的子樹的最后一個結點編號*/struct element x;int j;x.key=ai.key;j=2*i;/保存記錄內容/j 為左孩子編號while(j=m)if(jaj+1.key) /當結點 i有左,右兩個孩子時,j取關鍵較小的孩子編號j+;if(aj.keym,以便結束循環ai.key=x.key;/堆排序的主體函數void heapsort(struct element aSIZE,int n)int i,v;struct element x;for(i=n;i0;i-)ai.key=ai-1.key;for(i=n/2;i=1;i-)heap(a,i,n);for

11、(v=n;v=2;v-)x.key=a1.key;a1.key=av.key;av.key=x.key;heap(a,1,v-1);/堆頂堆尾元素交換/這次比上次少處理一個記錄for(i=0;in;i+)ai.key=ai+1.key;for(i=0;in/2;i+)int k;k=ai.key;ai.key=an-i-1.key;an-i-1.key=k;void main()int num,l,h,c;clock_t start, end;c=1;char file150 = 直接插入排序.txt;char file250 = 希爾排序.txt;char file350 = 非遞歸的快速排

12、序.txt;char file450 = 堆排序.txt;printf(*歡迎使用本系統學習各種排序*n);printf(*溫馨提示：首先請生成用于排序的元素，以便進行排序*n);printf(*主菜單*n);printf(*1生成隨機排序元素*n);printf(*printf(*printf(*printf(*printf(*23450直接插入排序希爾排序*n);*n);*n);*n);*n);非遞歸的快速排序堆排序退出printf(*n);while(c!=0)printf(*請輸入0-5進行操作n);scanf(%d,&c);switch(c)case 1:num=creat();pr

13、int(list,num);break;case 2:start = clock();insert_sort(list,num);end = clock();print(list,num);save(list,num, file1) ;printf(The time : %d msn, end - start );break;case 3:start = clock();shell(list,num);end = clock();print(list,num);save(list,num,file2) ;printf(The time : %d msn, end - start );break

14、;case 4:l=0;h=num-1;start = clock();end = clock();printf(輸出遞歸快速排序結果:n);print(list,num);save(list,num,file3);printf(The time : %d msn, end - start );break;case 5:start = clock();heapsort(list,num);end = clock();print(list,num);save(list,num,file4);printf(The time : %d msn, end - start );break;/main e

15、nd六、各種排序算法的性能分析由于程序不能統計出運行各種算法所需要的時間，所以在本程序中以各種算法的時間復雜度來分析各種算法的性能。2. 希爾排序：算法的時間復雜度為 n的 1.2次冪3. 冒泡排序 ：這是最原始，也是眾所周知的最慢的算法了。他的名字的由來因為它的工作看來象是冒泡。算法的時間復雜度為：O(n*n)。當數據為正序，將不會有交換，復雜度為 O(0)。4. 快速排序：算法的平均時間復雜度為：log2(n)*n，所有內部排。5.簡單排序：算法的時間復雜度為：O(n*n)。6.堆排序：算法的時間復雜度為：log2(n)*n綜上：由各種算法的時間復雜度比較可知，堆排序和快速排序是漸進最優的

16、排序算法?？?結1、插入排序（InsertSort）插入排序通過把序列中的值插入一個已經排序好的序列中，直到該序列的結束。插入排序是對冒泡排序的改進。它比冒泡排序快 2 倍。一般不用在數據大于 1000的場合下使用插入排序，或者重復排序超過 200數據項的序列。2、 Shell排序（ShellSort）Shell 排序通過將數據分成不同的組，先對每一組進行排序，然后再對所有的元素 進行一 次插入排序 ，以減 少數據 交換和 移動的次數 。平均 效率是O(nlogn)。其中分組的合理性會對算法產生重要的影響。現在多用 D.E.Knuth的分組方法。Shell排序比冒泡排序快 5倍，比插入排序大致

17、快 2倍。Shell排序比起QuickSort，MergeSort，HeapSort 慢很多。但是它相對比較簡單，它適合于數據量在 5000以下并且速度并不是特別重要的場合。它對于數據量較小的數列重復排序是非常好的。3、快速排序（QuickSort）快速排序是一個就地排序，分而治之，大規模遞歸的算法。從本質上來說，它是歸并排序的就地版本?？焖倥判蚩梢杂上旅嫠牟浇M成。（1） 如果不多于 1個數據，直接返回。（2） 一般選擇序列最左邊的值作為支點數據。（3） 將序列分成 2 部分，一部分都大于支點數據，另外一部分都小于支點數據。（4） 對兩邊利用遞歸排序數列?？焖倥判虮却蟛糠峙判蛩惴ǘ家?。盡管我

18、們可以在某些特殊的情況下寫出比快速排序快的算法，但是就通常情況而言，沒有比它更快的了?？焖倥判蚴沁f歸的，對于內存非常有限的機器來說，它不是一個好的選擇。4、堆排序（HeapSort）或者多維的暫存數組。這對于數據量非常巨大的序列是合適的。比如超過數百萬條記錄，因為快速排序，歸并排序都使用遞歸來設計算法，在數據量非常大的時候，可能會發生堆棧溢出錯誤。堆排序會將所有的數據建成一個堆，最大的數據在堆頂，然后將堆頂數據和序列的最后一個數據交換。接下來再次重建堆，交換數據，依次下去，就可以排序所有的數據。心 得 體 會說實話，本次做數據結構課程設計，時間非常緊，在課間我做的少，基本上都是在課后把本次課程

19、設計做出來的。我們的課程設計安排在 17、18、19 周去做。但是在 16 周的星期 1、2 的上午和星期 4 的下午我都有考試，因此在星期 1 的上午的考試結束后，在下午的課程設計的課上我都在復習第二天要考試的內容；而在星期2 上午考試結束后，星期 2 下午和星期三我都在復習星期 4 要考試的內容。所以，我從星期 1 到星期 4 的課程設計課我基本上什么也沒有做。我真正開始做課程設計是從星期 5 上午在寢室開始的。做了星期 5 一天，我才把方案設計、程序操作過程、程序流程圖和很少一部分程序源代碼做好，然后在寢室花了整整一周才把所有內容都寫完。然后星期 2 花了一整天的時間才整理出來這個課程設

20、計的論文。寫完后，我心里有兩個感受：第一是：累！我差不多花了整整 20 天時間來寫這個課程設計，在這其間，我只有在吃飯的時候看會兒電影，其余的時候我基本上都在做課程設計（睡覺的時間除外）。第二是：滿足！這個課程設計是我從搜集資料、整理資料、到寫好這份課程設計都是我一個人完成的，絕沒有抄襲別人的。通過這次課程設計，我收獲頗多。原來上課時沒有聽懂的地方，通過這次課程設計，我自己翻書，查資料，我基本上都理解了；原來疑惑的地方現在也明白了！自從拿到題目到完成整個編程，從理論到實踐，在兩周多的時間里，通過查資料，向老師和同學請教，讓我學到很多很多的東西，同時鞏固了以前所學過的知識。在測試階段中發現了幾處

21、錯誤導致程序運行不正確，去上網查找相關的資料,向老師請教，又同學一起討論。通過耐心的分析源代碼終于編好了一個完整無誤的程序。在這次的算法與數據結構程序設計中遇到了現實編程中必然見到的問題，通過對這些問題分析和解決積累了編程的實踐經驗。在實際的編程操作中發現自己對計算機編程語言知識的不足?？傊?，通過這次課程設計，我拓寬了知識面，鍛煉了能力。尤其是觀察、分析和解決問題的實際工作能力。從課堂走向實踐。通過課程設計，讓我們找出自身狀況與實際需要的差距，并在以后的學習期間及時補充相關知識。參 考 文 獻【1】嚴蔚敏，吳偉民.數據結構（C .清華大學出版社【2】鄧均輝. 數據結構與算法.清華大學出版社【3】朱站立，張選平，韓家新.數據結構-使用 c 語言.西安交通大學出版社【4】譚浩強.c 語言程序設計. 清華大學出版社.【5】 嚴蔚敏