c - 将数组分成两部分，对每个部分进行排序，然后重新组合成单​​个数组

Question

我一直在开发一个程序，该程序生成随机数数组，将数组分成两个相等的部分，对每个部分进行排序，然后将这两个部分重新组合回单个排序数组。当尝试插入排序时，我得到以下信息:

http://i.imgur.com/70J4eLG.png

你们能看出前半部分数组排序正确但后半部分排序不正确的原因吗？

int cmpfunc (const void *a, const void *b) {
    return ( *(int*)a - *(int*)b );
}

void insertion_sort (int ar[], int size) {
    int c, d, t;
    for (c = 1; c <= size - 1; c++){
        d = c;

        while(d > 0 && ar[d] < ar[d - 1]) {
            t = ar[d];
            ar[d] = ar[d - 1];
            ar[d - 1] = t;

            d--;
        }
    }
}

void check_sort (int ara[], int size_t) {
    int b;
    int c_i;

    c_i = 0;

    for  (b = 1; b < size_t; b++) {
        if (ara[b - 1] > ara[b]) {
            printf("Array is not sorted correctly\n");  
            break;
        } else {
            c_i++;
        }
    }

    if (c_i == size_t - 1) {
        printf("Array is sorted correctly\n");
    }
}

void combine_array(int a_ar[], int b_ar[], int c_ar[], int size_1, int size_2) {
    int i, j, k;
    i, j, k = 0;

    while (i < size_1 && j < size_2) {
        if (a_ar[i] < b_ar[j]) {
            c_ar[k] = a_ar[i];
            i++;
        } else {
            c_ar[k] = b_ar[j];
            j++;
        }
        k++;
    }

    if (i >= size_1) {
        while (j < size_2) {
            c_ar[k] = b_ar[j];
            j++;
            k++;
        }
    }

    if (j >= size_2) {
        while (i < size_1) {
            c_ar[k] = a_ar[i];
            i++;
            k++;
        }
    }
}

int main (int argc, char *argv[]) {
    int a_size, t_num;
    char s_type;
    int i, j, k; 
    int two_s[1];

    a_size = atoi(argv[1]);
    t_num = atoi(argv[2]);
    s_type = argv[3][0];

    int array_m[a_size];

    for (i = 0; i < a_size; i++) {
        array_m[i] = rand();
    }


    for (i = 0; i < a_size; i++) {
        printf("%d \n", array_m[i]);
    }

    printf("\n");

    if (t_num == 2) {
        two_s[0] = ((a_size/2));
        two_s[1] = (a_size);
        int array_s1[two_s[0]];
        int array_s2[two_s[0]];

        printf("First half \n");

        for (j = 0; j < two_s[0]; j ++) {
            array_s1[j] = array_m[j];
            printf("%d \n", array_s1[j]);
        }

        printf("Second half \n");

        for (k = two_s[0]; k < two_s[1]; k++) {
            array_s2[k] = array_m[k];
            printf("%d \n", array_s2[k]);
        }

        printf("Size of second array: %d", (two_s[1] - two_s[0]));

    printf("\n");

    check_sort(array_m, a_size);

    if (s_type == 'I') { //Insertion sort

        insertion_sort(array_s1, two_s[0]);
        insertion_sort(array_s2, two_s[0]);

        printf("Sorted first half \n");

        for (i = 0; i < two_s[0]; i++) {
            printf("%d \n", array_s1[i]);
        }

        printf("Sorted second half \n");

        for (i = 0; i < two_s[0]; i++) {
            printf("%d \n", array_s2[i]);
        }       

        //combine_array(array_s1, array_s2, array_m, two_s[0], two_s[0]);

        printf("\n");

        printf("Combined and sorted \n");

        for (i = 0; i < a_size; i++) {
            printf("%d \n", array_m[i]);
        }

        check_sort(array_m, a_size);
    }

    if (s_type == 'Q') { //Quick sort

        qsort(array_m, a_size, sizeof(int), cmpfunc);

        printf("\n");

        for (i = 0; i < a_size; i++) {
            printf("%d \n", array_m[i]);
        }
    }
    }

}

Answer 1

在您的示例中，array_s2 是一个包含 5 个元素的数组。在以下 for 循环中，您将写入数组边界之外的内存:

for (k = two_s[0]; k < two_s[1]; k++) {
    array_s2[k] = array_m[k];
    printf("%d \n", array_s2[k]);
}

k 的初始值为 5，最终值为 9，超出了 array_s2 的范围。尝试以下方法来正确索引数组:

for (k = two_s[0]; k < two_s[1]; k++) {
        array_s2[k - two_s[0]] = array_m[k];
        printf("%d \n", array_s2[k - two_s[0]]);
    }