數據結構實驗報告

實驗目的:

通過本次實驗，了解算法復雜度的分析方法，掌握遞歸算法時間復雜度的遞推計算過程。

實驗內容：

二路歸并排序的算法設計和復雜度分析

實驗過程：

1.算法設計

第一步，首先要將數組進行劃分，假設等待排序的數組是A[SIZE]，我們每次從數組的中間開始劃分。

1).假設等待劃分的數組是A{high …low} (是A中的一小段)，劃分點是它的中點，mid=(low+high)/2

2).如果數組段只剩下一個元素，比如A[5…5],劃分出來也是(5+5)/2=5,A[5…5]也是它本身。

3).如果數組段是奇數項。比如A[3…5]，（3+5）/2=4,劃分為了A[3…4]，A[5…5]

4).如果數組段是偶數段，比如A[2...5],(2+5)/2=3(因為是int),劃分為了A[2，3]，A[4…5]，均分

第二步，劃分必定是一遞歸的操作，因此設計一個類似于二叉樹遍歷的遞歸代碼。

1).函數名是mergeSort(A[],int low, int high),每次對A[low,high]進行劃分，劃分為A[low…mid],A[mid+1,high],然后再對這兩段數組進行遞歸的劃分。

2).劃分到單一元素的時候，進行合并操作

第三步，合并操作

2.程序清單

#include<stdio.h>
#include<malloc.h>
void disp(int a[],int n){int i;for(i=0;i<n;i++)printf("%d",a[i]);printf("\n");
}
void Merge(int a[],int low,int mid,int high){int * tmpa;int i=low,j=mid+1,k=0;tmpa=(int * )malloc((high-low+1)*sizeof(int));while (i<=mid&&j<=high)if(a[i]<=a[j]){tmpa[k]=a[i];i++;k++;}else{tmpa[k]=a[j];j++;k++;}while(i<=mid){tmpa[k]=a[i];i++;k++;}while(j<=high){tmpa[k]=a[j];j++;k++;}for(k=0,i=low;i<=high;k++,i++)a[i]=tmpa[k];free(tmpa);
}
void MergePass(int a[],int length,int n){int i;for(i=0;i+2*length-1<n;i=i+2*length)Merge(a,i,i+length-1,i+2*length-1);if(i+length-1<n)Merge(a,i,i+length-1,n-1);
}
void MergeSort(int a[],int low,int high){int mid;if(low<high){mid=(low+high)/2;MergeSort(a,low,mid);MergeSort(a,mid+1,high);Merge(a,low,mid,high);}
}
void main(){int n=10;int a[]={2,5,1,7,10,6,9,4,3,8};printf("排序前:");disp(a,n);MergeSort(a,0,9);printf("排序后:");disp(a,n);
}

3.運行結果

4.算法復雜度分析

數組段是偶數段，對于上述二路歸并排序算法，當有n個元素時需要[log2n]趟歸并，每一趟歸并，它的元素比較次數不超過n-1,元素移動次數都是n，因此二路歸并排序的時間復雜度O(nlog2n）

假設MergeSort(a,0,n-1)算法的執行時間為T（n),顯然，Merge(a,0,n/2,n-1)合并操作的執行時間為O(n)，所以得到以下遞推公式

T（n）=1 ????????????????當n=1的時候

T（n）=2T(n/2)+O(n) ????當n>1的時候

容易得出 T(n)=O(nlog2n)。

實驗總結：

在這次實驗中，我學到很多東西，加強了我的動手能力，并且培養了我的獨立思考能力。特別是在做實驗報告時，因為在做數據處理時出現很多問題，如果不解決的話,將會很難的繼續下去。還有動手這次實驗，使這門課的一些理論知識與實踐相結合, 更加深刻了我對算法設計與分析這門課的認識。

---

生活

寒假留校上半年還好，這學期開學就奇怪了，從家里來了之后就一直發燒，吃完退燒藥之后，消停了兩天，又發燒，直到學校正式開學，才消停，反反復復了十來天。罷了，總歸，又能活蹦亂跳了。

之前一直覺得自己性格特征不明顯，網上的東西很多都是刻板印象，直到玩得熟的朋友說我線上活潑還好說話，但線下很欠打，tm是個杠精，我才意識到，歐，好吧，不過還是不喜歡給自己貼標簽，因為畢竟，每個人都是獨一無二的。(?′?`?)

上次經歷了一些事情，朋友說那么愛問原因的你，怎么這回，不問問他原因呢？因為，我認為，無論是什么原因，如果后悔了，如果選擇的不是我，那就不屬于我，要么全部，要么全不，我永遠值得世界上最好的東西，是我的，誰也搶不走，不是我的，那我更不稀罕。或許，我的觀念有一天會改變，會意識到自己的狹隘，但目前為止，我尊重當下的自己。

?生活小滿勝萬全，現在 ,覺得，每天都無比絢麗多彩。24節氣快驚蟄了，為什么喜歡春天和夏天呢？因為它燦爛，明媚，熱烈。

上次跟同學聊天，偶然提到項目，他說

嘿嘿，誰得到夸夸和認可的時候不開心嘞 😎😎😎😎😎😎。

四級也過了，去年大英賽省二，今年的就不參加了，那就剩下，準備準備六級，還有藍橋杯了......

---

本來是想拍這個表情包的，

但是手機怎么放都不對,于是，畫風就變了，也很不錯了嘞

兩個突發奇想的小女孩兒（ 3月1日傍晚?）

---

基本不追星，但是高中的時候就喜歡張新成飾演的黎語冰，現在看，還是很喜歡

---

嘿嘿，臭屁一下，世界上怎么會有我這么棒棒噠的人兒，天哪，又是喜歡自己的一天。