# 根據另一個數組定義的順序對數組進行排序 > 原文： [https://www.geeksforgeeks.org/sort-array-according-order-defined-another-array/](https://www.geeksforgeeks.org/sort-array-according-order-defined-another-array/) 給定兩個數組`A1[]`和`A2[]`，對`A1`進行排序，以使元素之間的相對順序與`A2`中的相對順序相同。 對于`A2`中不存在的元素，最后按排序順序附加它們。 **例如**： ``` Input: A1[] = {2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8} A2[] = {2, 1, 8, 3} Output: A1[] = {2, 2, 1, 1, 8, 8, 3, 5, 6, 7, 9} ``` 該代碼應處理所有情況，例如與`A1[]`相比，`A2[]`中的元素數量可能更多或更少。 `A2[]`可能包含`A1[]`中可能不存在的某些元素，反之亦然。 **來源**： [Amazon 訪談| 系列 110（校園內）](https://www.geeksforgeeks.org/amazon-interview-set-110-campus/) [](https://practice.geeksforgeeks.org/problem-page.php?pid=434) ## 強烈建議您在繼續解決方案之前，單擊此處進行練習。 **方法 1（使用排序和二分搜索）** 假設`A1[]`的大小為`m`，而`A2[]`的大小為`n`。 * 創建一個大小為`m`的臨時數組`temp`，并將`A1[]`的內容復制到其中。 * 創建另一個訪問過的數組，并將其中的所有條目初始化為`false`。 `visit[]`用于標記`temp[]`中復制到`A1[]`的那些元素。 * 排序`temp[]` * 將輸出索引`ind`初始化為 0。 * 對`A2[]`中的每個元素`A2[i]`進行跟蹤 * 二分搜索`temp[]`中所有出現的`A2[i]`（如果存在），然后將所有出現的內容復制到`A1[ind]`并遞增`ind`。 還標記復制的元素`visit[]` * 將所有未訪問的元素從`temp[]`復制到`A1[]` . 下圖是上述方法的模擬：  下面是上述方法的實現： ## C++ ```cpp // A C++ program to sort an array according to the order defined // by another array #include <bits/stdc++.h> using namespace std; // A Binary Search based function to find index of FIRST occurrence // of x in arr[].? If x is not present, then it returns -1 // The same can be done using the lower_bound // function in C++ STL int first(int arr[], int low, int high, int x, int n) { ????// Checking condition ????if (high >= low) { ????????// FInd the mid element ????????int mid = low + (high - low) / 2; ????????// Check if the element is the extreme left ????????// in the left half of the array ????????if ((mid == 0 || x > arr[mid - 1]) && arr[mid] == x) ????????????return mid; ????????// If the element lies on the right half ????????if (x > arr[mid]) ????????????return first(arr, (mid + 1), high, x, n); ????????// Check for element in the left half ????????return first(arr, low, (mid - 1), x, n); ????} ????// ELement not found ????return -1; } // Sort A1[0..m-1] according to the order defined by A2[0..n-1]. void sortAccording(int A1[], int A2[], int m, int n) { ????// The temp array is used to store a copy of A1[] and visited[] ????// is used mark the visited elements in temp[]. ????int temp[m], visited[m]; ????for (int i = 0; i < m; i++) { ????????temp[i] = A1[i]; ????????visited[i] = 0; ????} ????// Sort elements in temp ????sort(temp, temp + m); ????// for index of output which is sorted A1[] ????int ind = 0; ????// Consider all elements of A2[], find them in temp[] ????// and copy to A1[] in order. ????for (int i = 0; i < n; i++) { ????????// Find index of the first occurrence of A2[i] in temp ????????int f = first(temp, 0, m - 1, A2[i], m); ????????// If not present, no need to proceed ????????if (f == -1) ????????????continue; ????????// Copy all occurrences of A2[i] to A1[] ????????for (int j = f; (j < m && temp[j] == A2[i]); j++) { ????????????A1[ind++] = temp[j]; ????????????visited[j] = 1; ????????} ????} ????// Now copy all items of temp[] ????// which are not present in A2[] ????for (int i = 0; i < m; i++) ????????if (visited[i] == 0) ????????????A1[ind++] = temp[i]; } // Utility function to print an array void printArray(int arr[], int n) { ????// Iterate in the array ????for (int i = 0; i < n; i++) ????????cout << arr[i] << " "; ????cout << endl; } // Driver Code int main() { ????int A1[] = { 2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8 }; ????int A2[] = { 2, 1, 8, 3 }; ????int m = sizeof(A1) / sizeof(A1[0]); ????int n = sizeof(A2) / sizeof(A2[0]); ????// Prints the sorted array ????cout << "Sorted array is \n"; ????sortAccording(A1, A2, m, n); ????printArray(A1, m); ????return 0; } ```