我已经尝试完成3天了,即使多次使用调试工具,我也找不到哪里出了问题。适用于2数组的大小,但适用于输入为55、34、76、12、45、76的大小为6的数组,排序后打印的数组得到不同的值,我的代码是:
#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>
void sort(int arr[], int beg, int end);
void merg(int arr[], int beg, int mid, int end);
int main(void)
{
int n = get_int("How many numbers? ");
int* arr = malloc(sizeof(int)*n);
for (int i = 0; i < n; i++)
{
printf("Enter %i Element of array: ", i + 1);
arr[i] = get_int("");
}
sort(arr, 0, n-1);
for (int i = 0; i < n; i++)
{
printf("%i ", arr[i]);
}
printf("\n");
}
void sort(int arr[], int beg, int end)
{
if (beg != end)
{
int mid = (beg + end) / 2;
sort(arr, beg, mid);
sort(arr + mid + 1, mid + 1, end);
merg(arr, beg, mid, end);
}
}
void merg(int arr[],int beg, int mid, int end)
{
int sizel = mid - beg + 1;
int sizer = end - mid;
int* left = malloc(sizeof(int) * (sizel));
int* right = malloc(sizeof(int) * sizer);
for (int i = 0; i < sizel; i++)
{
left[i] = arr[beg + i];
}
for (int i = 0; i < sizer; i++)
{
right[i] = arr[mid + 1 + i];
}
int i = 0, j = 0, k = 0;
for (k = 0; k <= end; k++)
{
if (i == sizel)
{
arr[k] = right[j];
j++;
}
else if (j == sizer)
{
arr[k] = left[i];
i++;
}
else
{
if (left[i] < right[j])
{
arr[k] = left[i];
i++;
}
else
{
arr[k] = right [j];
j++;
}
}
}
free(left);free(right);
return;
}
您的主要问题是您正在混淆符号。您可以通过start, length
或base, lo, hi
来标识子范围。
您有这个,其中一行执行一种方式,另一行执行另一种方式,但是做得不好:
sort(arr, beg, mid);
sort(arr + mid + 1, mid + 1, end);
您需要:
sort(arr, beg, mid);
sort(arr, mid + 1, end);
即始终使用start, lo, hi
表示法。就目前而言,您要告诉代码访问数组之外的很长一段路。这并不意味着您的程序会自动崩溃,但会导致不确定的行为和错误的结果。
您应该创建一个类似“转储数组”的函数:
static void dump_array(const char *tag, int size, const int data[size])
{
printf("%s (%d):", tag, size);
for (int i = 0; i < size; i++)
printf(" %d", data[i]);
putchar('\n');
}
这使您可以在需要时打印阵列。然后,在对sort()
的第一个递归调用之后,您输入:
dump_array("After 1st sub-sort", mid - beg + 1, &arr[beg]);
这样您就可以看到到达那里的内容,在第二次递归调用之后,在merg()之后的第三次调用之后,再看到。您也可以在其他地方打印(也可以选择输入该功能)。
在这种情况下,也许您应该对函数使用不同的设计:
static void dump_array(const char *tag, const int *data, int lo, int hi)
{
printf("%s (%d:%d):", tag, lo, hi);
for (int i = lo; i <= hi; i++)
printf(" %d", data[i]);
putchar('\n');
}
现在您可以写:
sort(arr, beg + 0, mid);
dump_array("After 1st sub-sort", arr, beg + 0, mid);
sort(arr, mid + 1, end);
dump_array("After 2nd sub-sort", arr, mid + 1, end);
此代码严重地重做了merg()
函数,该函数存在许多问题。它也添加了我推荐的工具。
#include <assert.h>
#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static void sort(int arr[], int beg, int end);
static void merg(int arr[], int beg, int mid, int end);
static void dump_array(const char *tag, const int *data, int lo, int hi);
int main(void)
{
int n = get_int("How many numbers? ");
int *arr = malloc(sizeof(int) * n);
assert(arr != NULL);
for (int i = 0; i < n; i++)
{
printf("Enter %i Element of array", i + 1);
arr[i] = get_int(": ");
}
sort(arr, 0, n - 1);
for (int i = 0; i < n; i++)
{
printf("%i ", arr[i]);
}
printf("\n");
}
static void sort(int arr[], int beg, int end)
{
if (beg != end)
{
int mid = (beg + end) / 2;
dump_array("-->> sort()", arr, beg, end);
sort(arr, beg, mid);
dump_array("After 1st sub-sort", arr, beg + 0, mid);
sort(arr, mid + 1, end);
dump_array("After 2nd sub-sort", arr, mid + 1, end);
merg(arr, beg, mid, end);
dump_array("<<-- sort()", arr, beg, end);
}
}
static void merg(int arr[], int beg, int mid, int end)
{
int sizel = mid - beg + 1;
int sizer = end - mid;
int *left = malloc(sizeof(int) * (sizel));
int *right = malloc(sizeof(int) * sizer);
assert(left != NULL && right != NULL);
memcpy(left, arr + beg, sizel * sizeof(int));
memcpy(right, arr + mid + 1, sizer * sizeof(int));
int i = 0;
int j = 0;
int k = beg;
while (i < sizel && j < sizer)
{
if (left[i] < right[j])
arr[k++] = left[i++];
else
arr[k++] = right[j++];
}
/* Only one of these loop bodies executes */
while (i < sizel)
arr[k++] = left[i++];
while (j < sizer)
arr[k++] = right[j++];
free(left);
free(right);
}
static void dump_array(const char *tag, const int *data, int lo, int hi)
{
printf("%s (%d:%d):", tag, lo, hi);
for (int i = lo; i <= hi; i++)
printf(" %d", data[i]);
putchar('\n');
}
我测试了一个名为data
的文件,其中包含:
11
19
66
71
69
91
46
14
38
77
97
34
第一行11表示条目数;然后在10到99之间有11个随机数。运行ms71 < data
的输出(忽略输入提示-由于从文件读取的数据未回显而显得愚蠢),输出为:
-->> sort() (0:10): 19 66 71 69 91 46 14 38 77 97 34
-->> sort() (0:5): 19 66 71 69 91 46
-->> sort() (0:2): 19 66 71
-->> sort() (0:1): 19 66
After 1st sub-sort (0:0): 19
After 2nd sub-sort (1:1): 66
<<-- sort() (0:1): 19 66
After 1st sub-sort (0:1): 19 66
After 2nd sub-sort (2:2): 71
<<-- sort() (0:2): 19 66 71
After 1st sub-sort (0:2): 19 66 71
-->> sort() (3:5): 69 91 46
-->> sort() (3:4): 69 91
After 1st sub-sort (3:3): 69
After 2nd sub-sort (4:4): 91
<<-- sort() (3:4): 69 91
After 1st sub-sort (3:4): 69 91
After 2nd sub-sort (5:5): 46
<<-- sort() (3:5): 46 69 91
After 2nd sub-sort (3:5): 46 69 91
<<-- sort() (0:5): 19 46 66 69 71 91
After 1st sub-sort (0:5): 19 46 66 69 71 91
-->> sort() (6:10): 14 38 77 97 34
-->> sort() (6:8): 14 38 77
-->> sort() (6:7): 14 38
After 1st sub-sort (6:6): 14
After 2nd sub-sort (7:7): 38
<<-- sort() (6:7): 14 38
After 1st sub-sort (6:7): 14 38
After 2nd sub-sort (8:8): 77
<<-- sort() (6:8): 14 38 77
After 1st sub-sort (6:8): 14 38 77
-->> sort() (9:10): 97 34
After 1st sub-sort (9:9): 97
After 2nd sub-sort (10:10): 34
<<-- sort() (9:10): 34 97
After 2nd sub-sort (9:10): 34 97
<<-- sort() (6:10): 14 34 38 77 97
After 2nd sub-sort (6:10): 14 34 38 77 97
<<-- sort() (0:10): 14 19 34 38 46 66 69 71 77 91 97
14 19 34 38 46 66 69 71 77 91 97
可能有优化的空间,这样当要排序的数组只有一个元素时,代码就不会递归。