北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn) 第三次實(shí)驗(yàn) 排序

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告1實(shí)驗(yàn)要求(1)實(shí)驗(yàn)?zāi)康耐ㄟ^選擇下面兩個題目之一，學(xué)習(xí)、實(shí)現(xiàn)、對比各種排序算法，掌握各種排序算法的優(yōu)劣，以及各種算法使用的情況。(2)實(shí)驗(yàn)內(nèi)容使用簡單數(shù)組實(shí)現(xiàn)下面各種排序算法，并進(jìn)行比較。排序算法：1、插入排序2、希爾排序3、冒泡排序4、快速排序5、簡單選擇排序6、堆排序（選作）7、歸并排序（選作）8、基數(shù)排序（選作）9、其他要求：1、測試數(shù)據(jù)分成三類：正序、逆序、隨機(jī)數(shù)據(jù)2、對于這三類數(shù)據(jù)，比較上述排序算法中關(guān)鍵字的比較次數(shù)和移動次數(shù)（其中關(guān)鍵字交換計(jì)為3次移動）。3、對于這三類數(shù)據(jù)，比較上述排序算法中不同算法的執(zhí)行時間，精確到微秒（選作）4、對2和3的結(jié)果進(jìn)行分析，驗(yàn)證上述

2、各種算法的時間復(fù)雜度編寫測試main()函數(shù)測試排序算法的正確性。 2. 程序分析2.1 存儲結(jié)構(gòu) 順序表: 示意圖：a0a1a2a3a4a5a6a7 2.2 關(guān)鍵算法分析（1） 測試數(shù)據(jù)的產(chǎn)生：正序、逆序、隨機(jī)數(shù)據(jù)用兩個數(shù)組實(shí)現(xiàn)亂序、順序以及逆序數(shù)據(jù)的排序。基本思想為：隨機(jī)序列產(chǎn)生一個指定長度的亂序序列，然后通過memcpy()函數(shù)拷貝到第二個數(shù)組里，第二個數(shù)組作為亂序序列的保存數(shù)組，每次對第一個數(shù)組進(jìn)行排序，之后拷貝第二個數(shù)組中的亂序序列到第一個數(shù)組，實(shí)現(xiàn)各次亂序排列。只要算法正確（第一步可以檢驗(yàn)），之后順序排列只需反復(fù)對第一個數(shù)組進(jìn)行操作即可，再后用第二個數(shù)組保存逆序數(shù)組，然后同樣在每次

3、排序之后復(fù)制第二數(shù)組存儲的亂序序列到第一組，對第一組反復(fù)排序即可。<1> pRandom1=new long intMax+1;pRandom2=new long intMax+1;<2> srand(unsigned)time(NULL); for(int i = 1; i <= Max;i+ ) pRandom2i=rand();<3> memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(long int);（2） 排序算法：<1>插入排序：依次將待排序的序列中的每一個記錄插入到先前排序好的序

4、列中，直到全部記錄排序完畢。/1/int j=0;/2/ for(int i =2; i <= Max;i+) parray0=parrayi;comparetimes0+; /4/parrayj+1=parray0;movetimes0+=2;示意圖：r1,r2,r3,ri-1,ri,ri+1,rn 有序區(qū) 待插入 無序區(qū)<2>希爾排序：先將整個序列分割成若干個子列，分別在各個子列中運(yùn)用直接插入排序，待整個序列基本有序時，再對全體記錄進(jìn)行一次直接插入排序。int Sort:ShellSort(long int parray)int j=0;for(int d=Max/2;d

5、>=1;d/=2)for(int i=d+1;i<=Max;i+) parray0=parrayi;comparetimes1+;for(j=i-d;j>0 && parray0<parrayj;j-=d) parrayj+d=parrayj;movetimes1+;parrayj+d=parray0;movetimes1+=2;return 0;<3>冒泡排序：兩兩比較相鄰記錄的關(guān)鍵碼，如果反序則交換，直到?jīng)]有反序記錄為止。int Sort:BubbleSort(long int parray) int exchange=Max;int b

6、ound,j;while(exchange) bound=exchange;exchange=0;for(j=1;j<bound;j+) comparetimes2+;if(parrayj>parrayj+1) parray0=parrayj;parrayj=parrayj+1;parrayj+1=parray0;exchange=j;movetimes2+=3;return 0;示意圖：r1,r2,r3,ri-1,ri,ri+1,rn 反序則交換 有序區(qū)<4>快速排序：首先選擇一個基準(zhǔn)，將記錄分割為兩部分，左支小于或等于基準(zhǔn)，右支則大于基準(zhǔn)，然后對兩部分重復(fù)上述過程，

