C语言归并排序算法求助

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

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

大佬们帮忙看下算法哪里有问题,编译环境:vs2019
问题已解决，感谢各位大佬的帮助，尤其是@tony666的回复让我找到了问题的所在，修改后的代码在10#

[C] 纯文本查看 复制代码

#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]);
                (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]);
                (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[i] = 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型数组的排序是可行的？

[C] 纯文本查看 复制代码

#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]);
		(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]);
		(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[left_low] < arr[right_low])
			tmp[k++] = arr[left_low++];
		else {
			tmp[k++] = arr[right_low++];
		}
	}
	while (left_low <= left_high) {
		tmp[k++] = arr[left_low++];
	}
	while (right_low <= right_high) {
		tmp[k++] = arr[right_low++];
	}

	for (i = 0; i < high - low + 1; i++)
		arr[low + i] = tmp[i];
	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[i] = 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 编辑

作为一个小白，一步一步看你代码到栈操作，我就知道后面排序不用看了。

这是你原来的运算结过，明显错误。

这是我改后的：

下面代码，自己好好想想自己写的栈怎么做的。

[C] 纯文本查看 复制代码

#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]);
                (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]);
                (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[i] = 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.建议使用随机数前先设种子

[C] 纯文本查看 复制代码

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

2. 应该是手滑了 j写成了i

[C] 纯文本查看 复制代码

        if (j <= r) {
                assign((char*)temp + k * elemSize, (char*)arr + j * elemSize, (r - j + 1) * elemSize);
        }

3.temp复制到arr时地址不对，

[C] 纯文本查看 复制代码

        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 编辑

谢谢，多谢帮助，现在解决了。
纠正后的代码

[C] 纯文本查看 复制代码

assign((char*)arr+p*elemSize, temp, (r - p + 1) * elemSize);

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

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

[C] 纯文本查看 复制代码

#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]);
                (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]);
                (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[i] = 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);
        }
}

运行结果:

帐号		自动登录	找回密码
密码			注册[Register]

[已解决] C语言归并排序算法求助