1

我不明白分而治之算法是如何在 C 中实现的。我的意思是我理解算法，但不明白用 C 编写时它为什么以及如何工作。

在以下示例中，执行的指令是什么以及决定它们执行顺序的因素是什么？

换句话说，为什么“merge_sort 初始化”、“merge_sort first”、“merge_sort second”和“merging”会以它们的方式出现？

#include<stdio.h>

int arr[8]={1, 2, 3, 4, 5, 6, 7, 8};

int main()
{
    int i;
    merge_sort(arr, 0, 7);

    printf("Sorted array:");

    for(i = 0; i < 8; i++)
        printf("%d", arr[i]);

    return 0;
}

int merge_sort(int arr[],int low,int high)
{
    printf("\nmerge_sort initialization\n");

    int mid;

    if(low < high) 
    {
        mid = (low + high) / 2;

        // Divide and Conquer
        merge_sort(arr, low, mid); 
        printf("\n merge_sort first\n");

        merge_sort(arr, mid + 1, high); 
        printf("\n merge_sort second\n");

        // Combine
        merge(arr, low, mid, high); 
        printf("\nmerging\n");
    }

    return 0;
}

int merge(int arr[], int l, int m, int h)
{
    int arr1[10], arr2[10];
    int n1, n2, i, j, k;
    n1 = m - l + 1;
    n2 = h - m;

    for(i = 0; i < n1; i++)
        arr1[i] = arr[l + i];

    for(j = 0; j < n2; j++)
        arr2[j] = arr[m + j + 1];

    arr1[i] = 9999;
    arr2[j] = 9999;

    i = 0;
    j = 0;

    for(k = l; k <= h; k++)
    {
        if(arr1[i] <= arr2[j])
            arr[k] = arr1[i++];
        else
            arr[k] = arr2[j++];
    }

    return 0;
}

提前感谢您的回答。

4

1 回答 1

2

我不确定你为什么要求人们让你理解算法。我只能帮助你，但你必须经历它。

简而言之，您必须将阵列分成两部分。假设你有 10 个元素high=0，然后low=10-1=1。mid = (9+0)/2 = 4. 因此，您已将主数组分为 2 个部分，从第 1 个元素到第 5 个元素，从第 6 个元素到第 10 个元素 (1..10)。当您在一块中有多个元素时，您会再次将其切成两半。最后合并它们，即再次添加数组，但以升序排列。最后你得到一个排序的数组。很难解释每一件。我认为来自wiki的这个链接可以提供帮助。http://en.wikipedia.org/wiki/Merge_sort

现在是函数调用。main 函数正在调用merge_sort它将传递低和高（数组的全部范围），但在此函数内，merge_sort将在前半范围内由自己调用两次（从中间开始，中间到最后一个元素）。每个调用将再次执行相同的操作（划分数组并调用前半部分并发送一半）。这个过程将继续下去。merge函数将以排序方式添加数组。这就是你所需要的。如果不清楚打印或调试参数的值。

于 2013-07-04T07:57:30.727 回答