7、直至整個序列排序完成。int Sort:QuickSort(long int parray)QuickSortRecursion(parray,1, Max);return 0;int Sort:QuickSortRecursion(long int parray, int first=1, int end=Max)if (first<end) int pivot=QuickSortPatition(parray, first, end); QuickSortRecursion(parray, first, pivot-1);/左側(cè)子序列排序 QuickSortRecursion(par

8、ray, pivot+1, end); /右側(cè)子序列排序return 0;int Sort:QuickSortPatition(long int r, int first, int end )int i=first;int j=end;int temp;while (i<j) while (i<j && ri<= rj) j-; comparetimes3+; /右側(cè)掃描 if (i<j) temp=ri; /將較小記錄交換到前面 ri=rj; rj=temp; i+; movetimes3+=3; while (i<j && ri

9、<= rj) i+; comparetimes3+; /左側(cè)掃描 if (i<j) temp=rj; rj=ri; ri=temp; /將較大記錄交換到后面 j-; movetimes3+=3; return i; /i為軸值記錄的最終位置示意圖：r1,r2,r3,ri-1,ri,ri+1,rn r<ri 軸值 r>ri<5>選擇排序：從待排序的記錄序列中選擇關(guān)鍵碼最小（或最大）的記錄并將它與序列中的第一個記錄交換位置；然后從不包括第一個位置上的記錄序列中選擇關(guān)鍵碼最?。ɑ蜃畲螅┑挠涗洸⑺c序列中的第二個記錄交換位置；如此重復(fù)，直到序列中只剩下一個記錄為止

10、。int Sort:SelectSort(long int parray)int i,j,index,temp; for (i=1; i<Max; i+) /對n個記錄進(jìn)行n-1趟簡單選擇排序 index=i; for (j=i+1; j<=Max; j+) comparetimes4+;/在無序區(qū)中選取最小記錄 if (parrayj<parrayindex) index=j; if (index!=i) temp=parrayi; parrayi=parrayindex; parrayindex=temp; movetimes4+=3; 示意圖：r1,r2,r3,ri-1

11、,ri,ri+1,rn 反序則交換 有序區(qū)<6>堆排序：通過建立大根堆或者小根堆，取出根節(jié)點(diǎn)，反復(fù)調(diào)整堆使之保持大根堆或者小根堆，直至最后序列有序。int Sort:HeapSort(long int parray)int i;for (i=Max/2; i>=1; i-)HeapSortSift(parray, i, Max) ; for (i=1; i<Max; i+) parray0=parrayMax-i+1; parrayMax-i+1=parray1; parray1=parray0; movetimes5+=3; HeapSortSift(parray,

12、1, Max-i); return 0;void Sort:HeapSortSift(long int parray, int k, int m)int i,j;i=k;j=2*i; /置i為要篩的結(jié)點(diǎn)，j為i的左孩子 while (j<=m) /篩選還沒有進(jìn)行到葉子 if (j<m && parrayj<parrayj+1) j+; comparetimes5+; /比較i的左右孩子，j為較大者 if (parrayi>parrayj) comparetimes5+; break; /根結(jié)點(diǎn)已經(jīng)大于左右孩子中的較大者else parray0=parra

13、yi; parrayi=parrayj; parrayj=parray0; movetimes5+=3; i=j; j=2*i; /被篩結(jié)點(diǎn)位于原來結(jié)點(diǎn)j的位置<7>歸并排序：將若干個有序序列兩兩歸并，直至所有待排序的記錄都在一個有序序列為止。int Sort:MergeSort(long int parray)long int r1Max+1;int h(1); while (h<Max) MergePass(parray, r1, h); /歸并 h=2*h; MergePass(r1, parray, h); h=2*h; return 0;void Sort:Merg

14、e(long int parray, long int r1, int s, int m, int t) /一次歸并int i=s;int j=m+1;int k=s; while (i<=m && j<=t) comparetimes6+; movetimes6+; if (parrayi<=parrayj) r1k+=parrayi+; else r1k+=parrayj+; if (i<=m) while (i<=m) r1k+=parrayi+; movetimes6+; else while (j<=t) r1k+=parrayj+

