[已解决]排序漏洞(第一次正常运行, 再次运行出差错)

Martine

#include <stdio.h>
#include <time.h>
void insertSort(int arr[] , int);
void swap(int*, int *);

void insertSort(int arr[], int len){
        int i, j;
        for(i=0; i<len; i++){
                j = i+1;
                while((j>0) && (arr[j]<arr[j-1])){
                        swap(&arr[j], &arr[j-1]);
                        j=j-1;
                }
        }
}

void swap(int *x, int *y){        
        *x ^= *y; *y ^= *x; *x ^= *y;
}

int main(void)
{
        int array[] = {73, 108, 111, 101, 70, 105, 104, 67};
        int i, len;
        time_t begin, end;

        begin = time(NULL);
        len = sizeof(array)/sizeof(int);

        insertSort(array, len);

        printf("After sort::");
        for(i=0; i<len; i++){
                printf("%d  ", array[i]);
        }
        putchar('\n');

        end = time(NULL);
        printf("spend %d sec!\n", end-begin);
        return 0;
}

最佳答案

月排行榜 / 总排行榜

ba21

2018-3-18 13:40:50

Martine 发表于 2018-3-18 13:02
问题依旧

我这linux 下测式也没问题，不过代码确定是有问题的。你改下看看你那会正常不。如下：

void insertSort(int arr[], int len){
        int i, j;
        for(i=0; i<len; i++){
                j = i+1;
                while((j>0) && (arr[j]<arr[j-1])){
                        swap(&arr[j], &arr[j-1]);
                        j=j-1;
                }
        }
}
改成
void insertSort(int arr[], int len){
        int i, j;
        for(i=0; i<len-1; i++){ // j=i+1 如果是8个元素，那么下标最大是7; j=7+1 ，j就越界了。
                j = i+1;
                while(arr[j]<arr[j-1]){ // (j>0) 去掉，因为多余
                        swap(&arr[j], &arr[j-1]);
                        j=j-1;
                }
        }
}

跳转到最佳答案楼层

ba21

windows 下测试没问题。
是不是你编译命令不正确？
gcc 1.c  && ./a.out

Martine

ba21 发表于 2018-3-18 11:35
windows 下测试没问题。
是不是你编译命令不正确？
gcc 1.c  && ./a.out

问题依旧

ba21

Martine 发表于 2018-3-18 13:02
问题依旧

我这linux 下测式也没问题，不过代码确定是有问题的。你改下看看你那会正常不。如下：

void insertSort(int arr[], int len){
        int i, j;
        for(i=0; i<len; i++){
                j = i+1;
                while((j>0) && (arr[j]<arr[j-1])){
                        swap(&arr[j], &arr[j-1]);
                        j=j-1;
                }
        }
}
改成
void insertSort(int arr[], int len){
        int i, j;
        for(i=0; i<len-1; i++){ // j=i+1 如果是8个元素，那么下标最大是7; j=7+1 ，j就越界了。
                j = i+1;
                while(arr[j]<arr[j-1]){ // (j>0) 去掉，因为多余
                        swap(&arr[j], &arr[j-1]);
                        j=j-1;
                }
        }
}

t6am3

楼主， 我用VC编译器运行多少次都没问题。

t6am3

t6am3 发表于 2018-3-18 14:51
楼主， 我用VC编译器运行多少次都没问题。

确实你的j= i+1那里会越界欸。