为了让事情变得简单，这里有一个我想做的示例：
假设我们有两个数组，A和B；
A=[5,5,5,9,1]
B=[9,5,1,4,4]
在程序中，有数百个这样的小数组。我正试图根据它们的最大值对它们进行排序。所以在这种情况下，它们都有9，所以转到下一个最大的数字。好吧，他们都有5，下一个数字。A数组有一个5，B数组有一一个4，所以A数组将首先排序。这里的问题是，我不知道如何在不对这些值进行排序的情况下对这些家伙进行排序。
我得到的是：
int compare(const void *x, const void *y)
{
struct Data *s1, *s2;
s1 = (struct Data *)x;
s2 = (struct Data *)y;
int maxv=-1000;
int maxv2=-1000;
int maxvn=1000;
int maxv2n=1000;
int j=0;
int k=0;
for (k=0; k < 5;k++)
{
max = -1000;
max2= -1000;
for (j=0; j<5;j++)
{
if (s1->margin[j]>max && s1->margin[j]<maxvn)
maxv=s1->margin[j];
if (s2->margin[j]>max2 && s2->margin[j]<maxv2n)
maxv2=s2->margin[j];
}
if (max2<max)
return 1;
if (max<max2)
return -1;
maxvn=maxv;
maxv2n=maxv2;
}
return 0;
}
所以，理论上，我希望数组A列在数组B之前。不幸的是，数组B列在数组A之前，因为（我认为）这个参数中的第二个条件：
if (s1->margin[j]>max && s1->margin[j]<maxvn)
由于第二个参数，数组A中的另外两个5被忽略。
现在，我不知道如何真正解决这个问题，除非我只是对一些数组进行malloc，然后对它们进行冒泡排序。不过这会减慢我的程序。这里有人能想到一个我可以实现的修复程序吗？它可以防止我使用任何类型的malloc，并且不会忽略重复出现的数字？
谢谢。
至少有两种可能的方法。更常见的方法是在堆栈上声明工作数组，将原始数组复制到这些工作数组中，对它们进行排序，然后进行比较。这避免了malloc()的开销和复杂性，并使您可以进行简单的元素比较。它仍然使用辅助空间。示例：
int compare(const void *x, const void *y)
{
struct Data *s1 = (struct Data *) x;
struct Data *s2 = (struct Data *) y;
int temp1[5]; /* or replace `int` with the correct type */
int temp2[5]; /* or replace `int` with the correct type */
int i;
memcpy(temp1, s1->margin, sizeof(temp1));
memcpy(temp2, s2->margin, sizeof(temp2));
/* ... sort temp1 and temp2 however you want ... */
/* compare */
for (i = 0; i < 5; i += 1) {
if (temp1[i] < temp2[i]) return -1;
if (temp1[i] > temp2[i]) return 1;
}
return 0;
}
或者，如果数组元素的边界足够小，则可以为每个元素计算一个键值并进行比较。如果数组元素都确定在0和20之间（包括），则此特定元素有效
int compare(const void *x, const void *y)
{
struct Data *s1 = (struct Data *) x;
struct Data *s2 = (struct Data *) y;
uint64_t key1 = 0;
uint64_t key2 = 0;
int i;
for (i = 0; i < 5; i += 1) {
key1 += 1 << (s1->margin[i] * 3);
key2 += 1 << (s2->margin[i] * 3);
}
if (key1 < key2) return -1;
if (key1 > key2) return 1;
return 0;
}
它将键视为3位元素的数组，并在每个元素中累积该元素的索引在相应的原始数组中出现的次数。所得到的64位值可以通过普通整数比较运算符进行比较。
如果原始数组的元素在0和9之间有界，那么32位密钥对于第二种方法就足够了。
更新以添加：
还要注意的是，如果您有大量这样的数组要排序，那么最大限度地减少比较成本将对您非常有利。计算密钥方法的优点是，您可以为每个数组只计算一次密钥，将其存储在某个位置，然后对其余的数组进行非常快速的比较。在单独的比较中，任何类型的临时数组或多循环方法都会对您的性能造成很大影响（即使每次重新计算密钥，虽然不可怕，但也不太好）。
您可以在每个数组中分配一个额外的元素，并将数组中包含的最大值存储在该元素中。然后，每当更新数组时，如果需要，执行更新的代码都可以保留最大值槽。数组的最高值总是在插槽0中（例如，如果数组总是包含5个元素，则为插槽5）。
这是经典的速度与尺寸在性能上的权衡。每个阵列增加一个元素的RAM占用空间，再加上保持最大元素更新的时间，而不是对阵列进行排序或串行扫描的复杂性。
首先，对所有小数组进行排序（使用qsort（），或者如果它们很小，您自己的冒泡或插入排序可能会更快），以使比较更容易。这将使比较函数变小。然后简化compare（）函数（现在它只需要同时通过两个数组一次），并对数组使用qsort（），将新的compare（（）函数传递给它。