排序一个数组到另一个 - 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; 
} 
}