little_boy 发表于 2020-2-21 10:06

C语言归并排序算法求助

本帖最后由 little_boy 于 2020-2-21 13:08 编辑

大佬们帮忙看下算法哪里有问题,编译环境:vs2019
问题已解决，感谢各位大佬的帮助，尤其是@tony666的回复让我找到了问题的所在，修改后的代码在10#
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int intCmp(void* vp1, void* vp2);
int* initialize(int* arr, int n);
void assign(void*, void*, int);
void merge(void* arr, int p, int q, int r, int elemSize, int (*cmpFunc)(void*, void*));
void mergeSort(void* arr, int p, int r, int elemSize, int (*cmpFunc)(void*, void*));

int main()
{
      int n;
      printf("Please input a number:");
      scanf("%d", &n);
      int* arr = (int*)malloc(n * sizeof(int));
      clock_t start = clock();
      initialize(arr, n);
      clock_t end = clock();
      printf("inintalize %d numbers costs %lfs\n",n, (double)(end - start)/CLOCKS_PER_SEC);
      printf("排序前:\n");
      for (int i = 0; i < n; i++)
      {
                printf("%-5d ", arr);
                (i + 1) % 10 == 0 ? printf("\n") :printf("") ;
      }
      start = clock();
      mergeSort(arr, 0, n - 1, sizeof(int), intCmp);
      end = clock();
      printf("\ninsertionSort %d numbers costs %lfs\n",n, (double)(end - start) / CLOCKS_PER_SEC);
      printf("排序后:\n");
      for (int i = 0; i < n; i++)
      {
                printf("%-5d ", arr);
                (i + 1) % 10 == 0 ? printf("\n") : printf("");
      }
      free(arr);
      return 0;
}

int* initialize(int* arr,int n)
{
      for (int i = 0; i < n; i++)
      {
                arr = rand() % n;
      }
      return arr;
}

int intCmp(void* vp1, void* vp2)
{
      return (*(int*)vp1) - (*(int*)vp2);
}

void assign(void* des, void* src,int elemSize)
{
      for (int i = 0; i < elemSize; i++)
      {
                *((char*)des + i) = *((char*)src + i);
      }
}

void merge(void* arr, int p, int q, int r, int elemSize, int (*cmpFunc)(void*, void*))
{
      int i = p;
      int j = q+1;
      int k = 0;
      char* temp = (char*)malloc((r-p+1)*elemSize);
      while (i <= q && j <= r) {
                if (cmpFunc((char*)arr + i * elemSize, (char*)arr + j * elemSize) < 0) {
                        assign((char*)temp + k * elemSize, (char*)arr + i * elemSize, elemSize);
                        i++;
                }
                else
                {
                        assign((char*)temp + k * elemSize, (char*)arr + j * elemSize, elemSize);
                        j++;
                }
                k++;
      }
      if (i <= q) {
                assign((char*)temp + k * elemSize, (char*)arr + i * elemSize, (q - i + 1) * elemSize);
      }
      if (j <= r) {
                assign((char*)temp + k * elemSize, (char*)arr + i * elemSize, (r - j + 1) * elemSize);
      }
      assign(arr, temp, (r - p + 1) * elemSize);
      free(temp);
}

void mergeSort(void* arr, int p, int r,int elemSize,int (*cmpFunc)(void*,void*))
{
                int q = 0;
      if (p < r) {
                q = (r+p) / 2;
                mergeSort(arr, p, q,elemSize,cmpFunc);
                mergeSort(arr, q + 1, r, elemSize, cmpFunc);
                merge(arr, p, q, r, elemSize,cmpFunc);
      }
}

小菜鸟一枚 发表于 2020-2-21 10:21

学了这么久，我都不会算法，羡慕楼主都会使用time.h了，好想学会malloc和库函数怎么用，
我VS2010编译楼主的程序并没有报错啊？排序是对的呀？


楼主想问的是什么呀？

54sdd 发表于 2020-2-21 10:23

把数据结构与算法分析的 c 语言实现版本拿来, 反复键入代码, 做一些测试数据进行调试, 就弄明白了
就是递归到底, 然后一层一层出栈,从左向右的.

