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

Martine

1. #include <stdio.h>
   
2. #include <time.h>
   
3. void insertSort(int arr[] , int);
   
4. void swap(int*, int *);
   
5. 
   
6. void insertSort(int arr[], int len){
   
7.         int i, j;
   
8.         for(i=0; i<len; i++){
   
9.                 j = i+1;
   
10.                 while((j>0) && (arr[j]<arr[j-1])){
    
11.                         swap(&arr[j], &arr[j-1]);
    
12.                         j=j-1;
    
13.                 }
    
14.         }
    
15. }
    
16. 
    
17. void swap(int *x, int *y){       
    
18.         *x ^= *y; *y ^= *x; *x ^= *y;
    
19. }
    
20. 
    
21. int main(void)
    
22. {
    
23.         int array[] = {73, 108, 111, 101, 70, 105, 104, 67};
    
24.         int i, len;
    
25.         time_t begin, end;
    
26. 
    
27.         begin = time(NULL);
    
28.         len = sizeof(array)/sizeof(int);
    
29. 
    
30.         insertSort(array, len);
    
31. 
    
32.         printf("After sort::");
    
33.         for(i=0; i<len; i++){
    
34.                 printf("%d  ", array[i]);
    
35.         }
    
36.         putchar('\n');
    
37. 
    
38.         end = time(NULL);
    
39.         printf("spend %d sec!\n", end-begin);
    
40.         return 0;
    
41. }
    

复制代码

最佳答案

月排行榜 / 总排行榜

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那里会越界欸。