# 用恒定的額外空間重新排列正數和負數 > 原文： [https://www.geeksforgeeks.org/rearrange-positive-and-negative-numbers/](https://www.geeksforgeeks.org/rearrange-positive-and-negative-numbers/) 給定一個正負數組，將它們排列成使所有負整數出現在數組**中的所有正整數之前，而無需使用任何其他數據結構**（例如哈希表，數組等）。出現的順序應 保持。 **示例**： ``` Input: [12 11 -13 -5 6 -7 5 -3 -6] Output: [-13 -5 -7 -3 -6 12 11 6 5] ``` 一個簡單的解決方案是使用另一個數組。 我們將原始數組的所有元素復制到新數組。 然后，我們遍歷新數組，并將所有負數和正數元素一一復制回原始數組。 在中討論了這種方法。 這種方法的問題在于它使用輔助數組，并且我們不允許使用任何數據結構來解決此問題。 一種不使用任何數據結構的方法是使用快排的使用分區過程。 想法是將 0 視為樞軸并圍繞其劃分數組。 這種方法的問題在于它會更改元素的相對順序。 在中討論了類似的分區過程。 現在，讓我們討論一些不使用任何其他數據結構并保留元素相對順序的方法。 **方法 1：修改插入排序** 我們可以修改[插入排序](http://geeksquiz.com/insertion-sort/)來解決此問題。 算法– ``` Loop from i = 1 to n - 1. a) If the current element is positive, do nothing. b) If the current element arr[i] is negative, we insert it into sequence arr[0..i-1] such that all positive elements in arr[0..i-1] are shifted one position to their right and arr[i] is inserted at index of first positive element. ``` 下面是實現– ## C++ ```cpp // C++ program to Rearrange positive and negative // numbers in a array #include <stdio.h> // A utility function to print an array of size n void printArray(int arr[], int n) { ????for (int i = 0; i < n; i++) ????????printf("%d ", arr[i]); ????printf("\n"); } // Function to Rearrange positive and negative // numbers in a array void RearrangePosNeg(int arr[], int n) { ????int key, j; ????for (int i = 1; i < n; i++) { ????????key = arr[i]; ????????// if current element is positive ????????// do nothing ????????if (key > 0) ????????????continue; ????????/* if current element is negative, ????????shift positive elements of arr[0..i-1], ????????to one position to their right */ ????????j = i - 1; ????????while (j >= 0 && arr[j] > 0) { ????????????arr[j + 1] = arr[j]; ????????????j = j - 1; ????????} ????????// Put negative element at its right position ????????arr[j + 1] = key; ????} } /* Driver program to test above functions */ int main() { ????int arr[] = { -12, 11, -13, -5, 6, -7, 5, -3, -6 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????RearrangePosNeg(arr, n); ????printArray(arr, n); ????return 0; } ```