使用 STL 根据因素数量进行排序 · GeeksForGeeks 中文系列教程

# 使用 STL 根据因素数量进行排序 > 原文： [https://www.geeksforgeeks.org/sort-basis-number-factors-using-stl/](https://www.geeksforgeeks.org/sort-basis-number-factors-using-stl/) 给定一个正整数数组。以每个元素的因子数量降序对给定数组进行排序，即应首先显示因子数量最多的元素，而因子数量最少的元素应最后显示。具有相同数量因子的两个元素应与原始数组中的顺序相同。例子： ``` Input : {5, 11, 10, 20, 9, 16, 23} Output : 20 16 10 9 5 11 23 Number of distinct factors: For 20 = 6, 16 = 5, 10 = 4, 9 = 3 and for 5, 11, 23 = 2 (same number of factors therefore sorted in increasing order of index) Input : {104, 210, 315, 166, 441, 180} Output : 180 210 315 441 104 166 ``` 我们已经讨论了一种基于[结构的解决方案，可以根据因素数](https://www.geeksforgeeks.org/sort-elements-basis-number-factors/)进行分类。以下步骤按因子计数的降序对数字进行排序。 1. 计算每个元素的不同数量的因素。请参考。 2. 创建[对](https://www.geeksforgeeks.org/pair-in-cpp-stl/)的[向量](http://www.geeksforgeeks.org/vector-in-cpp-stl/)，该向量存储元素及其因子计数。 3. 使用任何排序算法，根据问题陈述对该数组进行排序。 ``` // Sort an array of numbers according // to number of factors. #include <bits/stdc++.h> using namespace std; // Function that helps to sort elements // in descending order bool compare(const pair<int, int> &a, const pair<int, int> &b) { return (a.first > b.first); } // Prints array elements sorted in descending // order of number of factors. void printSorted(int arr[], int n) { vector<pair<int, int>> v; for (int i = 0; i < n; i++) { // Count factors of arr[i]. int count = 0; for (int j = 1; j * j <= arr[i]; j++) { // To check Given Number is Exactly // divisible if (arr[i] % j == 0) { count++; // To check Given number is perfect // square if (arr[i] / j != j) count++; } } // Insert factor count and array element v.push_back(make_pair(count, arr[i])); } // Sort the vector sort(v.begin(), v.end(), compare); // Print the vector for (int i = 0; i < v.size(); i++) cout << v[i].second << " "; } // Driver's Function int main() { int arr[] = {5, 11, 10, 20, 9, 16, 23}; int n = sizeof(arr) / sizeof(arr[0]); printSorted(arr, n); return 0; } ``` **输出**： ``` 20 16 10 9 5 11 23 ``` 时间复杂度：O（n * sqrt（n））辅助复杂度：`O(n)` * * * * * *