[已解决]C拓展阅读归并排序

houqing1999

这个代码不能运行，怎么修改，使用的是VisualStudio 如图

1. #define _CRT_SECURE_NO_WARNINGS 1//归并排序
   
2. #include <stdio.h>
   
3. 
   
4. void merge_sort(int array[], int length);
   
5. void merge_sort_recursive(int array[], int reg[], int start, int end);
   
6. 
   
7. void merge_sort_recursive(int array[], int reg[], int start, int end)
   
8. {
   
9.     if (start >= end)
   
10.     {
    
11.         return;
    
12.     }
    
13. 
    
14.     int k = start;
    
15.     int length = end - start;
    
16.     int mid = (length / 2) + start;
    
17.     int start1 = start, end1 = mid;
    
18.     int start2 = mid + 1, end2 = end;
    
19. 
    
20.     merge_sort_recursive(array, reg, start1, end1);
    
21.     merge_sort_recursive(array, reg, start2, end2);
    
22. 
    
23.     while (start1 <= end1 && start2 <= end2)
    
24.     {
    
25.         reg[k++] = array[start1] < array[start2] ? array[start1++] : array[start2++];
    
26.     }
    
27. 
    
28.     while (start1 <= end1)
    
29.     {
    
30.         reg[k++] = array[start1++];
    
31.     }
    
32. 
    
33.     while (start2 <= end2)
    
34.     {
    
35.         reg[k++] = array[start2++];
    
36.     }
    
37. 
    
38.     for (k = start; k <= end; k++)
    
39.     {
    
40.         array[k] = reg[k];
    
41.     }
    
42. }
    
43. 
    
44. void merge_sort(int array[], int length)
    
45. {
    
46.     int reg[length];
    
47.     merge_sort_recursive(array, reg, 0, length - 1);
    
48. }
    
49. 
    
50. int main(void)
    
51. {
    
52.     int array[] = { 73, 108, 111, 118, 101, 70, 105, 115, 104, 67, 46, 99, 111, 109 };
    
53.     int i, length;
    
54. 
    
55.     length = sizeof(array) / sizeof(array[0]);
    
56.     merge_sort(array, length);
    
57. 
    
58.     printf("排序后的结果是：");
    
59.     for (i = 0; i < length; i++)
    
60.     {
    
61.         printf("%d ", array[i]);
    
62.     }
    
63.     putchar('\n');
    
64. 
    
65.     return 0;
    
66. }

复制代码

最佳答案

月排行榜 / 总排行榜

isdkz

2023-6-22 14:28:30

这个问题发生在 Visual Studio 环境中，它不支持变长数组（Variable Length Array，VLA）。在 C99 标准中引入了变长数组，但是 C++ 和某些 C 编译器（包括 Visual Studio 的 MSVC 编译器）并不支持这个特性。在你的代码中，你试图根据输入的参数创建一个数组，这在 Visual Studio 中是不允许的。

这个问题的解决方案是使用动态内存分配。下面是一个修复后的版本：

1. #define _CRT_SECURE_NO_WARNINGS 1
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. 
   
5. void merge_sort(int array[], int length);
   
6. void merge_sort_recursive(int array[], int reg[], int start, int end);
   
7. 
   
8. void merge_sort_recursive(int array[], int reg[], int start, int end)
   
9. {
   
10.     if (start >= end)
    
11.     {
    
12.         return;
    
13.     }
    
14. 
    
15.     int length = end - start;
    
16.     int mid = (length / 2) + start;
    
17.     int start1 = start, end1 = mid;
    
18.     int start2 = mid + 1, end2 = end;
    
19.     int k = start;
    
20. 
    
21.     merge_sort_recursive(array, reg, start1, end1);
    
22.     merge_sort_recursive(array, reg, start2, end2);
    
23. 
    
24.     while (start1 <= end1 && start2 <= end2)
    
25.     {
    
26.         reg[k++] = array[start1] < array[start2] ? array[start1++] : array[start2++];
    
27.     }
    
28. 
    
29.     while (start1 <= end1)
    
30.     {
    
31.         reg[k++] = array[start1++];
    
32.     }
    
33. 
    
34.     while (start2 <= end2)
    
35.     {
    
36.         reg[k++] = array[start2++];
    
37.     }
    
38. 
    
39.     for (k = start; k <= end; k++)
    
40.     {
    
41.         array[k] = reg[k];
    
42.     }
    
43. }
    
