YTU 2987: 調整表中元素順序（線性表）

2987: 調整表中元素順序（線性表）

時間限制: 1 Sec  

記憶體限制: 2 MB

送出: 1  

解決: 1

題目描述

若一個線性表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函數）

迷失在幽谷中的鳥兒，獨自飛翔在這偌大的天地間，卻不知自己該飛往何方……

算法部分：

void move(SqList *&L)
{
    for(int i=0,j=0; i<L->length; i++)
        if(L->data[i]<0)
        {
            for(int k=i; k>j; k--)
                swap(L->data[k],L->data[k-1]);
            j++;
        }
}      

完整代碼：

#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)
{
    for(int i=0,j=0; i<L->length; i++)
        if(L->data[i]<0)
        {
            for(int k=i; k>j; k--)
                swap(L->data[k],L->data[k-1]);
            j++;
        }
}
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;
}