算法排序问题实验报告
更新时间:2023-08-05 18:19:01 阅读量: 实用文档 文档下载
.
.. 《排序问题求解》实验报告
一、算法的基本思想
1、直接插入排序算法思想
直接插入排序的基本思想是将一个记录插入到已排好序的序列中,从而得到一个新的,记录数增1 的有序序列。
直接插入排序算法的伪代码称为InsertionSort,它的参数是一个数组A[1..n],包含了n 个待排序的数。用伪代码表示直接插入排序算法如下:
InsertionSort (A)
for i←2 to n
do key←A[i] //key 表示待插入数
//Insert A[i] into the sorted sequence A[1..i-1]
j←i-1
while j>0 and A[j]>key
do A[j+1]←A[j]
j←j-1
A[j+1]←key
2、快速排序算法思想
快速排序算法的基本思想是,通过一趟排序将待排序序列分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可对这两部分记录继续进行排序,以达到整个序列有序。
假设待排序序列为数组A[1..n],首先选取第一个数A[0],作为枢轴(pivot),然后按照下述原则重新排列其余数:将所有比A[0]大的数都排在它的位置之前,将所有比A[0]
小的数都排在它的位置之后,由此以A[0]最后所在的位置i 作为分界线,将数组A[1..n]分成两个子数组A[1..i-1]和A[i+1..n]。这个过程称作一趟快速排序。通过递归调用快速排序,对子数组A[1..i-1]和A[i+1..n]排序。
一趟快速排序算法的伪代码称为Partition,它的参数是一个数组A[1..n]和两个指针low、high,设枢轴为pivotkey,则首先从high 所指位置起向前搜索,找到第一个小于pivotkey 的数,并将其移到低端,然后从low 所指位置起向后搜索,找到第一个大于pivotkey 的数,并将其移到高端,重复这两步直至low=high。最后,将枢轴移到正确的位置上。用伪代码表示一趟快速排序算法如下:
Partition ( A, low, high)
A[0]←A[low]
//用数组的第一个记录做枢轴记录
privotkey←A[low]
//枢轴记录关键字
while low<high //从表的两端交替地向中间扫描
while low<high && A[high]>=privotkey do high←high-1
A[low]←A[high] //将比枢轴记录小的记录移到低端
while low<high && A[low]<=pivotkey) do low←low+1
A[high]←A[low] //将比枢轴记录大的记录移到高端
A[low]←A[0] //枢轴记录到位
return low //返回枢轴位置
二、算法的理论分析
.
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)。
三、试验分析
1、试验环境
WIN 32系统,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时:
..
.
做出折线统计图
..
.
四、试验心得
通过本次试验首先对在C++下的文件操作有了一定的深入认识,对于快速排序和插入排序的时间有了相当清晰且一目了然的认识,并且从原理上明白了快速排序的快的原因,对各种排序算法的优劣性有了全局的认识!
五、实验代码
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <fstream>
#include <string>
using namespace std;
const int NumS = 80000;
void datagenetare(int num[],int n); //产生随机数,保存到数组num
void WriteFile(int num[],char name[],int n); //输出数组num到data.txt文件
void ReadFile(int num[],char name[]);//读取名为name文件中的数据,保存到数组num
void QuickSort(int arr[], int n);//将数组arr[]中数据快速排序
void InsertionSort(int arr[],int n);//将数组arr[]中数据直接插入排序
int main()
{
int *num=(int *)malloc(sizeof(int)*NumS);
int *num1=(int *)malloc(sizeof(int)*NumS);
int *num2=(int *)malloc(sizeof(int)*NumS);
clock_t start_time1,end_time1,start_time2,end_time2;
double timeQS=0,timeIS=0;
cout<<"Create "<<NumS<<" random numbers from 1 to 100000"<<endl;
datagenetare(num,NumS); //产生随机数,保存到数组num
WriteFile(num,"data.txt",NumS); //输出数组到data.txt文件
cout.precision(6); //设置浮点数的显示精度
cout.setf(ios_base::showpoint); //输出末尾的
..
.
.. //直接插入排序的分析
ReadFile(num1,"data.txt");//读取data.txt中的数据,保存到数组num1
cout<<"\nInsertionSort Start ....\n";
start_time1=clock(); //开始计时
InsertionSort(num1,NumS); //直接插入排序数组num1中的数据
end_time1=clock(); //结束计时
timeIS=(double)(end_time1-start_time1)/CLOCKS_PER_SEC;
cout<<"The Time-comsuption in InsertionSort is "<<timeIS<<" seconds!\n\n"; //输出运行时
间
WriteFile(num1,"resultsIS.txt",NumS); //排序后的数据输出到resultQS.txt
//输出运行时间timeIS到resultsIS.txt
ofstream ocout;
ocout.open("resultsIS.txt",ios::app);
if(ocout.good()) //打开resultsIS.txt
{
ocout<<"\nThe Time-comsuption in InsertionSort is "<<timeIS<<" seconds\n";
ocout.close();
}
else
{
cout<<"\nCan not open resultsIS.txt!\n";
exit(1); //异常退出
}
//快速排序的分析
ReadFile(num2,"data.txt"); //读取data.txt中的数据,保存到数组num2[]
cout<<"QuickSort Start .....\n";
start_time2=clock(); //开始计时
QuickSort(num2,NumS); //快速排序数组num中的数据
end_time2=clock(); //结束计时
timeQS=(double)(end_time2-start_time2)/CLOCKS_PER_SEC;
cout<<"The Time-comsuption in QuickSort is "<<timeQS<<" seconds:\n"; //输出运行时间WriteFile(num2,"resultsQS.txt",NumS); //排序后的数据输出到resultQS.txt
//输出运行时间timeQS到resultsQS.txt
ocout.open("resultsQS.txt",ios::app);
if(ocout.good()) //打开resultsIS.txt
{
ocout<<"\nThe Time-comsuption in QuickSort is "<<timeQS<<" seconds\n";
ocout.close();
}
else
{
cout<<"\nCan not open resultsQS.txt!\n";
exit(1); //异常退出
}
.
.. return 0;
}
void datagenetare(int *num,int n)
{
int i;
srand((unsigned)time(0)); //srand()种子发生器函数,还有rand()随机数生成器函数for(i=0;i<n;i++) //产生个到之间的随机数
num[i]=rand()%9999+1;
printf("\n");
}
//将数组中的数据输出到文件
void WriteFile(int *num,char name[],int n)
{
ofstream ocout;
ocout.open(name,ios::trunc);
int i=0;
if(ocout.fail())
exit(1); //打开文件失败,退出
for(;i<n;i++)
{
ocout<<num[i]<<" ";
if((i+1)%40==0||i==n-1) //每输出40个数,换一行
ocout<<"\n";
}
ocout.close();
}
//将文件中的数据输入到数组
void ReadFile(int *num,char name[])
{
string strLine;
int i=0;
char achLine[300];
const char* pchTok;
ifstream icin;
icin.open(name,ios::in); //打开名为name的文件
while(icin.good())
{
int i = 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();
}
//快速排序的实现,从左向右递增排序
void QuickSort(int *arr, int n)
{
int L = 0;
int R = n-1;
int t = arr[L]; //区间的第一个数作为基准
if(n<=1) //数组中存在个或个数据时,函数返回
return;
//将数据分成两个区间
while(L<R){ //区间内至少存在一个元素的情况
while(L<R&&t<=arr[R]) R--;//从右向左搜索,直到第一个小于t的数arr[R]
arr[L] = arr[R];
while(L<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);//对右区间递归排序
}
//直接插入排序的实现,从左向右递增排序
void InsertionSort(int *arr,int n)
{
int i=0,temp=0,j=0;
if(n<=1)
return;
for(i=1;i<n;++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]
.
.. }
}
正在阅读:
算法排序问题实验报告08-05
物料搬运系统设计论文 - 图文04-11
一句格言的启示作文500字07-14
小学幻想作文06-15
安全教育作文02-04
2015年北京东城初三一模化学试题及答案(word版) - 图文03-19
国外矿产资源深部找矿勘探的现状与趋势12-17
2019年高考化学大二轮复习综合训练(六)化学实验04-24
我的童年作文400字02-04
2011届中考语文病句讲解练习题05-16
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 算法
- 排序
- 实验
- 报告
- 问题
- 苏教版四年级上册综合实践教案江苏凤凰少年儿童出版社
- 智能化安防设计方案
- 团队合作励志文章
- 高德地图离线数据安装
- 解析应纳税暂时性差异和可抵扣暂时性差异
- 大学英语语法-Exercises for non-finite verbs-key
- 水质检测基础知识及上岗考试题
- 第二章 单片机芯片的硬件结构
- 《模拟电子技术基础》实验
- 人教版初三化学知识点复习总结
- 三级口腔医院评审标准2011版
- 非限制性定语从句练习题】
- 2011-2012高一生物必修二期末考试题(7)
- 江西省萍乡市芦溪县2017届九年级上学期 期中考试英语试题(含答案)
- 俞敏洪白手起家from Rags to Riches
- (完整版)高考定语从句与名词性从句填空改错(含答案)
- 七年级上册数学二元一次方程
- 第26章二次函数—二次函数小结与复习 01
- 如何做好英语阅读理解
- 环氧树脂的稳定