C语言 在气泡排序中显示 2 个相同的值

Question

我正在对值进行排序以找到前 3 个值。但是，如果有 2 个相同的最大值，我的气泡排序只能显示一个值。例如： 输出：

Please select broadband type (1 - DSL): 1
3800 , month 1
1700 , month 3
1400 , month 4

预期输出：

Please select broadband type (1 - DSL): 1
3800 , month 1
3800 , month 2
1400 , month 4

数组文件：

int file[3][6] =
{
{ 3800, 3800, 1700, 1400, 1300, 1285 },
{ 106900, 100400, 89600, 76900, 61500, 59200 },
{ 1260300, 1269900, 1285400, 1298800, 1316900, 1401280 }
};

功能：

{
int type3, c, d, highest = 0, prehighest = 99999999999, month = 0;
printf("1. DSL n");
printf("2. Cable Modem n");
printf("3. Fibre Based n");
printf("Please select broadband type (1 - DSL): ");
scanf(" %d", &type3);
if (type3 <= 3)
{
for (d = 0; d < 3; d++)
{
for (c = 0; c < 6; c++)
{
if (file[type3 - 1][c] > highest && file[type3 - 1][c] < prehighest)
{
highest = file[type3 - 1][c];
month = c + 1;
}
}
if (file[type3 -1][3])
printf(" %d , month %d n", highest, month);
prehighest = highest;
highest = 0;
}
}
else
{
printf("Error! Please enter a valid option. n");
}
type3 =getchar();
}

Answer 1

好的，你想找到 3 个最高值...

首先，由于您允许负值，因此也应该检查下限(实际上，您甚至还需要检查 0 表示无符号(，所以首先：

if (1 <= type3 && type3 <= 3)

然后，为了不必在循环中每次减去，我会在之前做一次：

{
--type3;

实际上，您不会进行任何气泡排序，因为您不会修改输入数组。你必须冒泡：

if(file[type3 - 1][c] > file[type3 - 1][c - 1]
{
// swap positions c and c - 1!!!
}

对于上面，你必须从 1 开始计数，当然......

然后排序后，您会在最后找到要查找的元素。

不过，您的代码会寻找尚未找到的最高元素(照原样，复杂性与气泡排序相同：O(k*n)，如果您想从n元素中找到k最大的元素 – 有一些方法可以做得更好，但对于这么小的输入集来说，这些将是矫枉过正......

但是，您的算法无法处理重复项;当您在找到第一个重复项后修改prehighest以higest时，条件

file[type3 - 1][c] < prehighest

对于任何一个进一步的重复项，都不能再为真了。

您可以通过计算重复项的数量来调整算法：

if (file[type3 - 1][c] > highest && file[type3 - 1][c] < prehighest)
{
/* ... */
count = 1;
}
else
{
count += file[type3 - 1][c] == highest;
}

现在，您可以输出count倍于找到的值。

因此，您将修改循环，例如：

for(d = 0; d < 3; d += count)

但是，您可能会发现比所需值更多的值，因此您可以执行以下操作：

int min = MIN(count, required);
required -= min;
for(int i = 0; i < min; ++i) { /* print */ };

在最外层循环中，您可以检查required是否为 ！= 0：

for(int required = 3; required; )
{
for (c = 0; c < 6; c++)
{
}
// print and adjust required
}

但是，在上面的循环中，有一个极端情况是开放的：如果你寻找数组中包含的更多元素，你最终会陷入一个无限循环(也适用于带有d += count的循环！如果该极端情况在任何进一步的情况下可能是现实的，则必须明确处理它。