如何根據除數的數量對數組元素進行排序？

我的問題是我在解決一些練習時遇到障礙。問題的根源在於我必須編寫一個程序，按每個元素除數的數量對數組進行降序排序，但是當兩個元素具有相同數量的除數時，應按升序排序這些值。到目前爲止我的代碼：如何根據除數的數量對數組元素進行排序？

#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

如何根據除數的數量對數組元素進行排序？

回答

相關問題