indexx()Numerical Recipes(C)索引排序算法奇怪地忽略了前两个元素

Question

我试图在C中使用Numerical Recipes(NR)中的indexx()算法，发现了一个非常奇怪的错误。

(NR可在此处公开获取：http://www2.units.it/ipl/students_area/imm2/files/Numerical_Recipes.pdf第338页，第8.4节)

函数应该输出一个索引数组，该数组对应于从低到高排序的浮点输入数组的元素。

下面是一个最小的工作示例，显示该算法似乎忽略了前两个元素。输出数组的前两个元素始终为0，后跟数组的长度(本例中为9)。其余元素似乎已正确排序。

哦，我试着在NR论坛上询问，但我已经等了很长时间才激活我的帐户。。。非常感谢！

[编辑的数组名称]

#include "nr_c/nr.h"
#include <stdio.h>
#include <stdlib.h>

int main()
{
float unsorted[9] = {4., 5., 2., 6., 3., 8., 1., 9., 7.};
long unsigned int sort[9];
printf("Unsorted input array:n");
for (int i=0; i<9; i++) {
printf("%.1f  ", unsorted[i]);
}
printf("nn");
indexx(9, unsorted, sort);
printf("Indexx output array:n");
for (int i=0; i<9; i++) {
printf("%d    ", sort[i]);
}
printf("nn");
printf("Should-be-sorted array:n");
for (int i=0; i<9; i++) {
printf("%.1f  ", unsorted[sort[i]]);
}
printf("nn");
return 0;
}

输出：

Unsorted input array:
4.0  5.0  2.0  6.0  3.0  8.0  1.0  9.0  7.0  
Indexx output array:
0    9    6    2    4    1    3    8    5    
Should-be-sorted array:
4.0  0.0  1.0  2.0  3.0  5.0  6.0  7.0  8.0 

Answer 1

数字配方C代码使用基于1的索引。(由于其FORTRAN的起源，第一个版本是用FORTRAN编写的，FORTRAN对数组和矩阵使用基于1的索引。C版本可能是基于f2c的输出…)在问题中的原始代码中，indexx()函数忽略了unsorted[]和sort[]数组的第一个元素。加：它访问数组最后一个元素之外的一个元素(导致UB)因此，索引数组中同时存在0和9。(初始0实际上是未初始化的内存，但indexx()功能尚未触及)

---

如果我的假设是正确的，以下应该有效：

---

#include "nr_c/nr.h"
#include <stdio.h>
#include <stdlib.h>

int main()
{
float unsorted[9] = {4., 5., 2., 6., 3., 8., 1., 9., 7.};
long unsigned int sort[9];
printf("Unsorted input array:n");
for (int i=0; i<9; i++) {
printf("%.1f  ", unsorted[i]);
}
printf("nn");
indexx(9, unsorted-1, sort-1); // <<-- HERE
printf("Indexx output array:n");
for (int i=0; i<9; i++) {
printf("%d    ", sort[i]);
}
printf("nn");
printf("Should-be-sorted array:n");
for (int i=0; i<9; i++) {
printf("%.1f  ", unsorted[sort[i]-1]); // <<-- AND HERE
}
printf("nn");
return 0;
}

---

numerical recipes in C代码假定基于1的索引：N大小的数组具有索引1..N。这样做是为了不混淆数学家。(因此，整整一代程序员都感到困惑)分配函数是malloc()的包装器，它通过返回指向分配空间的第-1个成员的指针来作弊。对于float矢量，这可能类似于：

---

#include <stdlib.h>
float * float_vector(unsigned size)
{
float * array;
array = calloc( size, sizeof *array);
if (!array) return NULL;
return array -1;
}