15、; movetimes6+; void Sort:MergePass(long int parray, long int r1, int h) /一趟歸并int i(1),k; while (i<=Max-2*h+1) Merge(parray, r1, i, i+h-1, i+2*h-1); i+=2*h; if (i<Max-h+1) Merge(parray, r1, i, i+h-1, Max); else for (k=i; k<=Max; k+) r1k=parrayk;movetimes6+;（3）比較上述排序算法中關(guān)鍵字的比較次數(shù)和移動次數(shù)：使用函數(shù)指針數(shù)組，

16、分別指向各排序函數(shù)的入口地址，然后在Statistics()函數(shù)中加以調(diào)用，使得排序函數(shù)運(yùn)行在統(tǒng)計(jì)時間函數(shù)之間，這樣使用一個for語句即可實(shí)現(xiàn)算法的一次性調(diào)用、時間統(tǒng)計(jì)、移動次數(shù)和比較次數(shù)統(tǒng)計(jì)。void Statistics(Sort &obj,int i,int j)obj.startTime=obj.GetNowTime();(obj.*pFunctioni)(obj.pRandom1);obj.endTime=obj.GetNowTime();obj.runtimeij=obj.endTime-obj.startTime;建立兩個數(shù)組分別統(tǒng)計(jì)運(yùn)行次數(shù)，再統(tǒng)一使用一個數(shù)組記錄七種算

17、法在三種不同數(shù)據(jù)情況下的移動次數(shù)和交換次數(shù)。在分別運(yùn)行亂序、順序和逆序數(shù)組排序時取出前兩個數(shù)組的值寫入第三個數(shù)組，然后置零繼續(xù)統(tǒng)計(jì)。(4)算法的執(zhí)行時間：獲取當(dāng)前系統(tǒng)時間，精確到微秒，分別在代碼運(yùn)行前后調(diào)用記錄前后時間，再相減即可得到代碼運(yùn)行時間。此處調(diào)用函數(shù)QueryPerformanceCounter()用于得到高精度計(jì)時器的值。long double Sort:GetNowT33ime()LARGE_INTEGER litmp; LONG64 QPart; QueryPerformanceCounter(&litmp);QPart=litmp.QuadPart;return (l

18、ong double)QPart;（5）各種算法的時間復(fù)雜度與空間復(fù)雜度：排序方法平均情況最好情況最壞情況輔助空間直接插入排序O(n2)O(n)O(n2)O(1)希爾排序O(nlog2n)O(n2)O(n1.3)O(n2)O(1)起泡排序O(n2)O (n)O(n2)O(1)快速排序O(nlog2n)O(nlog2n)O(n2)O(log2n) O(n)簡單選擇排序O(n2)O(n2)O(n2)O(1)堆排序O(nlog2n)O(nlog2n)O (nlog2n)O(1)歸并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)3. 程序運(yùn)行結(jié)果（1）流程圖：開始產(chǎn)生隨機(jī)數(shù)組亂序數(shù)

19、組七種排序和統(tǒng)計(jì)順序數(shù)組七種排序和統(tǒng)計(jì)逆序數(shù)組七種排序和統(tǒng)計(jì)輸出統(tǒng)計(jì)結(jié)果結(jié) 束（2）測試條件：本實(shí)驗(yàn)中隨機(jī)產(chǎn)生的數(shù)據(jù)量為50（3）測試結(jié)論運(yùn)行結(jié)果：分析：<1>多次運(yùn)行之后統(tǒng)計(jì)，從亂序的時間消耗來看，基本符合理論分析<2>由于加入了統(tǒng)計(jì)次數(shù)的代碼，勢必增加時間開銷，這樣統(tǒng)計(jì)出來的時間將有一定的誤差。假若比較次數(shù)和移動次數(shù)相差較多，則將產(chǎn)生較大的實(shí)驗(yàn)誤差。4. 總結(jié)（1） 調(diào)試時出現(xiàn)的問題及解決的方法在調(diào)試過程中，我遇到了一些困難。例如：循環(huán)的條件控制不正確。通過云閱讀書本，我發(fā)現(xiàn)，錯誤的原因是沒能正確理解概念。經(jīng)過反復(fù)的嘗試，不斷對知識的理解，最終我將錯誤改正。（2）

20、心得體會通過此次實(shí)驗(yàn)，我對各這種排序有了更加直觀和深刻的認(rèn)識，對書本上介紹的各種算法有了更熟練的掌握。在編程的過程中，我也遇到了一些困難，多是有關(guān)c+語法等方面的困難，通過不斷的調(diào)試與查詢資料，我對c+的一些語法更加了解，這對我以后的編程有很大的幫助。（3） 下一步的改進(jìn)本程序代碼設(shè)計(jì)時運(yùn)用了遞歸的調(diào)用方式，效率還可以通過將其轉(zhuǎn)換為棧模擬的方式得以提高。源代碼：由3部分組成/main.cpp#include<iostream>using namespace std;#include"Sort.h"#include<time.h>#include<

