2014-d-二-1

//本题要求时间最小，辅助空间最小，改自快排
void fun(int a[],int n)
{
    int i=0,j=n-1;//首尾坐标
    while(a[i]<0)++i;//找到首个待移动位置
    while(a[j]>0)--j;//最后一个待移动位置
    temp=a[i];
    while(i!=j)
    {
        while(j>i&&a[j]>0)--j;//找比0小的位置
        if(i<j)
        {
            a[i]=a[j];
            ++i;
        }
        while(i<j&&a[i]<0)++i;
        if(i<j)
        {
            a[j]=a[i];
            --j;
        }
    }
    a[i]=temp;
}

//其他算法，非最优
#include <iostream>
#include <stdlib.h>

using namespace std;

typedef struct Link
{
    int data;
    struct Link *next;
}Link;

/**
    算法思想：
            1.从头至尾扫描链表，找到第一个大于0的结点M
            2.继续扫描将小于0的结点插入到M前
**/
void sort(Link *&L)
{
    Link *p,*q,*r,*pre;
    p=L->next;//带头结点
    pre=L;
    //找到第一个正数
    while(p)
    {
        if(p->data>0) break;
        pre=p;//记录前驱结点
        p=p->next;
    }

    q=pre;//保留M的先前结点

    while(p)
    {
        if(p->data<0)
        {
            r=p;
            pre->next=p->next;//删除结点
            p=p->next;
            r->next=q->next;//将该结点插入到M前
            q->next=r;
        }else{
            pre=p;
            p=p->next;
        }
    }
}
/**
//用于测试
//打印链表
void print_link(Link *l)
{
    Link *p;
    p=l->next;
    while(p)
    {
        cout<<p->data<<endl;
        p=p->next;
    }
}

int main()
{

    //建立单链表
    Link *l,*s,*r;
    l=(Link *)malloc(sizeof(Link));
    l->next=NULL;
    r=l;

    s=(Link*)malloc(sizeof(Link));
    s->data=-1;
    s->next=NULL;
    r->next=s;
    r=s;

    s=(Link*)malloc(sizeof(Link));
    s->data=1;
    s->next=NULL;
    r->next=s;
    r=s;

    s=(Link*)malloc(sizeof(Link));
    s->data=-1;
    s->next=NULL;
    r->next=s;
    r=s;

    s=(Link*)malloc(sizeof(Link));
    s->data=-5;
    s->next=NULL;
    r->next=s;
    r=s;



    sort(l);
    print_link(l);
}
**/