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) ，如果您想在 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 的循环! )。如果这种极端情况在任何进一步的场景中都可能是现实的，那么您必须明确地处理它。