mergeSort是分, merge是治, 合起来就是分治思想

little_boy 发表于 2020-2-21 10:36

本帖最后由 little_boy 于 2020-2-21 10:46 编辑

54sdd 发表于 2020-2-21 10:23
把数据结构与算法分析的 c 语言实现版本拿来, 反复键入代码, 做一些测试数据进行调试, 就弄明白了
就是递 ...
为什么我把算法写成具体的int型数组的排序是可行的？
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void merge(int arr[], int low, int mid, int high);
void merge_sort(int arr[], int first, int last);
int* initialize(int* arr, int n);

int main()
{
        int n;
        printf("Please input a number:");
        scanf("%d", &n);
        int* arr = (int*)malloc(n * sizeof(int));
        clock_t start = clock();
        initialize(arr, n);
        clock_t end = clock();
        printf("inintalize %d numbers costs %lfs\n",n, (double)(end - start)/CLOCKS_PER_SEC);
        printf("排序前:\n");
        for (int i = 0; i < n; i++)
        {
                printf("%-5d ", arr);
                (i + 1) % 10 == 0 ? printf("\n") :printf("") ;
        }
        start = clock();
        merge_sort(arr, 0, n - 1);
        end = clock();
        printf("\ninsertionSort %d numbers costs %lfs\n",n, (double)(end - start) / CLOCKS_PER_SEC);
        printf("排序后:\n");
        for (int i = 0; i < n; i++)
        {
                printf("%-5d ", arr);
                (i + 1) % 10 == 0 ? printf("\n") : printf("");
        }
        free(arr);
        return 0;
}

void merge(int arr[], int low, int mid, int high)
{
        int i, k;
        int* tmp = (int*)malloc((high - low + 1) * sizeof(int));
        int left_low = low;
        int left_high = mid;
        int right_low = mid + 1;
        int right_high = high;
        k = 0;

        while (left_low <= left_high && right_low <= right_high)
        {
                if (arr < arr)
                        tmp = arr;
                else {
                        tmp = arr;
                }
        }
        while (left_low <= left_high) {
                tmp = arr;
        }
        while (right_low <= right_high) {
                tmp = arr;
        }

        for (i = 0; i < high - low + 1; i++)
                arr = tmp;
        free(tmp);
}

void merge_sort(int arr[], int first, int last) {
        int mid = 0;
        if (first < last)
        {
                mid = (first + last) / 2;
                merge_sort(arr, first, mid);
                merge_sort(arr, mid + 1, last);
                merge(arr, first, mid, last);
        }
}

int* initialize(int* arr,int n)
{
        for (int i = 0; i < n; i++)
        {
                arr = rand() % n;
        }
        return arr;
}

little_boy 发表于 2020-2-21 10:37

小菜鸟一枚 发表于 2020-2-21 10:21
学了这么久，我都不会算法，羡慕楼主都会使用time.h了，好想学会malloc和库函数怎么用，
我VS2010编译楼主 ...

编译运行可以但是完成不了排序的功能

我的爱是你 发表于 2020-2-21 11:48

本帖最后由 我的爱是你 于 2020-2-21 12:29 编辑

作为一个小白，一步一步看你代码到栈操作，我就知道后面排序不用看了。{:301_1005:}
这是你原来的运算结过，明显错误。

这是我改后的：


下面代码，自己好好想想自己写的栈怎么做的。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int intCmp(void* vp1, void* vp2);
int* initialize(int* arr, int n);
void assign(void*, void*, int);
void merge(void* arr, int p, int q, int r, int elemSize, int (*cmpFunc)(void*, void*));
void mergeSort(void* arr, int p, int r, int elemSize, int (*cmpFunc)(void*, void*));

