回 帖 发 新 帖 刷新版面

主题:分享个排序算法...........

#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个回复)

沙发

有创意呦:)可以叫两端选择法吧.

板凳

不错不错呀。呵呵

3 楼

改进(不用判断元素个数是否偶数了,把变量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 楼

看了N久 就是没看懂
我果然菜
大虾能否解释下算法?

5 楼

可以像euc所说的把它叫做双端选择排序吧,我上面写的是从小到大排序(改动一下就很容易变成从大到小了)第一次:i=0,把最大和最小的数找出来,后把最大的数跟最后一个数交换[大数放到最后],最小的数跟第一个数交换[小数放到最前];第二次:i=1,由于第一个位置和最后一个位置已经排好,在剩下的n-2个数里再找出最大和最小的两个数然后重复第一步的操作....如此直至排好序。这个算法比较好理解且时间复杂度也不是很大。

6 楼

自己想的?有点象快速排序.

7 楼

这是选择排序法的一个变种,原来也看到一个两端冒泡法,原理和它差不多,两端同时比较,看起来快了,其实速度差不多,时间复杂度仍然是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 楼

楼上有点错误,容我改过来.

9 楼

改过来了:
#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 楼

一个算法不单要时间复杂度和空间等要求(这当然最重要),有时后容易理解也是很重要的一方面。一目了然且时间复杂度低的算法容易很快的让人接受。很高兴看到那么多人的参与,这只是比较简单的算法,以后再写些算法来,一起研究并不断的改进好了......

我来回复

您尚未登录,请登录后再回复。点此登录或注册