首页 > 代码库 > 使负数在正数之前,不改变原来的顺序

使负数在正数之前,不改变原来的顺序

 1 /* 2 不改变正负号序列,使得负数在正数前面,要求O(n),时间复杂度,O(1)空间复杂度 3 实际情况,很可能做不到,可以用类似快排partition的方法,但是不能保证有序了,保证有序的一个方法是用翻转,例如 4 2,3,4,-1,-2,3,-5,-6——————翻转为2,3,4,-1,-2,-5,-6,3-----翻转为-1,-2,-5,-6,2,3,4,3,最好情况可以为O(n),最坏为O(N2) 5 方法二,采用插入排序的思想,时间复杂度直接O(n2),方法三,空间换时间,按顺序扫描,是负数就放一个数组中,正数放另一个数组,然后重新 6 复制回去,O(n),空间也O(n) 7 */ 8 #include <iostream> 9 using namespace std;10 #include <string>11 12 /*13 方法一,采用区间翻转法,2,3,4,-1,-2,3,-5,-614 */15 16 void rotatefull(int *A ,int begin,int end)17 {18     while(begin<end)19     {20         swap(A[begin],A[end]);21         begin++;22         end--;23     }24 }25 void rotate(int * A,int begin,int part,int end)     //例如3,-5,-6,part=0,begin=0,end=226 {27     if(A==NULL)28         return;29     rotatefull(A,begin,part);30     rotatefull(A,part+1,end);31     rotatefull(A,begin,end);32 }33 34 void mainrotate(int *A,int begin,int end)35 {36     int i=end;                   //i递推往前探测37     int j=end;                   //j作为每次翻转的负数的尾。38     while(i>=0)39     {40         while(i>=0&&A[i]<0)41             i--;42         if(i<0)                        //全负数的情况43             return;44         int part=i;45         while(i>=0&&A[i]>0)46             i--;47         rotate(A,i+1,part,j);         //这里就算是i<0了也要翻转,因为i+1开始翻转48         j=j-(part-i);49     }50 }51 52 /*53  插入排序方法:O(n2),还有点意思,本来以为很容易,其实还是要动下脑子的54 */55 void mainrotate2(int *A,int n)56 {57     if(A==NULL)58         return;59     for(int i=1;i<n;i++)60     {61         int tmp=A[i];62         int j=i-1;63         while(tmp<0&&A[j]>0&&j>=0)64         {65             A[j+1]=A[j];66             j--;67         }68         A[j+1]=tmp;69     }70 }71 72 /*73 变成浮点数的方法,其实同样是把空间变大了,相当于空间换时间。74 思维比较巧妙,例如:3,4,-1,-3,5,2,-7,6,1  -------变成  -1.1,-2.3,-3.7   和   1.3,2.4,3.5,4.2,5.6,6.1,变很好变就是分别记录两个num_po和num_ne,然后就可以变了75 但是有很大的缺陷啊,比如要是12呢,怎么知道是除以10还是除以100,变成0.12啊,所以只是个想法,但可行性不高。76 */77 78 79 int main()80 {81     int A[]={1,7,-5,-6,9,-12,15};82     int n=7;83     mainrotate(A,0,n-1);84     //mainrotate2(A,n);85     for(int i=0;i<n;i++)86     {87         cout<<A[i]<<endl;88     }89     system("pause");90 }