大數(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ù),以取得直觀感受.三、流程圖開始序簡(jiǎn)單項(xiàng)選擇擇排序直接插入排希爾排結(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

2、;for(int j=0;j<i;j+)while(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

3、-) aj=aj-1;change0+;)aj=a0;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<hig

4、h)(while(low<high&&ahigh>=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

5、(a,low,high); quicksort(a,low,key-1);quicksort(a,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

6、,aN;k=int(n/2);for(i=0;i<n;i+)(ai=si;)for(int gap = n/2; gap > 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

7、= 2 * i; j <len; j *= 2)(if(j < len && arrayj < 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+;彈出最大

8、值,重新對(duì)i-1個(gè)元素建堆heap_adjust(a,0,i-1);) void CMyDlg:OnButton1()(/ TODO: Add your control notification handler code here UpdateData(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_shuj

9、u1+=stri;)insertsort(s);m_zhijie1=compare0;m_zhijie2=change0;quicksort(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);五、調(diào)試過(guò)程對(duì)于算法的設(shè)計(jì),除了希爾排序和堆排序之外,都比擬簡(jiǎn)單,要注意每種排序的起