# 按頻率對元素排序| 系列 1 > 原文： [https://www.geeksforgeeks.org/sort-elements-by-frequency/](https://www.geeksforgeeks.org/sort-elements-by-frequency/) 如果 2 個數字具有相同的頻率，則以遞減的頻率打印數組的元素，然后打印第一個出現的頻率。 **示例**： ``` Input: arr[] = {2, 5, 2, 8, 5, 6, 8, 8} Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6} Input: arr[] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8} Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999} ``` **方法 1（使用排序）** * 使用排序算法對元素 **O（nlogn）**進行排序 * 掃描排序的數組，并構造一個 2D 元素數組，并計數 **`O(n)`。** * 根據計數 **O（nlogn）**對 2D 數組排序。 **示例**： ``` Input 2 5 2 8 5 6 8 8 After sorting we get 2 2 5 5 6 8 8 8 Now construct the 2D array as 2, 2 5, 2 6, 1 8, 3 Sort by count 8, 3 2, 2 5, 2 6, 1 ``` **如果頻率相同，如何保持元素順序？** ： 如果頻率相同，上述方法無法確定元素的順序。 為了解決這個問題，我們應該在第 3 步中使用索引，如果兩個計數相同，那么我們應該首先處理（或打印）具有較低索引的元素。 在步驟 1 中，我們應該存儲索引而不是元素。 ``` Input 5 2 2 8 5 6 8 8 After sorting we get Element 2 2 5 5 6 8 8 8 Index 1 2 0 4 5 3 6 7 Now construct the 2D array as Index, Count 1, 2 0, 2 5, 1 3, 3 Sort by count (consider indexes in case of tie) 3, 3 0, 2 1, 2 5, 1 Print the elements using indexes in the above 2D array. ``` 下面是上述方法的實現。 ``` // Sort elements by frequency. If two elements have same // count, then put the elements that appears first #include <bits/stdc++.h> using namespace std; // Used for sorting struct ele { ????int count, index, val; }; // Used for sorting by value bool mycomp(struct ele a, struct ele b) { ????return (a.val < b.val); } // Used for sorting by frequency. And if frequency is same, // then by appearance bool mycomp2(struct ele a, struct ele b) { ????if (a.count != b.count) ????????return (a.count < b.count); ????else ????????return a.index > b.index; } void sortByFrequency(int arr[], int n) { ????struct ele element[n]; ????for (int i = 0; i < n; i++) { ????????// Fill Indexes ????????element[i].index = i; ????????// Initialize counts as 0 ????????element[i].count = 0; ????????// Fill values in structure ????????// elements ????????element[i].val = arr[i]; ????} ????/* Sort the structure elements according to value, ???????we used stable sort so relative order is maintained. */ ????stable_sort(element, element + n, mycomp); ????/* initialize count of first element as 1 */ ????element[0].count = 1; ????/* Count occurrences of remaining elements */ ????for (int i = 1; i < n; i++) { ????????if (element[i].val == element[i - 1].val) { ????????????element[i].count += element[i - 1].count + 1; ????????????/* Set count of previous element as -1, we are ???????????????doing this because we'll again sort on the ???????????????basis of counts (if counts are equal than on ???????????????the basis of index)*/ ????????????element[i - 1].count = -1; ????????????/* Retain the first index (Remember first index ???????????????is always present in the first duplicate we ???????????????used stable sort. */ ????????????element[i].index = element[i - 1].index; ????????} ????????/* Else If previous element is not equal to current ??????????so set the count to 1 */ ????????else ????????????element[i].count = 1; ????} ????/* Now we have counts and first index for each element so now ???????sort on the basis of count and in case of tie use index ???????to sort.*/ ????stable_sort(element, element + n, mycomp2); ????for (int i = n - 1, index = 0; i >= 0; i--) ????????if (element[i].count != -1) ????????????for (int j = 0; j < element[i].count; j++) ????????????????arr[index++] = element[i].val; } // Driver program int main() { ????int arr[] = { 2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????sortByFrequency(arr, n); ????for (int i = 0; i < n; i++) ????????cout << arr[i] << " "; ????return 0; } ``` **輸出**： ``` 8 8 8 2 2 5 5 6 -1 9999999 ``` 感謝 Gaurav Ahirwar 提供了上述實現。 **方法 2（使用哈希和排序）** 使用哈希機制，我們可以將元素（也包括第一個索引）及其計數存儲在哈希中。 最后，根據哈希元素的計數對它們進行排序。 Below is the implementation of above approach. ``` #include <bits/stdc++.h> using namespace std; // Compare function bool fcompare(pair<int, pair<int, int> > p, ????????????????pair<int, pair<int, int> > p1) { ????if (p.second.second != p1.second.second) ????????return (p.second.second > p1.second.second); ????else ????????return (p.second.first < p1.second.first); } void sortByFrequency(int arr[], int n) { ????unordered_map<int, pair<int, int> > hash; // hash map ????for (int i = 0; i < n; i++) { ????????if (hash.find(arr[i]) != hash.end()) ????????????hash[arr[i]].second++; ????????else ????????????hash[arr[i]] = make_pair(i, 1); ????} // store the count of all the elements in the hashmap ????// Iterator to Traverse the Hashmap ????auto it = hash.begin(); ????// Vector to store the Final Sortted order ????vector<pair<int, pair<int, int> > > b; ????for (it; it != hash.end(); ++it) ????????b.push_back(make_pair(it->first, it->second)); ????sort(b.begin(), b.end(), fcompare); ????// Printing the Sorted sequence ????for (int i = 0; i < b.size(); i++) { ????????int count = b[i].second.second; ????????while (count--) ????????????cout << b[i].first << " "; ????} } // Driver Function int main() { ????int arr[] = { 2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????sortByFrequency(arr, n); ????return 0; } ``` **Output**: ``` 8 8 8 2 2 5 5 6 -1 9999999 ``` **方法 3（使用 BST 和排序）** * 在 BST 中一一插入元素，如果已經存在一個元素，則增加節點的計數。 二叉搜索樹的節點（用于此方法）如下。 ``` struct tree { ????int element; ????int first_index /*To handle ties in counts*/ ????????int count; } BST;</div> ``` * 將第一個索引和相應的 BST 計數存儲在 2D 數組中。 * 根據計數對 2D 數組進行排序（在平局的情況下使用索引）。 **時間復雜度：如果使用[自平衡二分搜索樹](http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree)，則** O（nlogn）。 這在 [Set 2](https://www.geeksforgeeks.org/sort-elements-by-frequency-set-2/) 中實現。 **第 2 組**： [按頻率對元素進行排序| 組合 2](https://www.geeksforgeeks.org/sort-elements-by-frequency-set-2/)