21、;string.h>static int (Sort:*pFunction7)(long int )=&Sort:InsertSort,&Sort:ShellSort,&Sort:BubbleSort,&Sort:QuickSort,&Sort:SelectSort,&Sort:HeapSort,&Sort:MergeSort;char *funcName7="1、插入排序:","2、希爾排序:","3、冒泡排序:","4、快速排序:","5、

22、選擇排序:","6、堆 排 序:","7、歸并排序:"/*統(tǒng)計(jì)時間函數(shù)*/void Statistics(Sort &obj,int i,int j)obj.startTime=obj.GetNowTime();(obj.*pFunctioni)(obj.pRandom1);obj.endTime=obj.GetNowTime();obj.runtimeij=obj.endTime-obj.startTime;/*主調(diào)函數(shù)*/int main()Sort obj;obj.CreateData();memcpy(obj.pRandom1,

23、obj.pRandom2,(Max+1)*sizeof(long int);int i(0),j(0);/*亂序序列*/obj.SetTimesZero();for(i=0;i<7;i+)Statistics(obj,i,0);cout<<funcNamei<<"n"/輸出各排序結(jié)果obj.PrintArray(obj.pRandom1);if(i!=6) memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(long int);obj.RecordTimes(0);/*順序序列*/obj.SetTim

24、esZero();for( i=0;i<7;i+)Statistics(obj,i,1);obj.RecordTimes(2);/*逆序序列*/obj.SetTimesZero();for(i=1;i<=Max;i+)obj.pRandom2i=obj.pRandom1Max+1-i;memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(long int);for(i=0;i<7;i+)Statistics(obj,i,2);memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(long in

25、t);obj.RecordTimes(4);/*統(tǒng)計(jì)排序數(shù)據(jù)*/obj.PrintStatistics(funcName);return 0;/Sort.hconst int Max =50;class Sortpublic:Sort();Sort();void CreateData(void);int InsertSort(long int );int ShellSort(long int );int BubbleSort(long int );int QuickSort(long int );int QuickSortRecursion(long int , int ,int);int Q

26、uickSortPatition(long int , int , int );int SelectSort(long int );int HeapSort(long int );/堆排序void HeapSortSift(long int , int , int );/篩選int MergeSort(long int );void Merge(long int ,long int , int , int , int );/歸并排序void MergePass(long int ,long int , int );long double GetNowTime(void);void PrintA

27、rray(long int*);void SetTimesZero(void);void RecordTimes(int);friend void Statistics(Sort &,int ,int);void PrintStatistics(char *);friend int main(void);private:long int *pRandom1;long int *pRandom2;long double runtime73;int comparetimes7; int movetimes7;int timestable76;long double startTime,en

28、dTime;/Function.cpp#include"Sort.h"#include<iostream>#include <stdlib.h>#include <time.h>#include<string.h>#include<cstdio>#include<windows.h>#include<string>#include<iomanip>using namespace std;/*構(gòu)造函數(shù)*/Sort:Sort()memset(timestable,0,sizeof(i

29、nt)*7*6);/*構(gòu)造數(shù)組*/void Sort:CreateData()pRandom1=new long intMax+1;pRandom2=new long intMax+1;srand(unsigned)time(NULL); for(int i = 1; i <= Max;i+ )pRandom2i=rand();cout<<"隨機(jī)亂序數(shù)組如下：n"/輸出原始數(shù)組PrintArray(pRandom2);/*簡單插入排序*/int Sort:InsertSort(long int parray)int j=0;for(int i =2; i

30、<= Max;i+)parray0=parrayi;comparetimes0+;/比較次數(shù)統(tǒng)計(jì)for(j=i-1;parray0<parrayj;j-)parrayj+1=parrayj;movetimes0+;/移動次數(shù)統(tǒng)計(jì)parrayj+1=parray0;movetimes0+=2;return 0;/*希爾排序*/int Sort:ShellSort(long int parray)int j=0;for(int d=Max/2;d>=1;d/=2)for(int i=d+1;i<=Max;i+)parray0=parrayi;comparetimes1+;f

