用机器学习过滤微博
卡特兰数

快速排序

scturtle posted @ 2012年2月21日 12:38 in algorithm , 1311 阅读
#include <cstdio>
#include <cstdlib>
#include <ctime>

void swap(int &x, int &y) { int t=x; x=y; y=t; }
void check(int t[],int n)
{
    bool res=true;
    for(int i=0;res && i<n-1;i++)
        if(t[i]>t[i+1])
            res=false;
    if(res)
        puts("Yes");
    else
    {
        puts("No");
        for(int i=0;i<n;i++)
            printf("%d ",t[i]);
        puts("");
    }
}

//////////////////////////////////////////////////////

int partation(int a[], int l, int r,int pi)
{
    swap(a[r],a[pi]);
    int p=a[r],here=l,j;
    for(j=l;j<r;j++)
        if(a[j]<p)
            swap(a[here++],a[j]);
    swap(a[here],a[r]);
    return here;
}

void qsort1(int a[], int l, int r)
{
    if(l>=r) return;
    int p=partation(a,l,r,(l+r)/2);
    qsort1(a,l,p-1);
    qsort1(a,p+1,r);
}

//////////////////////////////////////////////////////

void qsort2(int a[],int l,int r)
{
    if(l>=r) return;
    int p=a[l],i=l,j=r+1;
    while(1)
    {
        while(a[++i]<p);
        while(a[--j]>p);
        if(i>=j) break;
        swap(a[i],a[j]);
    }
    swap(a[j],a[l]);
    qsort2(a,l,j-1);
    qsort2(a,j+1,r);
}

//////////////////////////////////////////////////////

void qsort3(int a[],int l,int r)
{
    if(l>=r) return;
    int i=l-1,j=r+1,p=a[(l+r)/2];
    while(1)
    {
        while(a[++i]<p);
        while(a[--j]>p);
        if(i>j) break;
        swap(a[i],a[j]);
    }
    qsort3(a,l,j);
    qsort3(a,i,r);
}

//////////////////////////////////////////////////////

const int n=10000;
int t[n];

int main()
{
    freopen("out","w",stdout);
    srand(time(NULL));
    for(int i=0;i<n;i++)
        t[i]=1+rand()%1000;
    qsort3(t,0,n-1);
    check(t,n);
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter