中国科技大学算法导论-第一次实验报告
- 格式：doc
- 大小：1.03 MB
- 文档页数：11
word版本 .
快速排序实验报告
SA14225010
一、题目
当输入数据已经“几乎”有序时，插入排序速度很快。在实
际应用中，我们可以利用这一特点来提高快速排序的速度。当对
一个长度小于k的子数组调用快速排序时，让它不做任何排序就
返回。当上层的快速排序调用返回后，对整个数组运行插入排序
来完成排序过程。试证明：这一排序算法的期望时间复杂度为O
（nk+nlg（n/k））。分别从理论和实践的角度说明我们应该如何
选择k？
二、算法思想
当输入数据已经“几乎”有序时，插入排序速度很快。当
对一个长度小于k的子数组调用快速排序时，让它不做任何排序
就返回。当上层的快速排序调用返回后，对整个数组运行插入排
序来完成排序过程。累加k的值，计算出当k为不同值时算法运
行的时间，来算出当k大约为什么值时运行的时间最短，并与传
统的快速排序算法的运行时间进行比较。
三、实验结果
word版本 .
输入100个不同的整数值，选取不同的k的值，观察所用时间
word版本 .
word版本 .
word版本 .
word版本 .
word版本 .
word版本 .
四、实验分析
理论上看，k的值选取为20到25较好；但是，从实际上
来看，当k为50左右时间为39毫秒，最少，但不同的时刻
运行后的时间都不相同，而且不同的输入时刻的运行时间也
不相同，当数据较大时候，对k 的值的选取有会有所不同，
同时不同性能的机器对测试结果也不同，所以对于k值的选
取没有固定的数值。
#include
#include
using namespace std;
#define M 40
void swap(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=v[low];
word版本 .
for(i=low+1;i<=high;++i)
{
if(v[i]
pivotpos++;
if(pivotpos!=i)swap(v[i],v[pivotpos]);
}
}
v[low]=v[pivotpos];
v[pivotpos]=pivot;
//cout<<"the partition function is called\n";
return pivotpos;
}
/*
void QuickSort(int a[], const int low,const int high)
{
int item;
if(low
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(low
item=partition(a,low,high);
QuickSort(a,low,item-1);
word版本 .
QuickSort(a,item+1,high);
}
// cout<<"the QuickSort is called"<
void InsertSort(int a[],const int low,const int high)
{
int i,j;
int tem;
for(i=1;i
tem=a[i];
j=i-1;
while(j>=0&&tem
a[j+1]=a[j];
j--;
}
a[j+1]=tem;
}
//cout<<"the InsertSort is called"<
void HybridSort(int a[],const int low,const int high) } int main() cin>>n; cout<<" after sorted quickly,the result is"< //cout<<"the memory of array a is free"< return 0;
{
QuickSort(a,low,high);
InsertSort(a,low,high);
cout<<"the HybidSort is called"<
{
int i,a[100];
//int *a=NULL;
long int t;
struct timeb t1,t2;
/*cout<<"please input the number of the element:"<
a = (int*)malloc(n*sizeof(int));
cout<<"please input every element:"<
for( i=0; i<100; i++)
{
a[i]=i+10;
}
//QuickSort(a,0,n-1);
ftime(&t1);
HybridSort(a,0,99);
{
cout<
cout<
t=(t2.time-t1.time)*1000+(t2.millitm-t1.millitm); /* 计算时间差 */
printf("k=%d 用时%ld毫秒\n",M,t);
cout<<"\n"<
}
