數(shù)據(jù)結(jié)構(gòu)：簡(jiǎn)單選擇,直接插入,快速排序,冒泡排序希爾排序,堆排序算法比較平臺(tái)

1、一、試驗(yàn)內(nèi)容內(nèi)部排序算法效率比較平臺(tái)的設(shè)計(jì)與實(shí)現(xiàn)二、試驗(yàn)?zāi)康膯?wèn)題描述：各種內(nèi)部排序算法的時(shí)間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時(shí)間的階，或大概執(zhí)行時(shí)間。試通過(guò)隨機(jī)的數(shù)據(jù)比較幾種主要的基本算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)，以取得直觀感受。開(kāi)始三、流程圖 冒泡排序J=N-1I=0ai>ai+1 否 是ai與ai+1交換 I+ I=j 否J=J-1結(jié)束J=0?否開(kāi) 始 簡(jiǎn)單選擇排序int i=1;假 i<L.length真int j=i;k=i+1 假k<L.lenth真L.rj.key<L.rk.key j=k; k+ i!=j 假真 L.ri L.rji+結(jié) 束 直接插入

2、排序開(kāi)始i=2假i<=L.length真L.ri.key<L.ri-1.key假真L.r0=L.ri；L.ri=L.ri-1；j=i-2；假L.r0.key<L.rj.key真L.rj+1=L.rj；-j；L.rj+1=L.r0+i結(jié)束 希爾排序開(kāi)始k=0假k<t真ShellInsert(&L,dltak,&r);i=dk+1;假i<=L.length真假L.ri.key<L.ri-dk.key真L.r0=L.ri；j=i-dk；j>0&&L.r0.key<L.rj.key假真L.rj+dk=L.rj；j-=dk；

3、L.rj+dk=L.r0+i+k結(jié)束 快速排序開(kāi)始Low<high真-high假+low真Low<high&&L.rhigh.key<=pivotkey77L.rlow=L.rhighLow<high&&L.rhigh.key>=pivotkey77真L.r0=L.rlowPivotkey=L.rlow.key假L.rhigh=L.rlow結(jié)束L,low,high假開(kāi)始真Low<highL,low=pivotloc+1,high=highPivotloc=partioion(L,low,high),low=low,high=p

4、ivotloc-1;Low<highL，low，high假真假Pivotloc=partioion(L,low,high),low=low,high=pivotloc-1;QSort(L,low,pivotloc-1)結(jié)束四、源程序代碼#define N 10int compare6=0,0,0,0,0,0,change6=0,0,0,0,0,0;void input(int s)int testN; srand(unsigned)time(NULL); for(int i=0;i<N;i+) testi=rand()%100; for(int j=0;j<i;j+) whi

5、le(testj=testi) testi=rand()%N; j=0; for(i=0;i<=N-1;i+)si=testi;void swap(int &a,int &b) int tmp; tmp=a; a=b; b=tmp;void insertsort(int s)int i,j;int aN+1;for(i=1;i<=N;i+)ai=si-1;for(i=2;i<=N;i+)a0=ai;for(j=i;j>0&&a0<aj-1&&(+compare0);j-)aj=aj-1;change0+;aj=a0;

6、change0+;void bubble_sort(int s,int n)int i,j,temp,aN;for(i=0;i<n;i+)ai=si;for(i=0;i<n-1;i+)for(j=0;j<n-i-1;j+)compare1+;if(aj > aj+1)temp = aj;aj = aj+1;aj+1 = temp;change1+;int partition(int a,int low,int high)int t,key;t=alow;key=alow;while(low<high)while(low<high&&ahigh

7、>=key)high-;+compare2;if(low<high)alow=ahigh;low+;change2+;while(low<high&&alow<=key)low+;+compare2;if(low<high)ahigh=alow;high-;change2+;alow=t;return low;void quicksort(int a,int low,int high)int key;if(low<high)key=partition(a,low,high);quicksort(a,low,key-1);quicksort(a

8、,key+1,high);void selectsort(int s,int n)int i,j,k,aN;int t;for(i=0;i<n;i+)ai=si;for(i=0;i<n-1;i+)j=i;for(k=i+1;k<=n-1;k+)if(ak<aj&&(+compare3)j=k;if(j!=i)t=ai;ai=aj;aj=t;change3+;void shellinsertsort(int s,int n)int i,k,aN;k=int(n/2);for(i=0;i<n;i+)ai=si;for(int gap = n/2; ga

9、p > 0; gap /= 2) for(int i = gap; i < n; i+) int tmp = ai; int j = i; for(; j > 0 && tmp < aj-gap; j -= gap)aj = aj-gap; compare4+;aj = tmp;change4+; void heap_adjust(int array,int i,int len) int rc = arrayi; for(int j = 2 * i; j <len; j *= 2) if(j < len && arrayj &

10、lt; arrayj+1) j+;compare5+;if(rc >= arrayj) break; arrayi = arrayj; i = j; arrayi = rc;void heap_sort(int a,int len) int i; for(i = (len-1)/2; i >= 0; i-) heap_adjust(a,i,len); for( i = (len-1); i > 0; i-) swap(a0,ai);change5+;/彈出最大值，重新對(duì)i-1個(gè)元素建堆 heap_adjust(a,0,i-1); void CMyDlg:OnButton1()

11、 / TODO: Add your control notification handler code hereUpdateData(TRUE);int s10,a10;input(s);for(int i=0;i<N;i+)ai=si;CString str100;for(i=0;i<100;i+)stri=ai;for(i=0;i <N;i+) stri.Format("%i,",ai); /把整型數(shù)組添加到字符串 m_shuju1+=stri;insertsort(s);m_zhijie1=compare0;m_zhijie2=change0;qui

12、cksort(a,0,N-1);m_kuaisu1=compare2;m_kuaisu2=change2;selectsort(s,N);m_jiandan1=compare3;m_jiandan2=change3;shellinsertsort(s,N);m_xier1=compare4;m_xier2=change4;heap_sort(a,N);m_dui1=compare5;m_dui2=change5;bubble_sort(s,N);m_maopao1=compare1;m_maopao2=change1;CString str2100;for(i=0;i<100;i+)str2i=si;for(i=0;i <N;i+) str2i.Format("%i,",ai); /把整型數(shù)組添加到字符串 m_shuju2+=str2i;UpdateData(FALSE