某EYE中的一篇文，各种经典排序算法总结，BUG

Question

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]; 
        } 
    } 
}

 

 

Answer 1

嗯，想想确实是惯性思维了 傻了:)

Answer 2

LZ惯性思维了...很多算法书下标都是以1开始的

Answer 3

“给定待排序序列A[ 1......n ]” ，这句话的意思不是说这个序列的下标从1开始么？

Answer 4

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

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=%dn",n);
    int index,i,tmp; 
    if(n==1) 
    {
        printf("returnn");
        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 %dn",i,index,a[i],a[index]);
            index=i; 
            printf(" need swap, index=%dn",index);
        }else
        {
            printf(" nothingn");
        }
    } 
    //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); 
}

 

 

Answer 5