在冒泡排序中显示2个相同的值

Question

我正在对值进行排序，以找到前3个值。然而，如果有两个相同的最高值，我的冒泡排序只能显示一个值。例如:输出：

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)，如果您想要从k个元素中找到n个最大的元素--有一些方法可以做得更好，但对于这么小的输入集来说，这些方法就有点过分了……)。

但是，您的算法无法处理重复项；当您在找到第一个重复项后将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的循环)。如果这种情况在任何进一步的场景中都是现实的，那么您必须显式地处理它。