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

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

2、，計(jì)算出當(dāng)k為不同值時(shí)算法運(yùn)行的時(shí)間，來算出當(dāng)k大約為什么值時(shí)運(yùn)行的時(shí)間最短，并與傳統(tǒng)的快速排序算法的運(yùn)行時(shí)間進(jìn)行比較。3、 實(shí)驗(yàn)結(jié)果輸入100個(gè)不同的整數(shù)值，選取不同的k的值，觀察所用時(shí)間4、 實(shí)驗(yàn)分析理論上看，k的值選取為20到25較好；但是，從實(shí)際上來看，當(dāng)k為50左右時(shí)間為39毫秒，最少，但不同的時(shí)刻運(yùn)行后的時(shí)間都不相同，而且不同的輸入時(shí)刻的運(yùn)行時(shí)間也不相同，當(dāng)數(shù)據(jù)較大時(shí)候，對(duì)k 的值的選取有會(huì)有所不同，同時(shí)不同性能的機(jī)器對(duì)測(cè)試結(jié)果也不同，所以對(duì)于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); /*