算法排序问答实验报告Word下载.docx
《算法排序问答实验报告Word下载.docx》由会员分享，可在线阅读，更多相关《算法排序问答实验报告Word下载.docx（13页珍藏版）》请在冰点文库上搜索。
A[0]←A[low]
//用数组的第一个记录做枢轴记录
privotkey←A[low]
//枢轴记录关键字
whilelow<
high//从表的两端交替地向中间扫描
high&
&
A[high]>
=privotkeydohigh←high-1
A[low]←A[high]//将比枢轴记录小的记录移到低端
A[low]<
=pivotkey）dolow←low+1
A[high]←A[low]//将比枢轴记录大的记录移到高端
A[low]←A[0]//枢轴记录到位
returnlow//返回枢轴位置
2、算法的理论分析
1.直接插入排序算法理论分析
从空间来看，直接插入排序只需要一个数的辅助空间；
从时间来看，直接插入排序的基
本操作为：
比较两个关键字的大小和移动记录。
先分析一趟直接插入排序的情况。
伪代码
InsertionSort中while循环的次数取决于待插入的数与前i-1个数之间的关系。
若A[i]<
A[0],则在while循环中，待插入数需与有序数组A[1..i-1]中i-1个数进行比较，并将A[i-1]中i-1个数后移。
则在整个排序过程（进行n-1趟插入排序）中，当待排序数组中数按非递减有序排列时，则需进行数间比较次数达最小值n-1,数不需要移动；
反之，当待排序数组中数按非递增有序排列时，总的比较次数达最大值（n+2）（n-1）/2，数移动的次数也达到最大值（n+4）（n-1）/2。
若待排序数组是随机的，即待排序数组中的数可能出现的各种排序的概率相同，则我们可取
上述最小值和最大值的平均值，作为直接插入排序时所需进行数间的比较次数和数的移动次
数，约为n^2/4。
因此直接插入排序算法，在最佳情况下的时间复杂度是O（n），在最坏情况下的时间复杂度为O（n^2）。
2.快速排序算法理论分析
下面我们来分析快速排序的平均时间性能。
假设T（n）为对n个记录A[1..n]进行快速排序所需时间，则由算法QuickSort可见：
其中，Tpass（n）为对n个记录进行一趟快速排序Partition（A,1,n）所需的时间，从一
趟快速排序算法可见，其和记录数n成正比，可以用cn表示（c为某个常数）；
T（k-1）和T
（n-k）分别为对A[1..k-1]和A[k+1..n]中记录进行快速排序QuickSort（A,1,k-1）和
QuickSort（A,k+1,n）所需时间。
假设待排序列中记录是随机排列的，则在一趟排序之后，
k取1至n之间任何一值的概率相同，快速排序所需时间的平均值则为Tavg（n）=knInn，其中n为待排序序列中记录的个数，k为某个常数。
通常，快速排序被认为是，在所有同数量级（O（nlogn））的排序方法中，其平均性能最
好。
但是，若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，其时
间复杂度为O（n^2）。
3、试验分析
1、试验环境
WIN32系统，VC6.0
2、程序的执行
1）由函数datagenetare（）生成20000个在区间[1,100000]上的随机整数，并将随机整数保存到数组num[]，接着调用函数WriteFile（）将这些数输出到外部文件data.txt中。
2）调用函数ReadFile（）从data.txt中读取数据，并将其保存到数组num1[]中。
接着对数组num1进行直接插入排序，并计算和记录其运行时间。
最后，调用函数WriteFile（）将直接插入排序的结果写入resultsIS.txt，并记录运行时间为TimeIS。
3）调用函数ReadFile（）从data.txt中读取数据，并将其保存到数组num2[]中。
接着对数组num2进行快速排序，并计算和记录其运行时间。
最后，调用函数WriteFile（）将快速排序的结果写入resultsQS.txt，并记录运行时间为TimeQS。
3、试验数据
当N=20000时：
当N=30000时：
当N=40000时：
当N=50000时：
当N=60000时：
当N=70000时：
当N=80000时：
4、实验结果分析
20000
30000
40000
50000
60000
70000
80000
插入排序
0.325
0.719
1.397
2.199
3.05
4.571
5.46
快速排序
0.003
0.005
0.008
0.01
0.012
0.011
0.013
做出折线统计图
4、试验心得
通过本次试验首先对在C++下的文件操作有了一定的深入认识，对于快速排序和插入排序的时间有了相当清晰且一目了然的认识，并且从原理上明白了快速排序的快的原因，对各种排序算法的优劣性有了全局的认识！
5、实验代码
#include<
iostream>
ctime>
cstdlib>
fstream>
string>
usingnamespacestd;
constintNumS=80000;
voiddatagenetare（intnum[],intn）;
//产生随机数，保存到数组num
voidWriteFile（intnum[],charname[],intn）;
//输出数组num到data.txt文件
voidReadFile（intnum[],charname[]）;
//读取名为name文件中的数据，保存到数组num
voidQuickSort（intarr[],intn）;
//将数组arr[]中数据快速排序
voidInsertionSort（intarr[],intn）;
//将数组arr[]中数据直接插入排序
intmain（）
{
int*num=（int*）malloc（sizeof（int）*NumS）;
int*num1=（int*）malloc（sizeof（int）*NumS）;
int*num2=（int*）malloc（sizeof（int）*NumS）;
clock_tstart_time1,end_time1,start_time2,end_time2;
doubletimeQS=0,timeIS=0;
cout<
<
"
Create"
NumS<
randomnumbersfrom1to100000"
endl;
datagenetare（num,NumS）;
WriteFile（num,"
data.txt"
NumS）;
//输出数组到data.txt文件
cout.precision（6）;
//设置浮点数的显示精度
cout.setf（ios_base:
:
showpoint）;
//输出末尾的
//直接插入排序的分析
ReadFile（num1,"
）;
//读取data.txt中的数据，保存到数组num1
\nInsertionSortStart....\n"
;
start_time1=clock（）;
//开始计时
InsertionSort（num1,NumS）;
//直接插入排序数组num1中的数据
end_time1=clock（）;
//结束计时
timeIS=（double）（end_time1-start_time1）/CLOCKS_PER_SEC;
TheTime-comsuptioninInsertionSortis"
timeIS<
seconds!
\n\n"
//输出运行时间
WriteFile（num1,"
resultsIS.txt"
//排序后的数据输出到resultQS.txt
//输出运行时间timeIS到resultsIS.txt
ofstreamocout;
ocout.open（"
ios:
app）;
if（ocout.good（））//打开resultsIS.txt
{
ocout<
\nTheTime-comsuptioninInsertionSortis"
seconds\n"
ocout.close（）;
}
else
cout<
\nCannotopenresultsIS.txt!
\n"
exit
（1）;
//异常退出
//快速排序的分析
ReadFile（num2,"
//读取data.txt中的数据，保存到数组num2[]
QuickSortStart.....\n"
start_time2=clock（）;
QuickSort（num2,NumS）;
//快速排序数组num中的数据
end_time2=clock（）;
timeQS=（double）（end_time2-start_time2）/CLOCKS_PER_SEC;
TheTime-comsuptioninQuickSortis"
timeQS<
seconds:
WriteFile（num2,"
resultsQS.txt"
//输出运行时间timeQS到resultsQS.txt
\nTheTime-comsuptioninQuickSortis"
\nCannotopenresultsQS.txt!
return0;
}
voiddatagenetare（int*num,intn）
inti;
srand（（unsigned）time（0））;
//srand（）种子发生器函数，还有rand（）随机数生成器函数
for（i=0;
i<
n;
i++）//产生个到之间的随机数
num[i]=rand（）%9999+1;
printf（"
//将数组中的数据输出到文件
voidWriteFile（int*num,charname[],intn）
ocout.open（name,ios:
trunc）;
inti=0;
if（ocout.fail（））
//打开文件失败，退出
for（;
i++）
num[i]<
"
if（（i+1）%40==0||i==n-1）//每输出40个数，换一行
ocout<
ocout.close（）;
//将文件中的数据输入到数组
voidReadFile（int*num,charname[]）
stringstrLine;
charachLine[300];
constchar*pchTok;
ifstreamicin;
icin.open（name,ios:
in）;
//打开名为name的文件
while（icin.good（））
inti=0;
while（getline（icin,strLine））
{
strLine.copy（achLine,strLine.size（）,0）;
achLine[strLine.size（）]='
\0'
//每行中的元素以空格为标识断开转换为int类型后存入数组
pchTok=strtok（achLine,"
while（（pchTok!
=NULL））
{
num[i]=atoi（pchTok）;
i++;
pchTok=strtok（NULL,"
}
}
icin.close（）;
//快速排序的实现，从左向右递增排序
voidQuickSort（int*arr,intn）
intL=0;
intR=n-1;
intt=arr[L];
//区间的第一个数作为基准
if（n<
=1）//数组中存在个或个数据时，函数返回
return;
//将数据分成两个区间
while（L<
R）{//区间内至少存在一个元素的情况
while（L<
R&
t<
=arr[R]）R--;
//从右向左搜索，直到第一个小于t的数arr[R]
arr[L]=arr[R];
arr[L]<
=t）L++;
//从左向右搜索，找到第一个大于t的数arr[L]
arr[R]=arr[L];
arr[L]=t;
QuickSort（arr,L）;
//对左区间递归排序
QuickSort（arr+L+1,n-L-1）;
//对右区间递归排序
//直接插入排序的实现，从左向右递增排序
voidInsertionSort（int*arr,intn）
inti=0,temp=0,j=0;
=1）
for（i=1;
++i）
temp=arr[i];
//temp记录要插入的数据arr[i]
j=i;
//要插入的数据的位置
for（;
j>
0&
arr[j-1]>
temp;
--j）//将a[i]插入到已排序的arr[0]~arr[i-1]中
arr[j]=arr[j-1];
//比temp大的数据依次后移
arr[j]=temp;
//找到第一个不大于于temp的数据，在j处插入arr[i]
升级会员 