各種排序?qū)嶒?yàn)報(bào)告(編輯修改稿)
2025-04-03 21:43 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 +]=su[i]。}k=0。for(i=0。 i10。 i++){if(b[i]!=0){for(j=0。 jb[i]。 j++){su[k++]=a[i][j]。}}}⑴算法思想：由于折半插入排序的基本操作是在一個(gè)有序表中進(jìn)行查找和插入，這個(gè)“查找”操作可利用折半查找來(lái)實(shí)現(xiàn)，由此進(jìn)行的插入排序稱之為折半插入排序。折半插入排序所需附加存儲(chǔ)空間和直接插入排序相同，從時(shí)間上比較，這般插入排序僅減少了關(guān)鍵字間的比較次數(shù)，而記錄的移動(dòng)次數(shù) 不變。因此，這般插入排序的時(shí)間復(fù)雜度仍為O（n2）。 ⑵程序?qū)崿F(xiàn)及核心代碼的注釋：for(i=1。 iN。 i++){temp=su[i]。low=0。high=i1。while(low=high){m=(low+high)/2。if(tempsu[m])high=m1。elselow=m+1。}for(j=i。 jhigh+1。 j)su[j]=su[j1]。su[high+1]=temp。}⑴算法思想：直接插入排序是一種最簡(jiǎn)單的排序方法，它的基本操作是將一個(gè)記錄插入到一個(gè)已排好序的有序表中，從而得到一個(gè)新的、記錄數(shù)增一的有序表。在自i1起往前搜索的過(guò)程中，可以同時(shí)后移記錄。整個(gè)排序過(guò)程為進(jìn)行n1趟插入，即：先將序列中的第一個(gè)記錄看成是一個(gè)有序的子序列，然后從第二個(gè)記錄起逐個(gè)進(jìn)行插入，直至整個(gè)序列變成按關(guān)鍵字非遞減有序序列為止。⑵程序?qū)崿F(xiàn)及核心代碼的注釋：for(i=1。 iN。 i++){head=su[i]。for(j=0。 ji。 j++){if(headsu[j]){for(k=i。 kj。 k){su[k]=su[k1]。}su[j]=head。break。}}}詳細(xì)設(shè)計(jì)程序代碼:include iostreaminclude cstdioinclude cstdlibinclude algorithminclude cmathdefine H(X) (X%10)define HH(X) (X%100/10)define HHH(X) (X/100)using namespace std。//int ss[10000]= {32,37,64,87,16,12,24,32}。 //將要排序的數(shù)組int ss[10000]= {372,209,53,942,547,234,645,468,7,83}。 //將要排序的數(shù)組 int su[10000]。 //將要排序的數(shù)組int N=10。 //數(shù)組的長(zhǎng)度void input() //數(shù)組的輸入函數(shù){cout請(qǐng)輸入要排序的數(shù)組的長(zhǎng)度N：。cinN。cout請(qǐng)輸入需要排序的數(shù)組：endl。for(int i=0。 iN。 i++)cinss[i]。}void output() //數(shù)組的輸出函數(shù){for(int i=0。 iN。 i++)coutsu[i] 。coutendl。}void head(int i,int m) //堆排序的一個(gè)函數(shù){int j。int temp。temp=su[i]。for(j=2*i+1。 j=m。 j=j*2+1){if(jm1(su[j]su[j+1]))j++。if(temp=su[j])break。su[i]=su[j]。i=j。}su[i]=temp。}void dpx() //堆排序{int i,temp。cout排序之前的數(shù)組為：endl。output()。for(i=N/21。 i=0。 i){head(i,N)。}for(i=N1。 i0。 i){temp=su[i]。su[i]=su[0]。su[0]=temp。head(0,i1)。}cout排序之后的數(shù)組為：endl。output()。}int is2[1000]。void bing(int low,int mid,int high){int i=low,j=mid+1,k=low。while(i=midj=high)if(su[i]=su[j]) // 此處為排序順序的關(guān)鍵，用小于表示從小到大排序is2[k++]=su[i++]。elseis2[k++]=su[j++]。while(i=mid)is2[k++]=su[i++]。while(j=high)is2[k++]=su[j++]。for(i=low。 i=high。 i++) // 寫(xiě)回原數(shù)組su[i]=is2[i]。}void g(int a,int b){if(ab){int mid=(a+b)/2。g(a,mid)。g(mid+1,b)。bing(a,mid,b)。}}void gbpx() //歸 并 排 序{cout排序之前的數(shù)組為：endl。output()。g(0,N1)。cout排序之后的數(shù)組為：endl。output()。}void xepx() //希 爾 排 序{int i,j,temp。int m=N。cout排序之前的數(shù)組為：end
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1