# 在`O(n)`時間和`O(1)`額外空間中重新排列正數和負數 > 原文： [https://www.geeksforgeeks.org/rearrange-positive-and-negative-numbers-publish/](https://www.geeksforgeeks.org/rearrange-positive-and-negative-numbers-publish/) 數組包含隨機順序的正數和負數。 重新排列數組元素，以便交替放置正數和負數。 正數和負數不必相等。 如果有更多正數，它們將出現在數組的末尾。 如果還有更多負數，它們也會出現在數組的末尾。 例如，如果輸入數組為`[-1, 2, -3, 4, 5, 6, -7, 8, 9]`，則輸出應為`[9, -7, 8, -3, 5, - 1, 2, 4, 6]` **注意**：分區過程會更改元素的相對順序。 即 這種方法不能保持元素外觀的順序。 [請參見此](https://www.geeksforgeeks.org/rearrange-array-alternating-positive-negative-items-o1-extra-space/)，以維護此問題中元素的出現順序。 解決方案是先使用快排的分區過程將正數和負數分開。 在分區過程中，將 0 視為樞軸元素的值，以便將所有負數放在正數之前。 一旦負數和正數分開，我們就從第一個負數和第一個正數開始，然后將每個備用負數與下一個正數交換。 ## C++ ```cpp // A C++ program to put positive // numbers at even indexes (0, 2, 4,..)? // and negative numbers at odd? // indexes (1, 3, 5, ..) #include <iostream> using namespace std; class GFG { ????public: ????void rearrange(int [],int); ????void swap(int *,int *); ????void printArray(int [],int); }; // The main function that rearranges? // elements of given array. It puts // positive elements at even indexes? // (0, 2, ..) and negative numbers? // at odd indexes (1, 3, ..). void GFG :: rearrange(int arr[], int n) { ????// The following few lines are? ????// similar to partition process ????// of QuickSort. The idea is to? ????// consider 0 as pivot and ????// divide the array around it. ????int i = -1; ????for (int j = 0; j < n; j++) ????{ ????????if (arr[j] < 0) ????????{ ????????????i++; ????????????swap(&arr[i], &arr[j]); ????????} ????} ????// Now all positive numbers are at? ????// end and negative numbers at the ????// beginning of array. Initialize? ????// indexes for starting point of ????// positive and negative numbers? ????// to be swapped ????int pos = i + 1, neg = 0; ????// Increment the negative index by? ????// 2 and positive index by 1, ????// i.e., swap every alternate negative? ????// number with next positive number ????while (pos < n && neg < pos &&? ?????????????????????arr[neg] < 0) ????{ ????????swap(&arr[neg], &arr[pos]); ????????pos++; ????????neg += 2; ????} } // A utility function? // to swap two elements void GFG :: swap(int *a, int *b) { ????int temp = *a; ????*a = *b; ????*b = temp; } // A utility function to print an array void GFG :: printArray(int arr[], int n) { ????for (int i = 0; i < n; i++) ????????cout << arr[i] << " "; } // Driver Code int main()? { ????int arr[] = {-1, 2, -3, 4,? ??????????????????5, 6, -7, 8, 9}; ????int n = sizeof(arr) / sizeof(arr[0]); ????GFG test; ????test.rearrange(arr, n); ????test.printArray(arr, n); ????return 0; } // This code is contributed? // by vt_Yogesh Shukla 1 ``` ## C ``` // A C++ program to put positive numbers at even indexes (0,? // 2, 4,..) and negative numbers at odd indexes (1, 3, 5, ..) #include <stdio.h> // prototype for swap void swap(int *a, int *b); // The main function that rearranges elements of given array.? // It puts? positive elements at even indexes (0, 2, ..) and? // negative numbers at odd indexes (1, 3, ..). void rearrange(int arr[], int n) { ????// The following few lines are similar to partition process ????// of QuickSort.? The idea is to consider 0 as pivot and ????// divide the array around it. ????int i = -1; ????for (int j = 0; j < n; j++) ????{ ????????if (arr[j] < 0) ????????{ ????????????i++; ????????????swap(&arr[i], &arr[j]); ????????} ????} ????// Now all positive numbers are at end and negative numbers ????// at the beginning of array. Initialize indexes for starting ????// point of positive and negative numbers to be swapped ????int pos = i+1, neg = 0; ????// Increment the negative index by 2 and positive index by 1, ????// i.e., swap every alternate negative number with next? ????// positive number ????while (pos < n && neg < pos && arr[neg] < 0) ????{ ????????swap(&arr[neg], &arr[pos]); ????????pos++; ????????neg += 2; ????} } // A utility function to swap two elements void swap(int *a, int *b) { ????int temp = *a; ????*a = *b; ????*b = temp; } // A utility function to print an array void printArray(int arr[], int n) { ????for (int i = 0; i < n; i++) ????????printf("%4d ", arr[i]); } // Driver program to test above functions int main() { ????int arr[] = {-1, 2, -3, 4, 5, 6, -7, 8, 9}; ????int n = sizeof(arr)/sizeof(arr[0]); ????rearrange(arr, n); ????printArray(arr, n); ????return 0; } ``` ## Java ```java // A JAVA program to put positive numbers at even indexes // (0, 2, 4,..) and negative numbers at odd indexes (1, 3, // 5, ..) import java.io.*; class Alternate { ????// The main function that rearranges elements of given ????// array.? It puts positive elements at even indexes (0, ????// 2, ..) and negative numbers at odd indexes (1, 3, ..). ????static void rearrange(int arr[], int n) ????{ ????????// The following few lines are similar to partition ????????// process of QuickSort.? The idea is to consider 0 ????????// as pivot and divide the array around it. ????????int i = -1, temp = 0; ????????for (int j = 0; j < n; j++) ????????{ ????????????if (arr[j] < 0) ????????????{ ????????????????i++; ????????????????temp = arr[i]; ????????????????arr[i] = arr[j]; ????????????????arr[j] = temp; ????????????} ????????} ????????// Now all positive numbers are at end and negative numbers at ????????// the beginning of array. Initialize indexes for starting point ????????// of positive and negative numbers to be swapped ????????int pos = i+1, neg = 0; ????????// Increment the negative index by 2 and positive index by 1, i.e., ????????// swap every alternate negative number with next positive number ????????while (pos < n && neg < pos && arr[neg] < 0) ????????{ ????????????temp = arr[neg]; ????????????arr[neg] = arr[pos]; ????????????arr[pos] = temp; ????????????pos++; ????????????neg += 2; ????????} ????} ????// A utility function to print an array ????static void printArray(int arr[], int n) ????{ ????????for (int i = 0; i < n; i++) ????????????System.out.print(arr[i] + "?? "); ????} ????/*Driver function to check for above functions*/ ????public static void main (String[] args) ????{ ????????int arr[] = {-1, 2, -3, 4, 5, 6, -7, 8, 9}; ????????int n = arr.length; ????????rearrange(arr,n); ????????System.out.println("Array after rearranging: "); ????????printArray(arr,n); ????} } /*This code is contributed by Devesh Agrawal*/ ``` ## Python ``` #? Python program to put positive numbers at even indexes (0,? // 2, 4,..) and #? negative numbers at odd indexes (1, 3, 5, ..) # The main function that rearranges elements of given array.? # It puts? positive elements at even indexes (0, 2, ..) and? # negative numbers at odd indexes (1, 3, ..). def rearrange(arr, n): ????# The following few lines are similar to partition process ????# of QuickSort.? The idea is to consider 0 as pivot and ????# divide the array around it. ????i = -1 ????for j in range(n): ????????if (arr[j] < 0): ????????????i += 1 ????????????# swapping of arr ????????????arr[i], arr[j] = arr[j], arr[i] ????# Now all positive numbers are at end and negative numbers ????# at the beginning of array. Initialize indexes for starting ????# point of positive and negative numbers to be swapped ????pos, neg = i+1, 0 ????# Increment the negative index by 2 and positive index by 1, ????# i.e., swap every alternate negative number with next? ????# positive number ????while (pos < n and neg < pos and arr[neg] < 0): ????????# swapping of arr ????????arr[neg], arr[pos] = arr[pos], arr[neg] ????????pos += 1 ????????neg += 2 # A utility function to print an array def printArray(arr, n): ????for i in range(n): ????????print arr[i], # Driver program to test above functions arr = [-1, 2, -3, 4, 5, 6, -7, 8, 9] n = len(arr) rearrange(arr, n) printArray(arr, n) # Contributed by Afzal ``` ## C# ```cs // A C# program to put positive numbers // at even indexes (0, 2, 4, ..) and? // negative numbers at odd indexes (1, 3, 5, ..) using System; class Alternate { ????// The main function that rearranges elements? ????// of given array. It puts positive elements? ????// at even indexes (0, 2, ..) and negative? ????// numbers at odd indexes (1, 3, ..). ????static void rearrange(int[] arr, int n) ????{ ????????// The following few lines are similar to partition ????????// process of QuickSort. The idea is to consider 0 ????????// as pivot and divide the array around it. ????????int i = -1, temp = 0; ????????for (int j = 0; j < n; j++) { ????????????if (arr[j] < 0) { ????????????????i++; ????????????????temp = arr[i]; ????????????????arr[i] = arr[j]; ????????????????arr[j] = temp; ????????????} ????????} ????????// Now all positive numbers are at end? ????????// and negative numbers at the beginning of? ????????// array. Initialize indexes for starting point ????????// of positive and negative numbers to be swapped ????????int pos = i + 1, neg = 0; ????????// Increment the negative index by 2 and ????????// positive index by 1, i.e., swap every? ????????// alternate negative number with next positive number ????????while (pos < n && neg < pos && arr[neg] < 0) { ????????????temp = arr[neg]; ????????????arr[neg] = arr[pos]; ????????????arr[pos] = temp; ????????????pos++; ????????????neg += 2; ????????} ????} ????// A utility function to print an array ????static void printArray(int[] arr, int n) ????{ ????????for (int i = 0; i < n; i++) ????????????Console.Write(arr[i] + " "); ????} ????/*Driver function to check for above functions*/ ????public static void Main() ????{ ????????int[] arr = { -1, 2, -3, 4, 5, 6, -7, 8, 9 }; ????????int n = arr.Length; ????????rearrange(arr, n); ????????printArray(arr, n); ????} } // This code is contributed by vt_m. ``` ## PHP ```php <?php // A PHP program to put positive numbers?? // at even indexes (0, 2, 4,..) and negative? // numbers at odd indexes (1, 3, 5, ..)? // The main function that rearranges elements? // of given array. It puts positive elements? // at even indexes (0, 2, ..) and negative // numbers at odd indexes (1, 3, ..).? function rearrange(&$arr, $n)? {? ????// The following few lines are similar? ????// to partition process of QuickSort.? ????// The idea is to consider 0 as pivot? ????// and divide the array around it.? ????$i = -1;? ????for ($j = 0; $j < $n; $j++)? ????{? ????????if ($arr[$j] < 0)? ????????{? ????????????$i++;? ????????????swap($arr[$i], $arr[$j]);? ????????}? ????}? ????// Now all positive numbers are at end and? ????// negative numbers at the beginning of array.? ????// Initialize indexes for starting point of? ????// positive and negative numbers to be swapped? ????$pos = $i + 1; ????$neg = 0;? ????// Increment the negative index by 2 and? ????// positive index by 1, i.e., swap every? ????// alternate negative number with next ????// positive number? ????while ($pos < $n && $neg < $pos &&? ????????????????????????$arr[$neg] < 0)? ????{? ????????swap($arr[$neg], $arr[$pos]);? ????????$pos++;? ????????$neg += 2;? ????}? }? // A utility function to swap two elements? function swap(&$a, &$b)? {? ????$temp = $a;? ????$a = $b;? ????$b = $temp;? }? // A utility function to print an array? function printArray(&$arr, $n)? {? ????for ($i = 0; $i < $n; $i++)? ????????echo " " . $arr[$i] . " ";? }? // Driver Code $arr = array(-1, 2, -3, 4, 5, 6, -7, 8, 9);? $n = count($arr);? rearrange($arr, $n);? printArray($arr, $n);? // This code is contributed // by rathbhupendra ?> ``` **輸出**： ``` 4 -3 5 -1 6 -7 2 8 9 ``` **時間復雜度**：`O(n)`，其中`n`是給定數組中的元素數。 **輔助空間**： `O(1)` **相關文章**： [以恒定的額外空間重新排列正數和負數](https://www.geeksforgeeks.org/rearrange-positive-and-negative-numbers/) [將所有負數元素按順序移動到末尾，并留出額外的空間](https://www.geeksforgeeks.org/move-ve-elements-end-order-extra-space-allowed/) 本文由 **Abhay Rathi** 編寫。 如果發現任何不正確的地方，或者想分享有關上述主題的更多信息，請寫評論。