# 應用給定方程后對數組排序 > 原文： [https://www.geeksforgeeks.org/sort-array-applying-given-equation/](https://www.geeksforgeeks.org/sort-array-applying-given-equation/) 我們有一個按升序排序的整數數組。 我們也有 3 個整數 A，B 和 C。我們需要對數組中的每個元素 x 應用 A * x * x + B * x + C，并對修改后的數組進行排序。 **例如**： ``` Input : arr[] = {-1, 0, 1, 2, 3, 4} A = -1, B = 2, C = -1 Output : {-9, -4, -4, -1, -1, 0} Input array is {-1, 0, 1, 2, 3, 4}. After applying the equation A*x*x + B*x + C on every element x we get, {-4,-1, 0, -1, -4, -9} After sorting, we get {-9, -4, -4, -1, -1, 0} ``` 詢問：Adobe **方法 1（簡單）**： 1-將給定的方程式應用于所有元素。`O(n)` 2-對修改后的數組進行排序。 O（n 對數 n） `O(N log N)`的時間復雜度 **方法 2（有效）：拋物線屬性** 給出的方程是拋物線的。 因此，將其應用于已排序數組的結果將導致一個數組，該數組的最大值和最小值與其子數組的左側和右側進行排序。 在上面的示例中，maximum 為 0，其左側{-4，-1}的子數組以升序排序，其右側{-1，-4，-9}的子數組以降序排序 。 所有我們需要做的是合并這些排序的數組，這些數組在時間上是線性的。 所以算法是： 1. 在每個元素上應用方程式。 2. 查找最大值/最小值。 3. 合并子數組。 注意：以下代碼假定修改后的數組先增大然后減小。 ## C++ ```cpp // C program to sort an array after applying equation // A*x*x + B*x + C #include<bits/stdc++.h> using namespace std; // Function to sort an array after applying given // equation. void sortArray(int arr[], int n, int A, int B, int C) { ???// Apply equation on all elements ????for (int i = 0; i < n; i++) ????????arr[i] = A*arr[i]*arr[i] + B*arr[i] + C; ????// Find maximum element in resultant array ????int index, maximum = INT_MIN; ????for (int i = 0; i< n; i++) ????{ ????????if (maximum < arr[i]) ????????{ ????????????index = i; ????????????maximum = arr[i]; ????????} ????} ????// Use maximum element as a break point ????// and merge both subarrays usin simple ????// merge function of merge sort ????int i = 0, j = n-1; ????int new_arr[n], k = 0; ????while (i < index && j > index) ????{ ????????if (arr[i] < arr[j]) ????????????new_arr[k++] = arr[i++]; ????????else ????????????new_arr[k++] = arr[j--]; ????} ????// Merge remaining elements ????while (i < index) ????????new_arr[k++] = arr[i++]; ????while (j > index) ????????new_arr[k++] = arr[j--]; ????new_arr[n-1] = maximum; ????// Modify original array ????for (int i = 0; i < n ; i++) ????????arr[i] = new_arr[i]; } // Driver code int main() { ????int arr[] = {-21 ,-15, 12, 13, 14 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????int A = -6, B =-7, C = 2; ????sortArray(arr, n, A, B, C); ????cout << "Array after sorting is : n"; ????for (int i=0; i<n; i++) ???????cout << arr[i] << " "; ????return 0; } ``` ## Java ```java // Java program to sort an array after applying equation // A*x*x + B*x + C class Main { ????// Function to sort an array after applying given ????// equation. ????static void sortArray(int arr[], int n, int A, int B, int C) ????{ ???????// Apply equation on all elements ????????for (int i = 0; i < n; i++) ????????????arr[i] = A*arr[i]*arr[i] + B*arr[i] + C; ????????// Find maximum element in resultant array ????????int index=-1; ????????int maximum = -999999; ????????for (int i = 0; i< n; i++) ????????{ ????????????if (maximum < arr[i]) ????????????{ ????????????????index = i; ????????????????maximum = arr[i]; ????????????} ????????} ????????// Use maximum element as a break point ????????// and merge both subarrays usin simple ????????// merge function of merge sort ????????int i = 0, j = n-1; ????????int[] new_arr = new int[n]; ????????int k = 0; ????????while (i < index && j > index) ????????{ ????????????if (arr[i] < arr[j]) ????????????????new_arr[k++] = arr[i++]; ????????????else ????????????????new_arr[k++] = arr[j--]; ????????} ????????// Merge remaining elements ????????while (i < index) ????????????new_arr[k++] = arr[i++]; ????????while (j > index) ????????????new_arr[k++] = arr[j--]; ????????new_arr[n-1] = maximum; ????????// Modify original array ????????for (int p = 0; p < n ; p++) ????????????arr[p] = new_arr[p]; ????} ????// main function ????public static void main (String[] args)? ????{ ????????int arr[] = {-21 ,-15, 12, 13, 14 }; ????????int n = arr.length; ????????int A = -6, B =-7, C = 2; ????????sortArray(arr, n, A, B, C); ????????System.out.println("Array after sorting is : "); ????????for (int i=0; i<n; i++) ???????????System.out.print(arr[i]+" "); ????} } /* This code is contributed by Harsh Agarwal */ ``` ## Python3 ```py # Python3 program to sort an? # array after applying equation? # A*x*x + B*x + C? import sys # Function to sort an array? # after applying given equation.? def sortArray(arr, n, A, B, C): ????# Apply equation on all elements? ????for i in range(n): ????????arr[i] = (A * arr[i] * arr[i] +? ??????????????????B * arr[i] + C) ????index = -(sys.maxsize - 1) ????maximum = -(sys.maxsize - 1) ????# Find maximum element in ????# resultant array ????for i in range(n): ????????if maximum < arr[i]: ????????????index = i ????????????maximum = arr[i] ????# Use maximum element as a break point? ????# and merge both subarrays usin simple? ????# merge function of merge sort? ????i = 0; j = n - 1; ????new_arr = [0] * n ????k = 0 ????while i < index and j > index: ????????if arr[i] < arr[j]: ????????????new_arr[k] = arr[i] ????????????k += 1 ????????????i += 1 ????????else: ????????????new_arr[k] = arr[j] ????????????k += 1 ????????????j -= 1 ????# Merge remaining elements? ????while i < index: ????????new_arr[k] = arr[i] ????????k += 1 ????????i += 1 ????# Modify original array? ????while j > index: ????????new_arr[k] = arr[j] ????????k += 1 ????????j -= 1 ????????new_arr[n - 1] = maximum? ????for i in range(n): ????????arr[i] = new_arr[i] # Driver code arr = [-21, -15, 12, 13, 14] n = len(arr) A = -6 B= -7 C = 2 sortArray(arr, n, A, B, C) print("Array after sorting is:") for i in range(n): ????print(arr[i], end = " ") # This code is contributed? # by Shrikant13 ``` ## C# ```cs // C# program to sort an array after applying equation? // A*x*x + B*x + C? using System;? class MAIN? {? ????// Function to sort an array after applying given? ????// equation.? ????static void sortArray(int[] arr, int n, int A, int B, int C)? ????{? ???????// Apply equation on all elements? ????????for (int i = 0; i < n; i++)? ????????????arr[i] = A*arr[i]*arr[i] + B*arr[i] + C;? ????????// Find maximum element in resultant array? ????????int index=-1;? ????????int maximum = -999999;? ????????for (int i = 0; i< n; i++)? ????????{? ????????????if (maximum < arr[i])? ????????????{? ????????????????index = i;? ????????????????maximum = arr[i];? ????????????}? ????????}? ????????// Use maximum element as a break point? ????????// and merge both subarrays usin simple? ????????// merge function of merge sort? ????????int l = 0, j = n-1;? ????????int[] new_arr = new int[n];? ????????int k = 0;? ????????while (l < index && j > index)? ????????{? ????????????if (arr[l] < arr[j])? ????????????????new_arr[k++] = arr[l++];? ????????????else ????????????????new_arr[k++] = arr[j--];? ????????}? ????????// Merge remaining elements? ????????while (l < index)? ????????????new_arr[k++] = arr[l++];? ????????while (j > index)? ????????????new_arr[k++] = arr[j--];? ????????new_arr[n-1] = maximum;? ????????// Modify original array? ????????for (int p = 0; p < n ; p++)? ????????????arr[p] = new_arr[p];? ????}? ????// main function? ????public static void Main ()?? ????{? ????????int[] arr = {-21 ,-15, 12, 13, 14 };? ????????int n = arr.Length;? ????????int A = -6, B =-7, C = 2;? ????????sortArray(arr, n, A, B, C);? ????????Console.Write("Array after sorting is : "+"\n");? ????????for (int i=0; i<n; i++)? ???????????Console.Write(arr[i]+" ");? ????}? }? ``` ## PHP ```php <?php // PHP program to sort an array after? // applying equation A*x*x + B*x + C // Function to sort an array after? // applying given?? equation. function sortArray(&$arr, $n, $A, $B, $C) { ????// Apply equation on all elements ????for ($i = 0; $i < $n; $i++) ????????$arr[$i] = $A * $arr[$i] * $arr[$i] + ???????????????????$B * $arr[$i] + $C; ????// Find maximum element in? ????// resultant array ????$index = 0;? ????$maximum = PHP_INT_MIN; ????for ($i = 0; $i < $n; $i++) ????{ ????????if ($maximum < $arr[$i]) ????????{ ????????????$index = $i; ????????????$maximum = $arr[$i]; ????????} ????} ????// Use maximum element as a break point ????// and merge both subarrays usin simple ????// merge function of merge sort ????$i = 0; ????$j = $n - 1; ????$new_arr = array(); ????while ($i < $index && $j > $index) ????{ ????????if ($arr[$i] < $arr[$j]) ????????????array_push($new_arr, $arr[$i++]); ????????else ????????????array_push($new_arr, $arr[$j--]); ????} ????// Merge remaining elements ????while ($i < $index) ????????array_push($new_arr, $arr[$i++]); ????while ($j > $index) ????????array_push($new_arr, $arr[$j--]); ????array_push($new_arr, $maximum); ????// Modify original array ????for ($i = 0; $i < count($new_arr) ; $i++) ????????$arr[$i] = $new_arr[$i]; } // Driver code $arr = array(-21 ,-15, 12, 13, 14 ); $n = count($arr); $A = -6; $B = -7; $C = 2; sortArray($arr, $n, $A, $B, $C); echo "Array after sorting is : \n"; for ($i = 0; $i < $n; $i++) ????echo $arr[$i] . " "; // This code is contributed by mits ?> ``` **輸出**： ``` Array after sorting is : -2497 -1272 -1243 -1103 -946 ``` **時間復雜度**：`O(n)` **輔助空間**：`O(n)` **參考**： [http://stackoverflow.com/questions/4551599/sorting-result-array](http://stackoverflow.com/questions/4551599/sorting-result-array) 本文由 [**Sahil Chhabra**](https://www.facebook.com/sahil.chhabra.965) 貢獻。 如果您喜歡 GeeksforGeeks 并希望做出貢獻，則還可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰寫文章，或將您的文章郵寄至 tribution@geeksforgeeks.org。 查看您的文章出現在 GeeksforGeeks 主頁上，并幫助其他 Geeks。