劃分並征服範例和遞歸在C - 合併排序示例

Question

我不明白如何在C中實現分治算法。 我的意思是我理解算法，但不明白爲什麼以及如何工作當寫入C.

在下面的示例中執行的指令是什麼以及它們的執行順序是什麼？換句話說，爲什麼「merge_sort initialization」，「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; 
} 

在此先感謝您的答案。

Answer 1

我不確定你爲什麼要求人們讓你理解算法。我可以幫助你，但你必須經過它。

在合併短，你必須切成兩塊數組。假設你有10個元素，然後high=0和low=10-1=1。 mid = (9+0)/2 = 4。所以，你已經把主陣列分成了從第1個元素到第5個，從第6個元素到第10個（1..10）的2個部分。當你有一個以上的元素時，你再將它切成兩個。最後將它們合併，即按照升序重新添加數組。最後你得到一個單一的數組排序。它很難解釋每一件。我認爲這個來自wiki的鏈接可以提供幫助。 http://en.wikipedia.org/wiki/Merge_sort

現在來了函數調用。主要功能是調用merge_sort它會通過低和高（陣列的全部範圍），但在此功能中，merge_sort將自行調用兩次，前半部分範圍（從中途到中途到中途到最後一個元素）。每次通話都會再次執行相同的操作（將數組與前半部分通話併發送一半）。這個過程將繼續。 merge函數將以排序的方式添加數組。這就是你需要的。如果你不清楚打印或調試參數的值。