問題 B: 調整表中元素順序（線性表）
時間限制: 1 Sec??內存限制: 2 MB提交: 28??解決: 11
[提交][狀態][討論版]
題目描述
若一個線性表L采用順序存儲結構存儲，其中所有元素都為整數。設計一個算法，將所有小于0的元素移到所有大于0的元素前面，要求算法的時間復雜度不超過O(nlog(n))，空間復雜度為O(1)。
??
順序表的定義為：
typedef struct
{
ElemType data[SizeMax];
int length;
} SqList;
需編寫的算法為：
void move(SqList *&L);
注意：只需提交你所編寫的算法即可
輸入
輸入的數據有兩行，第一行輸入線性表的長度n，第二行依次輸入n個元素。
輸出
輸出的數據占一行，為調整之后的線性表，每個元素中間用空格分隔。
樣例輸入
10
-12 25 -19 21 -18 -11 5 -18 9 -22 樣例輸出
-12 -19 -18 -11 -18 -22 25 21 5 9 提示
1、請選擇C++提交
2、注意調整后元素的順序
3、只需提交調整順序表元素的算法（move函數）
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define SizeMax 100000
using namespace std;
typedef int ElemType;
typedef struct
{ElemType data[SizeMax];int length;
} SqList;
void CreateList(SqList *&L,ElemType n)
{if(n>SizeMax)return;L=(SqList*)malloc(sizeof(SqList));for(int i=0; i<n; i++)scanf("%d",&L->data[i]);L->length=n;
}void move(SqList *&L)
{int n=L->length,a[10000],m;for(int i=0,j=0,r=0;i<n;i++){if(L->data[i]<0){L->data[j]=L->data[i];j++;}else{a[r]=L->data[i];r++;}m=j;}for(int i=m,r=0;i<n;i++){L->data[i]=a[r];r++;}}
void Print(SqList *L)
{for(int i=0; i<L->length; i++)printf(i!=L->length-1?"%d ":"%d\n",L->data[i]);
}
int main()
{SqList *L;ElemType n;scanf("%d",&n);CreateList(L,n);move(L);Print(L);free(L);return 0;
}
)
