快速排序和归并排序(C语言)
1.0快速排序算法
(1)分解 (2)递归求解 (3)合并
int partition(int a[],int p,int r)
{
int i=p,j=r+1;
int x=a[p];
int temp;
while(1) //将<x的元素交换到左边元素,>x的元素交换到右边元素
{
while(a[++i]<x && i<r);
while(a[--j]>x);
if(i>=j)
break;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
a[p]=a[j];
a[j]=x;
return j;
}
void qSort(int a[],int p,int r,int num)
{
int i;
if(p<r)
{
int q=partition(a,p,r);
qSort(a,p,q-1,num); //对左半段排序
qSort(a,q+1,r,num); //对右半段排序
}
printf("快速排序过程:");
for(i=0;i<num;i++)
{
printf("%d ",a[i]);
}
printf("\n");
}
int main()
{
int num;
int i;
int a[100];
printf("请输入数组长度:");
scanf("%d",&num);
printf("请输入数组:\n");
for(i=0;i<num;i++)
{
scanf("%d",&a[i]);
}
qSort(a,0,num-1,num);
printf("快速排序结果:");
for(i=0;i<num;i++)
{
printf("%d ",a[i]);
}
return 0;
}
2.0归并排序算法
将两个有序的左右子表(以mid区分),合并成一个有序的表
void merge(int a[],int first,int mid,int last)
{
int indexA=first;
int indexB=mid+1;
int tempIndex=0;
int i;
static int temp[1000];
while(indexA<=mid && indexB<=last)//进行左右子表的遍历,如果其中有一个子表遍历完,则跳出循环
{
if(a[indexA]<a[indexB])
{
temp[tempIndex++]=a[indexA++];
}
else
{
temp[tempIndex++]=a[indexB++];
}
}
//有一侧子表遍历完后,跳出循环,将另外一侧子表剩下的数一次放入暂存数组中(有序)
while(indexA<=mid)
{
temp[tempIndex++]=a[indexA++];
}
while(indexB<=last)
{
temp[tempIndex++]=a[indexB++];
}
//将暂存数组中有序的数列写入目标数组的制定位置,使进行归并的数组段有序
tempIndex=0;
for(i=first;i<=last;i++)
{
a[i]=temp[tempIndex++];
}
}
void mergeSort(int a[],int first,int last,int num)
{
int i;
if(first<last)//子表的长度大于1,则进入下面的递归处理
{
int mid=(first+last)/2;
mergeSort(a,first,mid,num);
mergeSort(a,mid+1,first,num);
merge(a,first,mid,last);
}
printf("合并排序时的数组:\n");
for(i=0;i<num;i++)
{
printf("%d ",a[i]);
}
printf("\n");
}
int main()
{
int num;
int i;
int a[100];
printf("请输入数组长度:");
scanf("%d",&num);
printf("请输入数组:\n");
for(i=0;i<num;i++)
{
scanf("%d",&a[i]);
}
mergeSort(a,0,num-1,num);
printf("合并排序后的数组:\n");
for(i=0;i<num;i++)
{
printf("%d ",a[i]);
}
return 0;
}
最新文章
- Travis CI用来持续集成你的项目
- 如何在没有域的环境中搭建AlwaysOn(一)
- Oracle安装时OracleMTSRecoveryService找不到
- C#的选择语句练习
- Python-面向对象编程(二)
- C语言范例学习03-中
- 关于SAP的视图类型
- cocos2dx 3.x(精灵的碰撞检测,点击移动与拖动精灵)
- Http,Https(SSL)的Url绝对路径,相对路径解决方案Security Switch 4.2的配置和使用 分类: ASP.NET 2014-11-05 12:51 97人阅读 评论(0) 收藏
- Linux 文件系统同步
- 10. Regular Expression Matching
- csrf学习笔记
- Linux V4L2之camera
- 如何解决ORA-28002 the password will expire within 7 days问题(密码快过期)
- python命名规则
- DP入门基本问题
- lava.lang.String数据转换为java.sql.Date
- [CF1067D]Computer Game[凸包/斜率优化+倍增+矩阵乘法]
- Answer My Questions
- Docker之存储管理
热门文章
- 【转】iOS库 .a与.framework区别
- Vue学习(一):Vue实例
- Spotlight on MySQL
- [PocketFlow]解决在coco上mAP非常低的bug
- spring与mybatis整合(基于配置文件)
- SpringBoot 中使用shiro注解使之生效
- Python两个内置函数——locals 和globals (学习笔记)
- Jira &; filter &; subscribe &; issues
- Bootstrap中轮播图
- 使用XML传递数据