主题：分享个排序算法...........
InitInstance
[专家分：8720] 发布于 2006-06-25 10:57:00
#include<stdio.h>
#include<stdlib.h>
#define n 18
void main()
{
bool bIEvennumber=false;//元素个数是否偶数
int A[n]={3,1,5,4,7,9,8,6,10,2,12,11,14,13,16,15,18,17};
int max,min,i,j,d,c;
printf("原数组为： ");
for(i=0;i<n;i++)
printf("%d ",A[i]);
printf("\n");
if(n%2==0)
bIEvennumber=true;
for(i=0;i<n/2;i++) //
{
max=min=A[i];
c=d=i;
for(j=i+1;j<n-i;j++)
{
if(A[j]>=max)
{
max=A[j];
c=j;
}
else if(A[j]<=min)
{
min=A[j];
d=j;
}
}
if(j-i<=2)
break;
//较小值放前面
A[d]=A[i];
A[i]=min;
//较大值放后面
if(c!=i)
{
A[c]=A[j-1];
A[j-1]=max;
}
else
{
max=A[j-1];
//此处max被用做中间变量不用担心影响到它本来的作用
A[j-1]=A[d];
A[d]=max;
}
}
if(bIEvennumber&&A[i]>A[i+1])
{
int temp;
temp=A[i+1];
A[i+1]=A[i];
A[i]=temp;
}
printf("调整后的数组为：");
for(i=0;i<n;i++)
printf("%d ",A[i]);
printf("\n ");
return;
}
回复列表 （共22个回复）
沙发
euc [专家分：4310] 发布于 2006-06-25 15:18:00
有创意呦：）可以叫两端选择法吧.
板凳
寒狐风悠 [专家分：80] 发布于 2006-06-25 21:03:00
不错不错呀。呵呵
3 楼
InitInstance [专家分：8720] 发布于 2006-06-26 10:20:00
改进（不用判断元素个数是否偶数了，把变量bIsEvennumber除掉）：
//还有什么值得改进的请指出啊
//谢谢你的参与
//2006/06/26
#include<stdio.h>
#include<stdlib.h>
#define n 18
void main()
{
int A[n]={3,1,5,4,7,9,8,6,10,2,12,11,14,13,16,15,18,17};
int max,min,i,j,d,c;
printf("原数组为： ");
for(i=0;i<n;i++)
printf("%d ",A[i]);
printf("\n");
for(i=0;i<n/2;i++)
{
max=min=A[i];
c=d=i;
for(j=i+1;j<n-i;j++)
{
if(A[j]>=max)
{
max=A[j];
c=j;
}
else if(A[j]<=min)
{
min=A[j];
d=j;
}
}
if(j-i<=2)
break;
//较小值放前面
A[d]=A[i];
A[i]=min;
//较大值放后面
if(c!=i)
{
A[c]=A[j-1];
A[j-1]=max;
}
else
{
max=A[j-1];
//此处max被用做中间变量不用担心影响到它本来的作用
A[j-1]=A[d];
A[d]=max;
}
}
if(A[i]>A[i+1])
{
int temp;
temp=A[i+1];
A[i+1]=A[i];
A[i]=temp;
}
printf("调整后的数组为：");
for(i=0;i<n;i++)
printf("%d ",A[i]);
printf("\n ");
return;
}
4 楼
脱缰野马 [专家分：10] 发布于 2006-06-26 19:41:00
看了N久 就是没看懂
我果然菜
大虾能否解释下算法?
5 楼
InitInstance [专家分：8720] 发布于 2006-06-26 22:40:00
可以像euc所说的把它叫做双端选择排序吧，我上面写的是从小到大排序（改动一下就很容易变成从大到小了）第一次：i=0,把最大和最小的数找出来，后把最大的数跟最后一个数交换[大数放到最后]，最小的数跟第一个数交换[小数放到最前]；第二次：i=1,由于第一个位置和最后一个位置已经排好，在剩下的n-2个数里再找出最大和最小的两个数然后重复第一步的操作....如此直至排好序。这个算法比较好理解且时间复杂度也不是很大。
6 楼
lifeiwen [专家分：130] 发布于 2006-06-26 23:03:00
自己想的?有点象快速排序.
7 楼
goal00001111 [专家分：4030] 发布于 2006-06-27 02:22:00
这是选择排序法的一个变种,原来也看到一个两端冒泡法,原理和它差不多,两端同时比较,看起来快了,其实速度差不多,时间复杂度仍然是o(n^2)．虽然如此，想法可佳，值得鼓励！顶！
同时稍微优化一下，只是代码简化一下而已，呵呵！
#include<stdio.h>
#include<stdlib.h>
#define n 18
int main()
{
int A[n]={3,1,5,4,7,9,8,6,10,2,12,11,14,13,16,15,18,17};
int max,min,i,j,temp;
printf("原数组为： ");
for(i=0;i<n;i++)
printf("%d ",A[i]);
printf("\n");
for(i=0;i<n/2;i++)
{
max = min = i;
for(j=i+1;j<n-i;j++) //同时选择最大值和最小值
{
if(A[j]>A[max])
max=j;
else if(A[j]<A[min])
min=j;
}
if (max != j-1) //把最大值换到最后
{
temp=A[j-1];
A[j-1]=A[max];
A[max]=temp;
}
if (i != min) //把最小值换到最前面
{
temp=A[i];
A[i]=A[min];
A[min]=temp;
}
}
if (n > 1 && A[n/2-1] > A[n/2]) //调整中间的两个数，因为上面的程序不能正确的调整它们
{
temp=A[n/2-1];
A[n/2-1]=A[n/2];
A[n/2]=temp;
}
printf("调整后的数组为：");
for(i=0;i<n;i++)
printf("%d ",A[i]);
printf("\n ");
getchar();
return 0;
}
8 楼
goal00001111 [专家分：4030] 发布于 2006-06-27 11:23:00
楼上有点错误,容我改过来.
9 楼
goal00001111 [专家分：4030] 发布于 2006-06-27 11:53:00
改过来了:
#include<stdio.h>
#include<stdlib.h>
#define n 17
int main()
{
int A[n]={3,1,5,4,7,9,8,6,10,2,12,11,14,13,16,15,18};
int max,min,i,j,temp;
printf("原数组为： ");
for(i=0;i<n;i++)
printf("%d ",A[i]);
printf("\n");
for(i=0;i<n/2;i++)
{
max = min = i;
for(j=i+1;j<n-i;j++) //同时选择最大值和最小值
{
if(A[j]>A[max])
max=j;
else if(A[j]<A[min])
min=j;
}
if (max != j-1) //把最大值换到最后
{
temp=A[j-1];
A[j-1]=A[max];
A[max]=temp;
}
if (i != min) //把最小值换到最前面
{ //注意这个语句：因为我移动的是下标，当min == j-1时，因在上面的语句中A[j-1]和A[max]的值发生了交换，需要把min移到max位置
if (min == j-1)
min = max;
temp=A[i];
A[i]=A[min];
A[min]=temp;
}
}
printf("调整后的数组为：");
for(i=0;i<n;i++)
printf("%d ",A[i]);
printf("\n ");
getchar();
return 0;
}
10 楼
InitInstance [专家分：8720] 发布于 2006-06-27 12:58:00
一个算法不单要时间复杂度和空间等要求（这当然最重要），有时后容易理解也是很重要的一方面。一目了然且时间复杂度低的算法容易很快的让人接受。很高兴看到那么多人的参与，这只是比较简单的算法，以后再写些算法来，一起研究并不断的改进好了......
我来回复
您所在位置：