c++ - 排序数组优先级队列

Question

我正在实现一个排序数组优先级队列并在插入时进行排序。由于某种原因，队列没有完全排序。到目前为止，我是否正确地实现了它？我该如何从这里修复它？

void insertInt(int numToIns)
{
    if (total == 0)
    {
        q[0] = numToIns;
        minimum = numToIns;
    }
    else if (total != 0)
    {
        if (numToIns <= minimum)
        {
            minimum = numToIns;
            for (int move = total; move >= 0; --move)
            {
                q[move + 1] = q[move];
            }
            q[0] = numToIns;
        }
        else if (numToIns < q[total])
        {
            bool numFound = false;
            for (int j = 0; numFound != true; ++j)
            {
                if (numToIns <= q[j])
                {
                    numFound = true;
                    for (int move = total; move >= j; --move)
                    {
                        q[move + 1] = q[move];
                    }
                    q[j] = numToIns;
                }
            }

        }
        else if (numToIns >= q[total - 1])
        {
            q[total] = numToIns;
        }
    }
    ++total;
}

Answer 1

不确定您当前的代码是什么样的，但应该这样做:

#include <ctime>
#include <cstdlib>
#include <cstdio>
#include <iostream>

std::size_t total;
int q[100];
int minimum;

void print()
{
    for (std::size_t i{}; i < total; ++i)
        std::cout << q[i] << ' ';
    std::cout.put('\n');
}

void insertInt(int numToIns)
{
    if (total == 0)
    {
        q[0] = numToIns;
        minimum = numToIns;
    }
    else if (total != 0)
    {
        if (numToIns <= minimum)
        {
            minimum = numToIns;
            for (std::size_t move{ total }; move >= 0; --move)
            {
                q[move + 1] = q[move];
            }
            q[0] = numToIns;
        }
        else if (numToIns < q[total - 1])
        {
            bool numFound = false;
            for (std::size_t j{}; !numFound; ++j)
            {
                if (numToIns <= q[j])
                {
                    numFound = true;
                    for (std::size_t move{ total - 1 }; move >= j; --move)
                    {
                        q[move + 1] = q[move];
                    }
                    q[j] = numToIns;
                }
            }

        }
        else if (numToIns >= q[total - 1])
        {
            q[total] = numToIns;
        }
    }
    ++total;
}

int main()
{
    std::srand(static_cast<unsigned>(std::time(nullptr)));

    for (int i{}; i < 20; ++i) {
        insertInt(std::rand() % 20 + 1);
        print();
    }
}

请注意，由于我编写了该代码，三只小猫死了:(

无bs版本:

void insertInt(int num)
{
    std::size_t pos{};
    while (pos < total && num > q[pos])
        ++pos;

    for (std::size_t k{ total }; k > pos; --k)
        q[k] = q[k - 1];

    q[pos] = num;
    ++total;
}

如果要插入的数字大于最后一个元素，为了避免遍历数组，可以添加一个特殊情况:

void insertInt(int num)
{
    if (num > q[total - 1]) {
        q[total++] = num;
        return;
    }

    std::size_t pos{};
    while (pos < total && num > q[pos])
        ++pos;

    for (std::size_t k{ total }; k > pos; --k)
        q[k] = q[k - 1];

    q[pos] = num;
    ++total;
}