C++程序在O(n)时间内并使用O(1)额外空间重新排列正负数

一个数组包含随机顺序的正数和负数。重新排列数组元素，以便正数和负数交替放置。正数和负数的数量不必相等。如果有更多的正数，它们出现在数组的末尾。如果有更多的负数，它们也出现在数组末尾。
例如，如果输入数组为[-1，2，-3，4，5，6，-7，8，9]，则输出应为[9，-7，8，-3，5，-1，2，4，6]。
注意： 分区过程会改变元素的相对顺序。即，此方法不维护元素出现的顺序。查看此处以保持元素出现顺序的解决方案。

解决方案是首先使用QuickSort的分区过程将正数和负数分开。在分区过程中，将0视为枢轴元素的值，以便将所有负数放在正数之前。一旦分离了负数和正数，我们从第一个负数和第一个正数开始，并交替交换每个负数和下一个正数。

        //一个C++程序将正数放置于偶数索引（0，2，4，..），
        //并将负数放置在奇数索引（1、3、5、..）。
        #include 
        using namespace std;

        class GFG
        {
            public:
            void rearrange(int [],int);
            void swap(int *,int *);
            void printArray(int [],int);
        };

        //重排给定数组元素的主要函数。将正
        //元素放在偶数索引（0,2，..）并将负数
        //数字在奇数索引（1,3，..）。
        void GFG :: rearrange(int arr[], int n)
        {
            //以下几行类似于QuickSort的分区过程。
            //思路是将0视为枢轴，将其周围的数组分开。
            int i = -1;
            for (int j = 0; j < n; j++)
            {
                if (arr[j] < 0)
                {
                    i++;
                    swap(&arr;[i], &arr;[j]);
                }
            }

            //现在所有的正数都在结尾，而负数在
            //开始式。初始化正数和负数的起始点的索引
            //需要交换
            int pos = i + 1, neg = 0;

            //将负数索引增加2而将正数索引增加1，
            //即交换每个负数索引的相邻的下一个正数
            while (pos < n && neg < pos && arr[neg] < 0)
            {
                swap(&arr;[neg], &arr;[pos]);
                pos++;
                neg += 2;
            }
        }

        //交换两个元素的实用程序函数
        void GFG :: swap(int *a, int *b)
        {
            int temp = *a;
            *a = *b;
            *b = temp;
        }

        //打印数组的实用程序函数
        void GFG :: printArray(int arr[], int n)
        {
            for (int i = 0; i < n; i++)
                cout << arr[i] << " ";
        }

        //驱动代码
        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;
        }

        //此代码是由vt_Yogesh Shukla 1贡献的