排序一個數組到另一個 - C

Question

所以我試圖寫這個函數的輸入參數數組將被採取和複製到另一個數組，但以排序的方式。例如：輸入參數3, 1, 9, 8將複製到目標數組1, 3, 8, 9中。

這是我迄今爲止的，但它只複製每次最小的元素。我正在尋找一種方法來將每次通過時發現的最小值「列入黑名單」。

void sort_another_array(int *param, int *target, int size){ 
    int i, j, lowest = param[0]; 
    for(i = 0; i < size; i++){ 
     for(j = 0; j < size; j++){ 
      if(param[j] < lowest){ 
       lowest = param[j] 
      } 
     } 
     target[i] = lowest; 
    } 
} 

當然我也已經發現了最低值的另一個數組但是這更多不必要的循環和檢查，並增加了本已可怕的N^2的複雜性。有沒有更簡單的方法來做到這一點？

我完全新的C，所以請不要將其限制爲邏輯語句的簡單編程概念，使用一些標誌變量等。

Answer 1

的大概米最直接的方法是先複製整個數組，然後使用standard sorting algorithm就地對新數組進行排序。

但是，如果你想保持目前的結構，下面是當所有元素是唯一的選擇：

void sort_another_array(int *param, int *target, int size) { 
    int i, j, past_min = INT_MAX, current_min = INT_MAX; 
    for (i = 0; i < size; ++i) { 
     for (j = 0; j < size; ++j) { 
      if (i == 0 || param[j] > past_min) { 
       if (past_min == current_min || param[j] < current_min) { 
        current_min = param[j]; 
       } 
      } 
     } 
     target[i] = current_min; 
     past_min = current_min; 
    } 
} 

這裏做的事情是保持先前最低元素的跟蹤發現（past_min）。要查找的下一個元素在大於past_min的所有元素中最低。即，我們希望param[j] > past_min和param[j] < current_min都是正確的。但是，要添加到target的第一個元素（即i == 0）在其之前不會有較低的元素，因此我們會爲此添加一個例外。類似的，第一個在pass中滿足param[j] > past_min的元素將不會有任何要比較的元素，所以我們使用past_min == current_min添加另一個異常（這僅適用於在pass中找到的第一個元素）。

如果數組中的重複，這可能工作：

void sort_another_array(int *param, int *target, int size) { 
    int j, past_min, current_min, write = 0, round_write = 0; 
    while (round_write != size) { 
     for (j = 0; j < size; ++j) { 
      if (round_write == 0 || param[j] > past_min) { 
       if (write == round_write || param[j] < current_min) { 
        current_min = param[j]; 
        write = round_write; 
        target[write] = current_min; 
        ++write; 
       } else if (param[j] == current_min) { 
        target[write] = current_min; 
        ++write; 
       } 
      } 
     } 
     round_write = write; 
     past_min = current_min; 
    } 
} 

基本上是同樣的想法，但在相同的通寫的最小值的所有元素。

Answer 2

您可以使用修改後的插入排序算法來解決這個問題：

#include <stdio.h> 

void sort_another_array(int *param, int *target, int size) 
{ 
    for (int i = 0; i < size; i ++)   // do for all elements in param 
    { 
     int j = i - 1; 
     while (j >= 0 && target[j] > param[i]) // find index of element in target which is samler or equal than param[i] 
     { 
      target[j+1] = target[j];    // shift forward element of target which is greater than param[i] 
      j --; 
     } 
     target[j+1] = param[i];     // insert param[i] into target 
    } 
} 

#define SIZE 10 

int main(void) 
{ 
    int a[SIZE] = { 9, 8, 0, 2, 1, 3, 4, 5, 7, 6 }; 
    int b[SIZE]; 

    sort_another_array(a, b, SIZE); 
    for (int i = 0; i < SIZE; i ++) 
     printf("%2d", b[i]); 

    return 0; 
} 

Answer 3

我提供的解決方案，有一個限制，即：如果在數組中沒有重複，那麼這將工作：

void sort_another_array(int *param, int *target, int size) 
{ 
int i, j, lowest; 

for(i = 0; i < size; i++) 
{ 
    int k = 0; 
    if(i > 0) // for all except first iteration 
    { 
    while(param[k] <= target[i-1]) // find the one greater than the last one added 
     k++; 
    } 
    lowest = param[k]; 

    for(j = 1; j < size; j++) 
    { 
     if((i==0 && param[j] < lowest) || (i > 0 && param[j] < lowest && param[j] > target[i-1])) // for all except first iteration the min found should be greater than the last one found 
     { 
      lowest = param[j]; 
     } 
    } 
    target[i] = lowest; 
} 
}