如何按除数数对数组元素进行排序？

Question

我的问题是我在做练习的时候碰到了障碍。问题的根源是，我必须编写一个程序，根据每个元素的除数的数量对数组进行降序排序，但当两个元素具有相同数量的除数时，它应该对这些值进行升序排序。到目前为止我的代码如下：

#include <iostream>
#include <fstream>

using namespace std;

int cntDiv(int n)   //get number of divisors
{
    int lim = n;
    int c = 0;
    if(n == 1)
        return 1;
    for(int i = 1; i < lim; i++)
    {
        if(n % i == 0)
        {
            lim = n / i;
            if(lim != i)
                c++;
            c++;
        }
    }
    return c;
}

int main()
{
    ifstream fin("in.txt");
    int n, i, j;
    fin >> n;
    int v[n];
    for(i = 0; i < n; i++)
        fin >> v[i];

    int div[n];
    for(i = 0; i < n; i++)
        div[i] = cntDiv(v[i]);

    for(i = 0; i < n - 1; i++)
    {
        for(j = i + 1; j < n; j++)
        {
            if(div[i] < div[j] && div[i] != div[j]) //if the number of divisors are different
            {
                int t = v[i];
                v[i] = v[j];
                v[j] = t;

                t = div[i];
                div[i] = div[j];
                div[j] = t;
            }
            if(div[i] == div[j] && v[i] > v[j]) //if the number of divisors are the same
            {
                int t = v[i];
                v[i] = v[j];
                v[j] = t;
            }
        }
    }

    for(i = 0; i < n; i++)
    {
        cout << v[i] << " ";
    }
    return 0;
}

In.txt：

5
12 20 4 100 13

输出：

100 12 20 4 13

虽然它与这个和许多其他的都能很好地工作。对于更大的输入，它会超过时间限制，即0.1s。有什么建议吗?我应该如何重写排序？(我写了冒泡排序，因为我不能通过快速排序实现按属性排序数组)

Answer 1

使用结构数组。该结构将包含原始值和一个除数容器：

struct Number_Attributes
{
  int number;
  std::list<int> divisors;
};

然后，您可以编写自定义比较器函数并将其传递给std::sort：

bool Order_By_Divisors(const Number_Attributes& a,
                       const Number_Attributes& b)
{
  return a.divisors.size() < b.divisors.size();
}

然后，排序变成：

#define ARRAY_CAPACITY (20U)
Number_Attributes the_array[ARRAY_CAPACITY];
//...
std::sort(&array[0], &array[ARRAY_CAPACITY], Order_By_Divisors);

除数的生成留作运算的练习。

Answer 2

使用std::sort重新编写代码

std::vector<std::pair<int, int>> customSort(const std::vector<int>& v)
{
    std::vector<std::pair<int, int>> ps;
    ps.reserve(v.size());

    // We don't have zip sort :/
    // So building the pair
    for (auto e : v)
    {
        ps.emplace_back(e, cntDiv(e)); 
    }
    std::sort(ps.begin(), ps.end(), [](const auto&lhs, const auto& rhs) {
        // descending number of divisors, increasing value
        return std::make_tuple(-lhs.second, lhs.first)
             < std::make_tuple(-rhs.second, rhs.first);
    });
    return ps;
}

int main()
{
    const std::vector<int> v = {12, 20, 4, 100, 13};
    const auto res = customSort(v);

    for(const auto& p : res)
    {
        std::cout << p.first << " ";
    }
}

Demo