5
回答
某EYE中的一篇文,各种经典排序算法总结,BUG
利用AWS快速构建适用于生产的无服务器应用程序,免费试用12个月>>>   

http://www.iteye.com/topic/1116829?page=2#2269934

比如其中

简单选择排序的过程

 

描述:给定待排序序列A[ 1......n ] ,选择出第i小元素,并和A[i]交换,这就是一趟简单选择排序。

文章中是

 

void simpleSelectionSort1(int *a,int n) 

    int i,j,index; 
    //1.进行n-1趟选择,每次选出第i小记录 
    for(i=1;i<n;i++){ 
        index=i; 
        //2.选择第i小记录为a[index] 
        for(j=i+1;j<=n;j++) 
            if(a[j]<a[index]) 
                index=j; 
        //3.与第i个记录交换 
        if(index!=i){ 
            a[i]=a[i]+a[index]; 
            a[index]=a[i]-a[index]; 
            a[i]=a[i]-a[index]; 
        } 
    } 
}

既然是C语言,数组下标是从0起始的,其中两个FOR的地方应该改下吧

void simpleSelectionSort1(int *a,int n) 

    int i,j,index; 
    //1.进行n-1趟选择,每次选出第i小记录 
    for(i=0;i<n-1;i++){ 
        index=i; 
        //2.选择第i小记录为a[index] 
        for(j=i+1;j<n;j++) 
            if(a[j]<a[index]) 
                index=j; 
        //3.与第i个记录交换 
        if(index!=i){ 
            a[i]=a[i]+a[index]; 
            a[index]=a[i]-a[index]; 
            a[i]=a[i]-a[index]; 
        } 
    } 
}

 

 

举报
ddatsh
发帖于6年前 5回/413阅
共有5个答案 最后回答: 6年前

第二个改进的排序也是不对的


void simpleSelectionSort2(int *a,int n) 

    int index,i; 
    if(n==1) 
        return; 
    //1.选择待排序序列a中的最小记录,其下标为index 
    for(index=i=0;i<n;i++){ 
        if(a[i]<a[index]) 
            index=i; 
    } 
    //2.最小记录与待排序序列首元素进行交换 
    if(index!=1){ 
        a[1]=a[1]+a[index]; 
        a[index]=a[1]-a[index]; 
        a[1]=a[1]-a[index]; 
    } 
    //3.待排序序列元素个数减少,递归对剩下的无序序列排序 
    simpleSelectionSort2(a+1,n-1); 
}

 

a[1]改成a[0]

写了点辅助用的

void simpleSelectionSort2(int *a,int n) 

    printf("n=%d\n",n);
    int index,i,tmp; 
    if(n==1) 
    {
        printf("return\n");
        return; 
    }
    //1.选择待排序序列a中的最小记录,其下标为index 
    for(index=i=0;i<n;i++){ 
        printf("i=%d index=%d a[i(%d)]=%d, a[index(%d)]=%d",i,index,i,a[i],index,a[index]);
        if(a[i]>a[index]) 
        {
            //printf("%d %d %d %d\n",i,index,a[i],a[index]);
            index=i; 
            printf(" need swap, index=%d\n",index);
        }else
        {
            printf(" nothing\n");
        }
    } 
    //2.最小记录与待排序序列首元素进行交换 
    if(index!=0){ 
        printf("change,a[0]=%d,a[index=]=%d",a[0],a[index]);
        tmp=a[0];
        a[0]=a[index];
        a[index]=tmp;
        /*a[0]=a[0]+a[index]; 
        a[index]=a[0]-a[index]; 
        a[1]=a[0]-a[index];  */
    } 
    printf("\n");
    //3.待排序序列元素个数减少,递归对剩下的无序序列排序 
    simpleSelectionSort2(a+1,n-1); 
}

 

 

顶部