# 使用內置排序功能重新排列正數和負數 > 原文： [https://www.geeksforgeeks.org/rearrange-positive-negative-numbers-using-inbuilt-sort-function/](https://www.geeksforgeeks.org/rearrange-positive-negative-numbers-using-inbuilt-sort-function/) 給定正負數數組，請排列它們，使所有負整數出現在數組中所有正整數之前，而無需使用任何其他數據結構（例如哈希表，數組等）。應保持外觀的順序。 **示例**： ``` Input : arr[] = [12, 11, -13, -5, 6, -7, 5, -3, -6] Output : arr[] = [-13, -5, -7, -3, -6, 12, 11, 6, 5] Input : arr[] = [-12, 11, 0, -5, 6, -7, 5, -3, -6] Output : arr[] = [-12, -5, -7, -3, -6, 0, 11, 6, 5] ``` 以前的方法：在中已經討論了一些方法。 它們充其量已實現。 **方法 3**：還有另一種方法。 在 C++ STL 中，有一個內置函數[`std::sort()`](https://www.geeksforgeeks.org/sort-c-stl/)。 我們可以修改`comp()`函數以獲得所需的結果。 因為我們必須先放置負數，然后再放置正數。 我們還必須在正數和負數之間保持零（如果存在）。 此代碼中的`comp()`函數以所需順序重新排列給定的數組。 在`bool comp(int a, int b)`中，如果`arr[]`中的整數`'a'`具有第`j`個索引，整數`'b'`具有第`i`個索引元素，則`j > i`。 `comp()`函數將以這種方式調用。 如果`comp()`返回`true`，則將完成交換。 ``` // CPP program to rearrange positive? // and negative integers keeping? // order of elements. #include <bits/stdc++.h> using namespace std; bool comp(int a, int b) { // swap not needed if((a > 0 && b > 0) ||? ???(a < 0 && b < 0) ||? ???(a > 0 && b < 0 )) return false; // swap needed if(a < 0 && b > 0)? return true; // swap not needed if((a == 0 && b < 0) ||? ???(a > 0 && b == 0)) return false; // swap needed if((a == 0 && b > 0) ||? ???(a < 0 && b == 0)) return true; } void rearrange(int arr[], int n) { ????sort(arr, arr + n, comp); } // Driver code int main() { ????int arr[] = { -12, 11, -13, -5,? ??????????????????6, -7, 5, -3, -6 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????rearrange(arr, n); ????for (int i = 0; i < n; i++) ????????cout << " " << arr[i]; ????return 0; } ``` **輸出**： ``` -12 -13 -5 -7 -3 -6 11 6 5 ``` **輸出**： ``` -12 -13 -5 -7 -3 -6 11 6 5 ``` **時間復雜度**與排序即`O(n log n)`相同。 由于我們使用的是標準排序功能。 但這確實更快，因為內置排序功能使用 [introsort](https://www.geeksforgeeks.org/c-qsort-vs-c-sort/) 。 **方法 4**：還有另一種方法可以解決此問題。 我們遞歸遍歷數組，將其切成兩半（`array[start..start]`和`array[(start + 1).. end]`，然后繼續拆分 數組，直到到達最后一個元素，然后開始將其合并回去，其想法是在任何時候使數組保持正負整數的正確順序，合并邏輯為： （I）如果`arr[start]`為負數，則按原樣合并其余數組，以保持負數的順序。 這樣做的原因是，由于我們要從遞歸調用中追溯，因此我們開始在數組中從右向左移動，從而自然地保持了原始序列。 （II）如果`arr[start]`為正，則合并數組的其余部分，但是右旋數組的一半`[(start + 1) .. end]`。 旋轉的想法是合并數組，以便使正`array[start]`始終與正元素合并。 但是，這里唯一的事情是合并后的數組將在左側具有所有正元素，在右側具有負元素。 因此，我們在每次遞歸中都顛倒了順序，以得到負元素的原始序列，然后再得到正元素。 可以觀察到，因為我們在每次遞歸中與正的第一個元素合并的同時反轉了數組，所以正元素的順序雖然排在負元素之后，但順序相反。 因此，作為最后一步，我們只反轉最終數組的正半部分，然后得到預期的序列。 下面是上述方法的實現： ## CPP ``` // C++ implementation of the above approach #include <iostream> void printArray(int array[], int length) { ????std::cout << "["; ????for(int i = 0; i < length; i++) ????{ ????????std::cout << array[i]; ????????if(i < (length - 1)) ????????????std::cout << ", "; ????????else ????????????std::cout << "]" << std::endl; ????} } void reverse(int array[], int start, int end) { ????while(start < end) ????{ ????????int temp = array[start]; ????????array[start] = array[end]; ????????array[end] = temp; ????????start++; ????????end--; ????} } // Rearrange the array with all negative integers // on left and positive integers on right? // use recursion to split the array with first element // as one half and the rest array as another and then? // merge it with head of the array in each step?? void rearrange(int array[], int start, int end) { ????// exit condition? ????if(start == end) ????????return; ????// rearrange the array except the first ????// element in each recursive call? ????rearrange(array, (start + 1), end); ????// If the first element of the array is positive,? ????// then right-rotate the array by one place first ????// and then reverse the merged array. ????if(array[start] >= 0) ????{ ????????reverse(array, (start + 1), end); ????????reverse(array, start, end); ????} } // Driver code int main() { ????int array[] = {-12, -11, -13, -5, -6, 7, 5, 3, 6}; ????int length = (sizeof(array) / sizeof(array[0])); ????int countNegative = 0; ????for(int i = 0; i < length; i++) ????{ ????????if(array[i] < 0) ????????????countNegative++; ????} ????std::cout << "array: "; ????printArray(array, length); ????rearrange(array, 0, (length - 1)); ????reverse(array, countNegative, (length - 1)); ????std::cout << "rearranged array: "; ????printArray(array, length); ????return 0; } ```