int main()
{
      int n;
      printf("Please input a number:");
      scanf_s("%d", &n);
      int* arr = (int*)malloc(n * sizeof(int));//分配一个数组
      clock_t start = clock();   //返回运行时间毫秒
      initialize(arr, n);      
      clock_t end = clock();   //赋值后再次计算运行时间
      printf("inintalize %d numbers costs %lfs\n", n, (double)(end - start) / CLOCKS_PER_SEC);    //输出列输出秒
      printf("排序前:\n");
      for (int i = 0; i < n; i++)       //输出数组
      {
                printf("%-5d ", arr);
                (i + 1) % 10 == 0 ? printf("\n") : printf("");   //输出10位换行
      }
      start = clock();   //毫秒
      mergeSort(arr, 0, n - 1, sizeof(int), intCmp);   //数组,0,列,4,,0
      end = clock();
      printf("\ninsertionSort %d numbers costs %lfs\n", n, (double)(end - start) / CLOCKS_PER_SEC);
      printf("排序后:\n");
      for (int i = 0; i < n; i++)
      {
                printf("%-5d ", arr);
                (i + 1) % 10 == 0 ? printf("\n") : printf("");
      }
      free(arr);
      return 0;
}

int* initialize(int* arr, int n)
{
      for (int i = 0; i < n; i++)
      {
                arr = rand() % n;   //对数组进行赋值
      }
      return arr;   
}

int intCmp(void* vp1, void* vp2)//返回 vp1 - vp2的值
{
      return (*(int*)vp1) - (*(int*)vp2);
}

void assign(void* des, void* src, int elemSize)
{
      for (int i = 0; i < elemSize; i++)
      {
                *((char*)des + i) = *((char*)src + i);
      }
}

void merge(void* arr, int p, int q, int r, int elemSize, int (*cmpFunc)(void*, void*))
{
      int i = p;
      int j = q + 1;
      int k = 0;
      char* temp = (char*)malloc((r - p + 1) * elemSize);
      while (i <= q && j <= r) {
                if (cmpFunc((char*)arr + i * elemSize, (char*)arr + j * elemSize) < 0) {
                        assign((char*)temp + k * elemSize, (char*)arr + i * elemSize, elemSize);
                        i++;
                }
                else
                {
                        assign((char*)temp + k * elemSize, (char*)arr + j * elemSize, elemSize);
                        j++;
                }
                k++;
      }
      if (i <= q) {
                assign((char*)temp + k * elemSize, (char*)arr + i * elemSize, (q - i + 1) * elemSize);
      }
      if (j <= r) {
                assign((char*)temp + k * elemSize, (char*)arr + i * elemSize, (r - j + 1) * elemSize);
      }
      assign(arr, temp, (r - p + 1) * elemSize);
      free(temp);
}

void mergeSort(void* arr, int p, int r, int elemSize, int (*cmpFunc)(void*, void*))
{
      int q = 0;
      if (p < r) {
                q = (r + p) / 2;   //二分
                mergeSort(arr, p, q, elemSize, cmpFunc);//栈操作，后两位无意义
                //mergeSort(arr, q + 1, r, elemSize, cmpFunc);   //？
                merge(arr, p, q, r, elemSize, cmpFunc);
      }
}

tony666 发表于 2020-2-21 12:09

本帖最后由 tony666 于 2020-2-21 12:10 编辑

