中國科技大學(xué)算法導(dǎo)論_第一次實驗報告

1、快速排序?qū)嶒瀳蟾鍿A14225010 1、 題目當(dāng)輸入數(shù)據(jù)已經(jīng)“幾乎”有序時，插入排序速度很快。在實際應(yīng)用中，我們可以利用這一特點來提高快速排序的速度。當(dāng)對一個長度小于k的子數(shù)組調(diào)用快速排序時，讓它不做任何排序就返回。當(dāng)上層的快速排序調(diào)用返回后，對整個數(shù)組運行插入排序來完成排序過程。試證明：這一排序算法的期望時間復(fù)雜度為O（nk+nlg（n/k）。分別從理論和實踐的角度說明我們應(yīng)該如何選擇k？2、 算法思想當(dāng)輸入數(shù)據(jù)已經(jīng)“幾乎”有序時，插入排序速度很快。當(dāng)對一個長度小于k的子數(shù)組調(diào)用快速排序時，讓它不做任何排序就返回。當(dāng)上層的快速排序調(diào)用返回后，對整個數(shù)組運行插入排序來完成排序過程。累加k的值

2、，計算出當(dāng)k為不同值時算法運行的時間，來算出當(dāng)k大約為什么值時運行的時間最短，并與傳統(tǒng)的快速排序算法的運行時間進行比較。3、 實驗結(jié)果輸入100個不同的整數(shù)值，選取不同的k的值，觀察所用時間4、 實驗分析理論上看，k的值選取為20到25較好；但是，從實際上來看，當(dāng)k為50左右時間為39毫秒，最少，但不同的時刻運行后的時間都不相同，而且不同的輸入時刻的運行時間也不相同，當(dāng)數(shù)據(jù)較大時候，對k 的值的選取有會有所不同，同時不同性能的機器對測試結(jié)果也不同，所以對于k值的選取沒有固定的數(shù)值。#include#includeusing namespace std;#define M 40void swap

3、(int * a,int * b) int tem; tem=*a; *a=*b; *b=tem;int partition(int v,const int low,const int high)int i,pivotpos,pivot;pivotpos=low;pivot=vlow;for(i=low+1;i=high;+i) if(vipivot) pivotpos+; if(pivotpos!=i)swap(vi,vpivotpos); vlow=vpivotpos;vpivotpos=pivot;/coutthe partition function is calledn;return

4、 pivotpos;/*void QuickSort(int a, const int low,const int high)int item; if(lowhigh) item=partition(a,low,high); QuickSort(a,low,item-1); QuickSort(a,item+1,high); */void QuickSort(int a, const int low,const int high)int item;if(high-low=M)return; if(lowhigh) item=partition(a,low,high); QuickSort(a,

5、low,item-1); QuickSort(a,item+1,high); / coutthe QuickSort is calledendl;void InsertSort(int a,const int low,const int high)int i,j;int tem;for(i=1;i=0&temaj) aj+1=aj; j-; aj+1=tem;/coutthe InsertSort is calledendl;void HybridSort(int a,const int low,const int high) QuickSort(a,low,high); InsertSort

6、(a,low,high); coutthe HybidSort is calledendl;int main() int i,a100;/int *a=NULL;long int t;struct timeb t1,t2;/*coutplease input the number of the element:n;a = (int*)malloc(n*sizeof(int);coutplease input every element:endl;*/for( i=0; i100; i+)ai=i+10;/QuickSort(a,0,n-1);ftime(&t1);HybridSort(a,0,99);cout after sorted quickly,the result isendl;for(i=0; i100; i+)coutai ;if(i%10=0)coutendl;coutendl;ftime(&t2);t=(t2.time-t1.time)*1000+(litm); /*