设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › C\C++交流 › C拓展阅读归并排序
返回列表 发新帖
查看: 645|回复: 4

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

[复制链接]
houqing1999
发表于 2023-6-22 14:24:53 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
本帖最后由 houqing1999 于 2023-6-24 20:35 编辑

这个代码不能运行，怎么修改，使用的是VisualStudio 如图 微信图片_20230622142324.png 
#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[k++] = array[start1] < array[start2] ? array[start1++] : array[start2++];
    }

    while (start1 <= end1)
    {
        reg[k++] = array[start1++];
    }

    while (start2 <= end2)
    {
        reg[k++] = array[start2++];
    }

    for (k = start; k <= end; k++)
    {
        array[k] = reg[k];
    }
}

void merge_sort(int array[], int length)
{
    int reg[length];
    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[0]);
    merge_sort(array, length);

    printf("排序后的结果是：");
    for (i = 0; i < length; i++)
    {
        printf("%d ", array[i]);
    }
    putchar('\n');

    return 0;
}
最佳答案
月排行榜 / 总排行榜
isdkz
2023-6-22 14:28:30
这个问题发生在 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[k++] = array[start1] < array[start2] ? array[start1++] : array[start2++];
    }

    while (start1 <= end1)
    {
        reg[k++] = array[start1++];
    }

    while (start2 <= end2)
    {
        reg[k++] = array[start2++];
    }

    for (k = start; k <= end; k++)
    {
        array[k] = reg[k];
    }
}

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[0]);
    merge_sort(array, length);

    printf("排序后的结果是：");
    for (i = 0; i < length; i++)
    {
        printf("%d ", array[i]);
    }
    putchar('\n');

    return 0;
}

在这个修复版本中，我使用了  malloc()  函数来创建一个动态数组。记住，当你使用  malloc()  为一个变量分配内存时，你需要在后面使用  free()  来释放这个内存，避免内存泄露。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

isdkz
发表于 2023-6-22 14:28:30 | 显示全部楼层    本楼为最佳答案   
这个问题发生在 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[k++] = array[start1] < array[start2] ? array[start1++] : array[start2++];
    }

    while (start1 <= end1)
    {
        reg[k++] = array[start1++];
    }

    while (start2 <= end2)
    {
        reg[k++] = array[start2++];
    }

    for (k = start; k <= end; k++)
    {
        array[k] = reg[k];
    }
}

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[0]);
    merge_sort(array, length);

    printf("排序后的结果是：");
    for (i = 0; i < length; i++)
    {
        printf("%d ", array[i]);
    }
    putchar('\n');

    return 0;
}

在这个修复版本中，我使用了  malloc()  函数来创建一个动态数组。记住，当你使用  malloc()  为一个变量分配内存时，你需要在后面使用  free()  来释放这个内存，避免内存泄露。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

houqing1999
 楼主| 发表于 2023-6-24 19:15:52 | 显示全部楼层
isdkz 发表于 2023-6-22 14:28
这个问题发生在 Visual Studio 环境中，它不支持变长数组（Variable Length Array，VLA）。在 C99 标准中引 ...

归并排序能否解释一下里面函数的意思以及代码的具体实现，需要另开贴的话，您说
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

isdkz
发表于 2023-6-24 19:18:33 | 显示全部楼层
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[k++] = array[start1] < array[start2] ? array[start1++] : array[start2++]; // 将较小的元素放入临时数组
    }

    while (start1 <= end1) // 如果左半部分还有剩余元素，将它们复制到临时数组
    {
        reg[k++] = array[start1++];
    }

    while (start2 <= end2) // 如果右半部分还有剩余元素，将它们复制到临时数组
    {
        reg[k++] = array[start2++];
    }

    for (k = start; k <= end; k++) // 将临时数组的内容复制回原数组
    {
        array[k] = reg[k];
    }
}

这就是归并排序算法的基本实现。它是一种非常有效的排序算法，尤其是对于大型数据集。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

Wei-Yuanzhe
发表于 2023-7-5 21:12:05 | 显示全部楼层

回帖奖励 +10 鱼币

都好厉害
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-24 09:15

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表