1 / 13
文档名称:

快速排序与归并排序算法及时间复杂度分析(C ).doc

格式:doc   大小:263KB   页数:13页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

快速排序与归并排序算法及时间复杂度分析(C ).doc

上传人:AIOPIO 2021/1/7 文件大小:263 KB

下载得到文件列表

快速排序与归并排序算法及时间复杂度分析(C ).doc

相关文档

文档介绍

文档介绍:答:(1)归并排序算法
#include <iostream>
#include<>
using namespace std;
void merge(int *data, int p, int q, int r) {
int n1, n2, i, j, k;
int *left=NULL, *right=NULL;
n1 = q-p+1;
n2 = r-q;
left = (int *)malloc(sizeof(int)*(n1));
right = (int *)malloc(sizeof(int)*(n2));
for(i=0; i<n1; i++) //对左数组赋值
left[i] = data[p+i];
for(j=0; j<n2; j++) //对右数组赋值
right[j] = data[q+1+j];
i = j = 0;
k = p;
while(i<n1 && j<n2) //将数组元素值两两比较,并合并到data数组
{
if(left[i] <= right[j])
data[k++] = left[i++];
else
data[k++] = right[j++];
}
for(; i<n1; i++) //如果左数组有元素剩余,则将剩余元素合并到data数组
data[k++] = left[i];
for(; j<n2; j++) //如果右数组有元素剩余,则将剩余元素合并到data数组
data[k++] = right[j];
}
void mergeSort(int *data, int p, int r) {
int q;
if(p < r) //只有一个或无记录时不须排序
{
q = (int)((p+r)/2); //将data数组分成两半
mergeSort(data, p, q); //递归拆分左数组
mergeSort(data, q+1, r); //递归拆分右数组
merge(data, p, q, r); //合并数组
}
}
int main()
{
int n;
int* input = NULL;
//输入数据
cout<<"请输入数组的长度: ";
cin>>n;
input = (int *)malloc(sizeof(int)*(n));
cout<<"请对数组赋值: ";
for(int i=0; i<n; ++i)
{
cin>>input[i];
}
//处理数据
clock_t start,finish;
double totaltime;
start=clock(); ////开始统计时间
mergeSort(input,0,n-1);
//输出结果
for(i=0; i<n; ++i)
cout<<input[i]<<" ";
cout<<endl;
system("pause"); ///
finish=clock();
totaltime=(double)(finish-start)/CLOCKS_PER_SEC; //统计时间截止
cout<<"\n此程序的运行时间为"<<totaltime<<"秒!"<<endl;
return 0;
}
操作结果截屏

快速排序算法:
#include<iostream>
#include<>
using namespace std;

最近更新

二零二五年度企业内部审计专员聘用合同模板 7页

2025年化脓性骨髓炎病理机制详解 65页

二零二五年度人防车位使用权及车位租赁与车位.. 9页

二零二五年度人力资源服务合同 9页

二零二五年度产品推广宣传册定制印刷合同 9页

二零二五年度交通事故责任划分及补偿协议 8页

2025年创伤急救知识与技能精要 52页

二零二五年度二手奢侈品寄卖服务合同 8页

二零二五年度事业单位临时工聘用合同修订方案.. 7页

二零二五年度乡村旅游开发农村土地租赁框架协.. 8页

2025年感动什么中国作文 17页

2025年感动中国十大人物颁奖典礼观后感(范文.. 12页

2025年关节软骨损伤修复攻略图文详解 40页

二零二五年度中小学生艺术特长校外教育合同 9页

二零二五年度个体转让协议:旅游项目经营权转.. 9页

二零二五年度个体户网络安全技术员劳动合同范.. 9页

2025年意大利详细留学申请流程和条件一览 7页

2025年想要大声说我爱你一句话情书 2页

2025年儿童营养失衡问题解析 54页

2025年惊蛰节气寓意含义 4页

2025年惊蛰时节有什么习俗 4页

二零二五年度个人租车共享出行合同 8页

2025年情人节送多少玫瑰(2) 8页

二零二五年度个人消费借款担保协议 7页

2025年情人节文案大全0句 20页

二零二五年度个人摊位租赁合同(含文化旅游元.. 8页

2025年悲伤逆流成河经典语录 8页

2025年儿童急性上呼吸道感染护理指南 20页

二零二五年度个人店铺智能家居解决方案委托合.. 9页

2025年儿童常见疾病解析与防治讲座 49页