44. 
    
45. void merge_sort(int array[], int length)
    
46. {
    
47.     int* reg = (int*)malloc(length * sizeof(int)); // 使用 malloc 创建动态数组
    
48.     merge_sort_recursive(array, reg, 0, length - 1);
    
49.     free(reg); // 使用完毕后，别忘了释放内存
    
50. }
    
51. 
    
52. int main(void)
    
53. {
    
54.     int array[] = { 73, 108, 111, 118, 101, 70, 105, 115, 104, 67, 46, 99, 111, 109 };
    
55.     int i, length;
    
56. 
    
57.     length = sizeof(array) / sizeof(array[0]);
    
58.     merge_sort(array, length);
    
59. 
    
60.     printf("排序后的结果是：");
    
61.     for (i = 0; i < length; i++)
    
62.     {
    
63.         printf("%d ", array[i]);
    
64.     }
    
65.     putchar('\n');
    
66. 
    
67.     return 0;
    
68. }
    

复制代码

在这个修复版本中，我使用了  malloc()  函数来创建一个动态数组。记住，当你使用  malloc()  为一个变量分配内存时，你需要在后面使用  free()  来释放这个内存，避免内存泄露。

跳转到最佳答案楼层

isdkz

这个问题发生在 Visual Studio 环境中，它不支持变长数组（Variable Length Array，VLA）。在 C99 标准中引入了变长数组，但是 C++ 和某些 C 编译器（包括 Visual Studio 的 MSVC 编译器）并不支持这个特性。在你的代码中，你试图根据输入的参数创建一个数组，这在 Visual Studio 中是不允许的。

这个问题的解决方案是使用动态内存分配。下面是一个修复后的版本：

1. #define _CRT_SECURE_NO_WARNINGS 1
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. 
   
5. void merge_sort(int array[], int length);
   
6. void merge_sort_recursive(int array[], int reg[], int start, int end);
   
7. 
   
8. void merge_sort_recursive(int array[], int reg[], int start, int end)
   
9. {
   
10.     if (start >= end)
    
11.     {
    
12.         return;
    
13.     }
    
14. 
    
15.     int length = end - start;
    
16.     int mid = (length / 2) + start;
    
17.     int start1 = start, end1 = mid;
    
18.     int start2 = mid + 1, end2 = end;
    
19.     int k = start;
    
20. 
    
21.     merge_sort_recursive(array, reg, start1, end1);
    
22.     merge_sort_recursive(array, reg, start2, end2);
    
23. 
    
24.     while (start1 <= end1 && start2 <= end2)
    
25.     {
    
26.         reg[k++] = array[start1] < array[start2] ? array[start1++] : array[start2++];
    
27.     }
    
28. 
    
29.     while (start1 <= end1)
    
30.     {
    
31.         reg[k++] = array[start1++];
    
32.     }
    
33. 
    
34.     while (start2 <= end2)
    
35.     {
    
36.         reg[k++] = array[start2++];
    
37.     }
    
38. 
    
39.     for (k = start; k <= end; k++)
    
40.     {
    
41.         array[k] = reg[k];
    
42.     }
    
43. }
    
44. 
    
45. void merge_sort(int array[], int length)
    
46. {
    
47.     int* reg = (int*)malloc(length * sizeof(int)); // 使用 malloc 创建动态数组
    
48.     merge_sort_recursive(array, reg, 0, length - 1);
    
49.     free(reg); // 使用完毕后，别忘了释放内存
    
50. }
    
51. 
    
52. int main(void)
    
53. {
    
54.     int array[] = { 73, 108, 111, 118, 101, 70, 105, 115, 104, 67, 46, 99, 111, 109 };
    
55.     int i, length;
    
56. 
    
57.     length = sizeof(array) / sizeof(array[0]);
    
58.     merge_sort(array, length);
    
59. 
    
60.     printf("排序后的结果是：");
    
61.     for (i = 0; i < length; i++)
    
62.     {
    
63.         printf("%d ", array[i]);
    
64.     }
    
65.     putchar('\n');
    
66. 
    
67.     return 0;
    
68. }
    

