c++ - 选择排序获取错误的数组索引

Question

我正在写一个选择排序，给定一个无序元素数组，将用排序元素的索引填充一个新数组。例如，

[3, 2, 1]

会回来

[2, 1, 0] // original indexes of sorted array [1, 2, 3]

不幸的是，它错误地填充了数组，重复了相同的索引。

这是我的代码:

void sort(float data[], int indx[], int len) {
  int   min;
  float temp;
  float tempData[len];

  for (int x = 0; x < len; ++x){
    tempData[x] = data[x];
  }

  for (int i = 0; i < len; ++i) {
    min = i;

    for (int j = i + 1; j < len; ++j) {
      if (tempData[j] < tempData[min]) {
        min = j;
      }
    }

    temp = tempData[i];
    tempData[i] = tempData[min];
    tempData[min] = temp;

    indx[i] = min;
  }
}

给定这个数组:

[8.5, 10.0, 9.25, 12.5, 12.75, 12.5, 16.0, 14.75, 17.0, 18.0, 21.0, 13.0, 7.25];

它返回:

[12, 12, 2, 12, 5, 12, 12, 11, 11, 12, 11, 12, 12]

我似乎无法弄清楚逻辑错误发生在哪里。有人可以帮我找到吗？

Answer 1

最初用数字 0 到 len -1 填充 indx，并使用索引访问来扫描和操作数组。您当前的代码有可能与输入不同步。而且您不需要 tempData。

所以像这样:

void sort(float data[], int indx[], int len) {
    int   min;
    float temp;

    for(int x = 0; x < len; ++x){
        indx[x] = x;
    }   

    for (int i = 0; i < len; ++i) {
        min = i;

        for (int j = i + 1; j < len; ++j) 
        {
            if (data[indx[j]] < data[indx[min]])
            {
                min = j;
            }
        }

        temp = indx[i];
        indx[i] = indx[min];
        indx[min] = temp;
    }   
}