C拓展阅读归并排序
本帖最后由 houqing1999 于 2023-6-24 20:35 编辑这个代码不能运行，怎么修改，使用的是VisualStudio 如图
#define _CRT_SECURE_NO_WARNINGS 1//归并排序
#include <stdio.h>
void merge_sort(int array[], int length);
void merge_sort_recursive(int array[], int reg[], int start, int end);
void merge_sort_recursive(int array[], int reg[], int start, int end)
{
if (start >= end)
{
return;
}
int k = start;
int length = end - start;
int mid = (length / 2) + start;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
merge_sort_recursive(array, reg, start1, end1);
merge_sort_recursive(array, reg, start2, end2);
while (start1 <= end1 && start2 <= end2)
{
reg = array < array ? array : array;
}
while (start1 <= end1)
{
reg = array;
}
while (start2 <= end2)
{
reg = array;
}
for (k = start; k <= end; k++)
{
array = reg;
}
}
void merge_sort(int array[], int length)
{
int reg;
merge_sort_recursive(array, reg, 0, length - 1);
}
int main(void)
{
int array[] = { 73, 108, 111, 118, 101, 70, 105, 115, 104, 67, 46, 99, 111, 109 };
int i, length;
length = sizeof(array) / sizeof(array);
merge_sort(array, length);
printf("排序后的结果是：");
for (i = 0; i < length; i++)
{
printf("%d ", array);
}
putchar('\n');
return 0;
} 这个问题发生在 Visual Studio 环境中，它不支持变长数组（Variable Length Array，VLA）。在 C99 标准中引入了变长数组，但是 C++ 和某些 C 编译器（包括 Visual Studio 的 MSVC 编译器）并不支持这个特性。在你的代码中，你试图根据输入的参数创建一个数组，这在 Visual Studio 中是不允许的。
这个问题的解决方案是使用动态内存分配。下面是一个修复后的版本：
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
void merge_sort(int array[], int length);
void merge_sort_recursive(int array[], int reg[], int start, int end);
void merge_sort_recursive(int array[], int reg[], int start, int end)
{
if (start >= end)
{
return;
}
int length = end - start;
int mid = (length / 2) + start;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
int k = start;
merge_sort_recursive(array, reg, start1, end1);
merge_sort_recursive(array, reg, start2, end2);
while (start1 <= end1 && start2 <= end2)
{
reg = array < array ? array : array;
}
while (start1 <= end1)
{
reg = array;
}
while (start2 <= end2)
{
reg = array;
}
for (k = start; k <= end; k++)
{
array = reg;
}
}
void merge_sort(int array[], int length)
{
int* reg = (int*)malloc(length * sizeof(int)); // 使用 malloc 创建动态数组
merge_sort_recursive(array, reg, 0, length - 1);
free(reg); // 使用完毕后，别忘了释放内存
}
int main(void)
{
int array[] = { 73, 108, 111, 118, 101, 70, 105, 115, 104, 67, 46, 99, 111, 109 };
int i, length;
length = sizeof(array) / sizeof(array);
merge_sort(array, length);
printf("排序后的结果是：");
for (i = 0; i < length; i++)
{
printf("%d ", array);
}
putchar('\n');
return 0;
}
在这个修复版本中，我使用了malloc()函数来创建一个动态数组。记住，当你使用malloc()为一个变量分配内存时，你需要在后面使用free()来释放这个内存，避免内存泄露。 isdkz 发表于 2023-6-22 14:28
这个问题发生在 Visual Studio 环境中，它不支持变长数组（Variable Length Array，VLA）。在 C99 标准中引 ...
归并排序能否解释一下里面函数的意思以及代码的具体实现，需要另开贴的话，您说 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() 函数分解：
void merge_sort_recursive(int array[], int reg[], int start, int end)
{
if (start >= end) // Base case: 当前数组段只有一个元素
{
return;
}
int length = end - start;
int mid = (length / 2) + start; // 计算中间的索引
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
int k = start;
// 递归地将数组分为两个半部分
merge_sort_recursive(array, reg, start1, end1); // 左半部分
merge_sort_recursive(array, reg, start2, end2); // 右半部分
// 开始合并两个已排序的部分
while (start1 <= end1 && start2 <= end2)
{
reg = array < array ? array : array; // 将较小的元素放入临时数组
}
while (start1 <= end1) // 如果左半部分还有剩余元素，将它们复制到临时数组
{
reg = array;
}
while (start2 <= end2) // 如果右半部分还有剩余元素，将它们复制到临时数组
{
reg = array;
}
for (k = start; k <= end; k++) // 将临时数组的内容复制回原数组
{
array = reg;
}
}
这就是归并排序算法的基本实现。它是一种非常有效的排序算法，尤其是对于大型数据集。 都好厉害{:10_257:}
页:
[1]