合併和排序兩個包含雙打的排序數組C

Question

因此，我有兩個數組由雙數組成，它們是排序的。

我想最有效地將這些組合到一個數組中，並將這個數組排序。

我的第一個念頭是，也許你可以簡單地加入他們一起，然後就可以使用快速排序，但這不會是有效的。那麼也許使用合併排序？然而，我對如何在C中實現合併排序有什麼想法嗎？

我正在使用來自其中一個答案的代碼嘗試合併排序。我還沒有將它用於自己的方法，在我將它運用到工作之後會做到這一點。

double partitions[][5] = {{45.0, 5.0, 88.4, 0.4, 44.0}, {1000.0, 2.0, 3.4, 7.0, 50.0}}; 
double* res; 

int n1 = sizeof(partitions[0])/sizeof(partitions[0][0]); 
int n2 = sizeof(partitions[1])/sizeof(partitions[1][0]); 
int n3 = n1 + n2; 

res = malloc(n3 * sizeof(double)); 

// Merging starts 
int i = 0; 
int j = 0; 
int k = 0; 

while (i < n1 && j < n2) { 
    if (partitions[0][i] - partitions[1][j] < 0.000001) { 
     res[k] = partitions[0][i]; 
     i++; 
     k++; 
    } 
    else { 
     res[k] = partitions[1][j]; 
     k++; 
     j++; 
    } 
} 

/* Some elements in array 'arr1' are still remaining 
where as the array 'arr2' is exhausted */ 
while (i < n1) { 
    res[k] = partitions[0][i]; 
    i++; 
    k++; 
} 

/* Some elements in array 'arr2' are still remaining 
where as the array 'arr1' is exhausted */ 
while (j < n2) { 
    res[k] = partitions[1][j]; 
    k++; 
    j++; 
} 

int m; 
for (m = 0; m < n3; m++) 
    printf("%f \n", res[m]); 

Answer 1

由於陣列排序你只需要排序合併的合併部件，它是O（N1 + N2），其中n1是一個陣列的長度和n2是另一陣列的長度：

例如：

void merge(int n1, int n2){ //suppose global arrays arr1,arr2 and result array 

     i = 0; 
     j = 0; 
     k = 0; 

    // Merging starts 
    while (i < n1 && j < n2) { 
     if (arr1[i] <= arr2[j]) { 
      res[k] = arr1[i]; 
      i++; 
      k++; 
     } 
     else { 
      res[k] = arr2[j]; 
      k++; 
      j++; 
     } 
    } 

    /* Some elements in array 'arr1' are still remaining 
    where as the array 'arr2' is exhausted */ 

    while (i < n1) { 
     res[k] = arr1[i]; 
     i++; 
     k++; 
    } 

    /* Some elements in array 'arr2' are still remaining 
    where as the array 'arr1' is exhausted */ 

    while (j < n2) { 
     res[k] = arr2[j]; 
     k++; 
     j++; 
    } 
} 

而且我注意到，您的數組包含雙所以你需要改變的條件比較兩個數字時。例如，而不是if (arr1[i] <= arr2[j])，您需要編寫一個條件：if (arr1[i] < arr2[j])，然後是其他部分。