好资源导航 » 文章资讯 » C语言实现快速排序改进版

C语言实现快速排序改进版

2023-09-08 23:27:05 256

利用三者取中法改进快速排序，具体内容如下

实现取数组中第一个,中间和最后一个元素的中间元素作为划分元素(否则将这些元素排除在划分过程之外).大小为11或更小的数组在划分过程中被忽略,然后使用插入排序来完成排序.

#include
#include
#include
#include
#include
#include
usingnamespacestd;
#defineOK1
#defineERROR-1
#defineTRUE1
#defineFALSE0
typedefintStatus;
//输出函数
voidPrint(inta[],intl,intr)
{
inti;
for(i=l;i<=r;i++)
{
printf("%d",a[i]);
}
printf("\n");
}
//插入排序的改进
voidInsertion(inta[],intl,intr)
{
inti,j;
//循环找到数组中的最小值
for(i=r;i>l;i--)
{
if(a[i-1]>a[i])
{
swap(a[i-1],a[i]);
}
}
//由于上面的循环,a[0]a[1]已经有序
for(i=l+2;i<=r;i++)
{
inttemp=a[i];
j=i;
//此时a[j]的位置已被记录
//while循环比较进行移位操作
while(tempa[i])
{
i++;
}
//从右边进行扫描,当出现比划分元素小的元素,扫描停止
while(temp=left)
{
j--;
}
//如果i>=j,循环截止,下面的交换不执行
if(i>=j)break;
//交换停止时的元素
swap(a[i],a[j]);
}
//交换该元素与划分元素
swap(a[i],a[right]);
//printf("i=%d\n",i);
//Print(a,0,6);
//划分过程结束
returni;
}

voidqsort(inta[],intleft,intright)
{
inti;
if(right-left<=10)
return;
swap(a[(left+right)/2],a[right-1]);
if(a[left]>a[right-1])
swap(a[left],a[right-1]);
if(a[left]>a[right])
swap(a[left],a[right]);
if(a[right]>a[right-1])
swap(a[right-1],a[right]);
i=partion(a,left+1,right-1);
qsort(a,left,i-1);
qsort(a,i+1,right);
}
voidSort(inta[],intleft,intright)
{
qsort(a,left,right);
Insertion(a,left,right);
}

intmain()
{
inta[12]={2,5,3,7,6,1,4,11,8,10,9,12};
//快速排序改进
printf("对0~11排序\n");
Sort(a,0,11);
Print(a,0,11);
return0;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。

声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

返回顶部
3162201930
czq8825@qq.com

C语言实现快速排序改进版

热门推荐

随机推荐