# 按頻率對元素排序| 系列 2 > 原文： [https://www.geeksforgeeks.org/sort-elements-by-frequency-set-2/](https://www.geeksforgeeks.org/sort-elements-by-frequency-set-2/) 給定整數數組，請根據元素的頻率對數組進行排序。 例如，如果輸入數組是`{2, 3, 2, 4, 5, 12, 12, 2, 3, 3, 3, 12}`，則將該數組修改為`{3, 3, 3, 3, 2, 2, 2, 12, 12, 4, 5}`。 在[以前的文章](https://www.geeksforgeeks.org/sort-elements-by-frequency/)中，我們討論了根據頻率進行排序的所有方法。 在本文中，將詳細討論方法 2，并提供了該方法的 C++ 實現。 以下是詳細的算法。 * 創建一個 [BST](https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/) ，并在創建 BST 時保持同一 BST 中每個即將到來的元素的計數即頻率。 如果使用自平衡 BST，則此步驟可能需要`O(nLogn)`時間。 * 對 BST 進行遍歷，并將每個元素和每個元素的計數存儲在輔助數組中。 讓我們將輔助數組稱為`count[]`。 注意，該數組的每個元素都是元素和頻率對。 此步驟需要`O(n)`時間。 * 根據元素的頻率對`count[]`進行排序。 如果使用`O(nLogn)`排序算法，則此步驟需要`O(nLogn)`時間。 * 遍歷排序后的數組`count[]`。 對于每個元素`x`，請按“頻率”倍數打印，其中“頻率”是`x`的頻率。 此步驟需要`O(n)`時間。 如果我們使用`O(nLogn)`排序算法，并且將自平衡 BST 與`O(nLogn)`插入操作。 以下是上述算法的實現。 ``` // Implementation of above algorithm in C++. #include <iostream> #include <stdlib.h> using namespace std; /* A BST node has data, freq, left and right pointers */ struct BSTNode { ????struct BSTNode *left; ????int data; ????int freq; ????struct BSTNode *right; }; // A structure to store data and its frequency struct dataFreq { ????int data; ????int freq; }; /* Function for qsort() implementation. Compare frequencies to ???sort the array according to decreasing order of frequency */ int compare(const void *a, const void *b) { ????return ( (*(const dataFreq*)b).freq - (*(const dataFreq*)a).freq ); } /* Helper function that allocates a new node with the given data, ???frequency as 1 and NULL left and right? pointers.*/ BSTNode* newNode(int data) { ????struct BSTNode* node = new BSTNode; ????node->data = data; ????node->left = NULL; ????node->right = NULL; ????node->freq = 1; ????return (node); } // A utility function to insert a given key to BST. If element // is already present, then increases frequency BSTNode *insert(BSTNode *root, int data) { ????if (root == NULL) ????????return newNode(data); ????if (data == root->data) // If already present ????????root->freq += 1; ????else if (data < root->data) ????????root->left = insert(root->left, data); ????else ????????root->right = insert(root->right, data); ????return root; } // Function to copy elements and their frequencies to count[]. void store(BSTNode *root, dataFreq count[], int *index) { ????// Base Case ????if (root == NULL) return; ????// Recur for left substree ????store(root->left, count, index); ????// Store item from root and increment index ????count[(*index)].freq = root->freq; ????count[(*index)].data = root->data; ????(*index)++; ????// Recur for right subtree ????store(root->right, count, index); } // The main function that takes an input array as an argument // and sorts the array items according to frequency void sortByFrequency(int arr[], int n) { ????// Create an empty BST and insert all array items in BST ????struct BSTNode *root = NULL; ????for (int i = 0; i < n; ++i) ????????root = insert(root, arr[i]); ????// Create an auxiliary array 'count[]' to store data and ????// frequency pairs. The maximum size of this array would ????// be n when all elements are different ????dataFreq count[n]; ????int index = 0; ????store(root, count, &index); ????// Sort the count[] array according to frequency (or count) ????qsort(count, index, sizeof(count[0]), compare); ????// Finally, traverse the sorted count[] array and copy the ????// i'th item 'freq' times to original array 'arr[]' ????int j = 0; ????for (int i = 0; i < index; i++) ????{ ????????for (int freq = count[i].freq; freq > 0; freq--) ????????????arr[j++] = count[i].data; ????} } // A utility function to print an array of size n void printArray(int arr[], int n) { ????for (int i = 0; i < n; i++) ????????cout << arr[i] << " "; ????cout << endl; } /* Driver program to test above functions */ int main() { ????int arr[] = {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12}; ????int n = sizeof(arr)/sizeof(arr[0]); ????sortByFrequency(arr, n); ????printArray(arr, n); ????return 0; } ``` **輸出**： ``` 3 3 3 3 2 2 2 12 12 5 4 ``` **練習**： 上面的實現并不能保證具有相同頻率的元素的原始順序（例如，輸入 4 在 5 之前，而輸出 4 在 5 之后）。 擴展實現以保持原始順序。 例如，如果兩個元素具有相同的頻率，則在輸入數組中打印第一個出現的元素。 本文由 [**Chandra Prakash**](https://www.facebook.com/chandra.prakash.52643?fref=ts) 編譯。 如果發現任何不正確的地方，或者想分享有關上述主題的更多信息，請發表評論