31、or(j=i-d;j>0 && parray0<parrayj;j-=d)parrayj+d=parrayj;movetimes1+;parrayj+d=parray0;movetimes1+=2;return 0;/*冒泡排序*/int Sort:BubbleSort(long int parray)int exchange=Max;int bound,j;while(exchange)bound=exchange;exchange=0;for(j=1;j<bound;j+)comparetimes2+;if(parrayj>parrayj+1)par

32、ray0=parrayj;parrayj=parrayj+1;parrayj+1=parray0;exchange=j;movetimes2+=3;return 0;/*快速排序*/int Sort:QuickSort(long int parray)QuickSortRecursion(parray,1, Max);return 0;int Sort:QuickSortRecursion(long int parray, int first=1, int end=Max)if (first<end) int pivot=QuickSortPatition(parray, first,

33、end); QuickSortRecursion(parray, first, pivot-1);/左側(cè)子序列排序 QuickSortRecursion(parray, pivot+1, end); /右側(cè)子序列排序return 0;int Sort:QuickSortPatition(long int r, int first, int end )int i=first;int j=end;int temp; while (i<j) while (i<j && ri<= rj) j-; comparetimes3+; /右側(cè)掃描 if (i<j) te

34、mp=ri; /將較小記錄交換到前面 ri=rj; rj=temp; i+; movetimes3+=3; while (i<j && ri<= rj) i+; comparetimes3+; /左側(cè)掃描 if (i<j) temp=rj; rj=ri; ri=temp; /將較大記錄交換到后面 j-; movetimes3+=3; return i; /i為軸值記錄的最終位置/*選擇排序*/int Sort:SelectSort(long int parray)int i,j,index,temp; for (i=1; i<Max; i+) /對n個記

35、錄進(jìn)行n-1趟簡單選擇排序 index=i; for (j=i+1; j<=Max; j+) comparetimes4+;/在無序區(qū)中選取最小記錄 if (parrayj<parrayindex) index=j; if (index!=i) temp=parrayi; parrayi=parrayindex; parrayindex=temp; movetimes4+=3; return 0;/*堆排序*/int Sort:HeapSort(long int parray)int i;for (i=Max/2; i>=1; i-)HeapSortSift(parray,

36、i, Max) ; for (i=1; i<Max; i+) parray0=parrayMax-i+1; parrayMax-i+1=parray1; parray1=parray0; movetimes5+=3; HeapSortSift(parray, 1, Max-i); return 0;void Sort:HeapSortSift(long int parray, int k, int m)int i,j;i=k;j=2*i; /置i為要篩的結(jié)點(diǎn)，j為i的左孩子 while (j<=m) /篩選還沒有進(jìn)行到葉子 if (j<m && parrayj

37、<parrayj+1) j+; comparetimes5+; /比較i的左右孩子，j為較大者 if (parrayi>parrayj) comparetimes5+; break; /根結(jié)點(diǎn)已經(jīng)大于左右孩子中的較大者else parray0=parrayi; parrayi=parrayj; parrayj=parray0; movetimes5+=3; i=j; j=2*i; /被篩結(jié)點(diǎn)位于原來結(jié)點(diǎn)j的位置 /*歸并排序*/int Sort:MergeSort(long int parray)long int r1Max+1;int h(1); while (h<Max)

38、 MergePass(parray, r1, h); /歸并 h=2*h; MergePass(r1, parray, h); h=2*h; return 0;void Sort:Merge(long int parray, long int r1, int s, int m, int t) /一次歸并int i=s;int j=m+1;int k=s; while (i<=m && j<=t) comparetimes6+; movetimes6+; if (parrayi<=parrayj) r1k+=parrayi+; else r1k+=parrayj

39、+; if (i<=m) while (i<=m) r1k+=parrayi+; movetimes6+; else while (j<=t) r1k+=parrayj+; movetimes6+; void Sort:MergePass(long int parray, long int r1, int h) /一趟歸并int i(1),k; while (i<=Max-2*h+1) Merge(parray, r1, i, i+h-1, i+2*h-1); i+=2*h; if (i<Max-h+1) Merge(parray, r1, i, i+h-1, M

40、ax); else for (k=i; k<=Max; k+) r1k=parrayk;movetimes6+;/*獲取當(dāng)前時間*/long double Sort:GetNowTime()LARGE_INTEGER litmp; LONG64 QPart; QueryPerformanceCounter(&litmp);QPart=litmp.QuadPart;return (long double)QPart;/*打印數(shù)組*/void Sort:PrintArray(long int *pRandom)for(int j=1;j<=Max;j+)cout<<pRandomj<<'t'cout<<endl;/*數(shù)組置零函數(shù)*/void Sort:SetTimesZero()