# 用恒定的额外空间重新排列正数和负数 > 原文： [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; } ```