如何根据除数的数量对数组元素进行排序？

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

#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。任何建议如何重写排序？（我写了气泡排序，因为我无法通过属性通过快速排序实现排序数组）

来源

2016-06-10 Paralyz3d

这是没有咨询网站。并且没有语言C/C++。你的代码是C++，而不是C！重新表现：你已经自己回答了你的问题。 – Olaf

*“我无法通过快速排序按属性排序数组”* - 我不明白这是什么意思。你为什么不能实施快速排序？ –

其实我什么都听不懂。英语不是他的第一语言 –

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

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);

作为OP的练习留下了除数的生成。

来源

2016-06-10 17:57:55

比较器稍微复杂一些：它应该处理相同大小的“除数”。 – Jarod42

返工你的代码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

来源

2016-06-10 17:58:18 Jarod42

如何根据除数的数量对数组元素进行排序？

回答

相关问题