复制代码

在这个修复版本中，我使用了  malloc()  函数来创建一个动态数组。记住，当你使用  malloc()  为一个变量分配内存时，你需要在后面使用  free()  来释放这个内存，避免内存泄露。

houqing1999

isdkz 发表于 2023-6-22 14:28
这个问题发生在 Visual Studio 环境中，它不支持变长数组（Variable Length Array，VLA）。在 C99 标准中引 ...

归并排序能否解释一下里面函数的意思以及代码的具体实现，需要另开贴的话，您说

isdkz

houqing1999 发表于 2023-6-24 19:15
归并排序能否解释一下里面函数的意思以及代码的具体实现，需要另开贴的话，您说

归并排序（Merge Sort）是一种常用的排序算法，基于分治法的原理。它将一个大问题分解为两个相同的小问题，然后解决这两个小问题，最后合并小问题的解来得到原问题的解。归并排序是稳定的排序方法，时间复杂度为O(nlogn)。

在这个程序中，有两个主要的函数： merge_sort() 和 merge_sort_recursive() 。

merge_sort() 函数接受两个参数：一个整数数组和数组的长度。它首先分配一个临时数组（用于存放排序结果），然后调用 merge_sort_recursive() 。

merge_sort_recursive() 函数是递归函数，也接受一个数组，一个临时数组，和两个索引（表示要排序的部分的开始和结束位置）。这个函数首先检查当前的片段是否已经为1（即开始索引等于结束索引），如果是，那么就返回（因为只有一个元素的片段已经排序）。

接下来，函数计算中间索引，并且递归地调用自身，一次处理左半部分和右半部分。然后，它使用临时数组来合并两个已排序的半部分，最后，它将排序好的部分复制回原来的数组。

这个程序中的归并排序过程可以大致分为以下步骤：

1. 递归地将数组分为两个半部分，直到数组的大小为1，此时认为数组已经排序。

2. 将两个排序的半部分进行合并，过程中将较小的元素先放入临时数组中。

3. 如果两个半部分的元素数量不等，将剩余的元素复制到临时数组。

4. 将临时数组的内容复制回原始数组，完成排序。

下面是具体的 merge_sort_recursive() 函数分解：

1. void merge_sort_recursive(int array[], int reg[], int start, int end)
   
2. {
   
3.     if (start >= end) // Base case: 当前数组段只有一个元素
   
4.     {
   
5.         return;
   
6.     }
   
7. 
   
8.     int length = end - start;
   
9.     int mid = (length / 2) + start; // 计算中间的索引
   
10.     int start1 = start, end1 = mid;
    
11.     int start2 = mid + 1, end2 = end;
    
12.     int k = start;
    
13. 
    
14.     // 递归地将数组分为两个半部分
    
15.     merge_sort_recursive(array, reg, start1, end1); // 左半部分
    
16.     merge_sort_recursive(array, reg, start2, end2); // 右半部分
    
17. 
    
18.     // 开始合并两个已排序的部分
    
19.     while (start1 <= end1 && start2 <= end2)
    
20.     {
    
21.         reg[k++] = array[start1] < array[start2] ? array[start1++] : array[start2++]; // 将较小的元素放入临时数组
    
22.     }
    
23. 
    
24.     while (start1 <= end1) // 如果左半部分还有剩余元素，将它们复制到临时数组
    
25.     {
    
26.         reg[k++] = array[start1++];
    
27.     }
    
28. 
    
29.     while (start2 <= end2) // 如果右半部分还有剩余元素，将它们复制到临时数组
    
30.     {
    
31.         reg[k++] = array[start2++];
    
32.     }
    
33. 
    
34.     for (k = start; k <= end; k++) // 将临时数组的内容复制回原数组
    
35.     {
    
36.         array[k] = reg[k];
    
37.     }
    
38. }
    

复制代码

这就是归并排序算法的基本实现。它是一种非常有效的排序算法，尤其是对于大型数据集。

Wei-Yuanzhe

都好厉害