楼主很厉害哈，没啥大问题，学习了
1.建议使用随机数前先设种子
int* initialize(int* arr,int n)
{
      srand(time(NULL));
      for (int i = 0; i < n; i++)
      {
                arr = rand() % n;
      }
      return arr;

2. 应该是手滑了 j写成了i
      if (j <= r) {
                assign((char*)temp + k * elemSize, (char*)arr + j * elemSize, (r - j + 1) * elemSize);
      }

3.temp复制到arr时地址不对，
      assign((void*)((int*)arr+p), temp, (r - p + 1) * elemSize);
      free(temp);

little_boy 发表于 2020-2-21 12:52

我的爱是你 发表于 2020-2-21 11:48
作为一个小白，一步一步看你代码到栈操作，我就知道后面排序不用看了。
这是你原来的运算结过 ...

虽然不是这里的问题，不过还是非常感谢你的热心回答。

little_boy 发表于 2020-2-21 12:55

本帖最后由 little_boy 于 2020-2-21 12:57 编辑



谢谢，多谢帮助，现在解决了。
纠正后的代码
assign((char*)arr+p*elemSize, temp, (r - p + 1) * elemSize);

little_boy 发表于 2020-2-21 13:11

本帖最后由 little_boy 于 2020-2-21 13:18 编辑

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int intCmp(void* vp1, void* vp2);
int* initialize(int* arr, int n);
void assign(void*, void*, int);
void merge(void* arr, int p, int q, int r, int elemSize, int (*cmpFunc)(void*, void*));
void mergeSort(void* arr, int p, int r, int elemSize, int (*cmpFunc)(void*, void*));

int main()
{
      int n;
      printf("Please input a number:");
      scanf_s("%d", &n);
      int* arr = (int*)malloc(n * sizeof(int));//分配一个数组
      clock_t start = clock();   //返回运行时间毫秒
      initialize(arr, n);      
      clock_t end = clock();   //赋值后再次计算运行时间
      printf("inintalize %d numbers costs %lfs\n", n, (double)(end - start) / CLOCKS_PER_SEC);    //输出列输出秒
      printf("排序前:\n");
      for (int i = 0; i < n; i++)       //输出数组
      {
                printf("%-5d ", arr);
                (i + 1) % 10 == 0 ? printf("\n") : printf("");   //输出10位换行
      }
      start = clock();   //毫秒
      mergeSort(arr, 0, n - 1, sizeof(int), intCmp);   //数组,0,列,4,,0
      end = clock();
      printf("\ninsertionSort %d numbers costs %lfs\n", n, (double)(end - start) / CLOCKS_PER_SEC);
      printf("排序后:\n");
      for (int i = 0; i < n; i++)
      {
                printf("%-5d ", arr);
                (i + 1) % 10 == 0 ? printf("\n") : printf("");
      }
      free(arr);
      return 0;
}

int* initialize(int* arr, int n)
{
      for (int i = 0; i < n; i++)
      {
                arr = rand() % n;   //对数组进行赋值
      }
      return arr;   
}

int intCmp(void* vp1, void* vp2)//返回 vp1 - vp2的值
{
      return (*(int*)vp1) - (*(int*)vp2);
}

void assign(void* des, void* src, int elemSize)
{
      for (int i = 0; i < elemSize; i++)
      {
                *((char*)des + i) = *((char*)src + i);
      }
}

void merge(void* arr, int p, int q, int r, int elemSize, int (*cmpFunc)(void*, void*))
{
      int i = p;
      int j = q+1;
      int k = 0;
      char* temp = (char*)malloc((r-p+1)*elemSize);
      while (i <= q && j <= r) {
                if (cmpFunc((char*)arr + i * elemSize, (char*)arr + j * elemSize) < 0) {
                        assign((char*)temp + k * elemSize, (char*)arr + i * elemSize, elemSize);
                        i++;
                }
                else
                {
                        assign((char*)temp + k * elemSize, (char*)arr + j * elemSize, elemSize);
                        j++;
                }
                k++;
      }
      if (i <= q) {
                assign((char*)temp + k * elemSize, (char*)arr + i * elemSize, (q - i + 1) * elemSize);
      }
      if (j <= r) {
                assign((char*)temp + k * elemSize, (char*)arr + j * elemSize, (r - j + 1) * elemSize);
      }
      assign((char*)arr+p*elemSize, temp, (r - p + 1) * elemSize);
      free(temp);
}

void mergeSort(void* arr, int p, int r,int elemSize,int (*cmpFunc)(void*,void*))
{
                int q = 0;
      if (p < r) {
                q = (r+p) / 2;
                mergeSort(arr, p, q,elemSize,cmpFunc);
                mergeSort(arr, q + 1, r, elemSize, cmpFunc);
                merge(arr, p, q, r, elemSize,cmpFunc);
      }
}

运行结果:
页: [1]
查看完整版本: C语言归并排序算法求助


免责声明：
吾爱破解所发布的一切破解补丁、注册机和注册信息及软件的解密分析文章仅限用于学习和研究目的；不得将上述内容用于商业或者非法用途，否则，一切后果请用户自负。本站信息来自网络，版权争议与本站无关。您必须在下载后的24个小时之内，从您的电脑中彻底删除上述内容。如果您喜欢该程序，请支持正版软件，购买注册，得到更好的正版服务。如有侵权请邮件与我们联系处理。

Mail To:Service@52pojie.cn