「二叉搜索树 / set / 朝鲜树 / 替罪羊树」快速排序

#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define mod 1000000
#define pi acos(-1)
#define inf 0x7fffffff
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
vector<int> a;
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
    	int x=read();
    	a.push_back(x);
	}
    sort(a.begin(),a.end());
    for(vector<int>::iterator i=a.begin();i!=a.end();i++)
    	printf("%d ",*i);
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

#include<map>

#include<set>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define mod 1000000

#define pi acos(-1)

#define inf 0x7fffffff

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n;

vector<int> a;

int main()

{

n=read();

for(int i=1;i<=n;i++)

{

int x=read();

a.push_back(x);

}

sort(a.begin(),a.end());

for(vector<int>::iterator i=a.begin();i!=a.end();i++)

printf("%d ",*i);

return 0;

}

#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define mod 1000000
#define pi acos(-1)
#define inf 0x7fffffff
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
set<int>st;
int main()
{	
    n=read();
    for(int i=1;i<=n;i++)
    {
    	int x=read();
    	st.insert(x);
	}
	for(set<int>::iterator i=st.begin();i!=st.end();i++)
    	printf("%d ",*i);
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

#include<map>

#include<set>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define mod 1000000

#define pi acos(-1)

#define inf 0x7fffffff

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n;

set<int>st;

int main()

{

n=read();

for(int i=1;i<=n;i++)

{

int x=read();

st.insert(x);

}

for(set<int>::iterator i=st.begin();i!=st.end();i++)

printf("%d ",*i);

return 0;

}

#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define mod 1000000
#define pi acos(-1)
#define inf 0x7fffffff
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int rt,cnt;
int t,n,ans;
int v[200005],ls[200005],rs[200005];
bool tag[200005];
int insert(int &k,int x)
{
    if(!k)
    {
        k=++cnt;
        v[k]=x;
        return k;
    }
    if(x<v[k])insert(ls[k],x);
    else insert(rs[k],x);
    return k;
}
void dfs(int x)
{
    if(!x)return;
    dfs(ls[x]);
    printf("%d ",v[x]);
    dfs(rs[x]);
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        int x=read();
        insert(rt,x);
    }
    dfs(rt);
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

#include<map>

#include<set>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define mod 1000000

#define pi acos(-1)

#define inf 0x7fffffff

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int rt,cnt;

int t,n,ans;

int v[200005],ls[200005],rs[200005];

bool tag[200005];

int insert(int &k,int x)

{

if(!k)

{

k=++cnt;

v[k]=x;

return k;

}

if(x<v[k])insert(ls[k],x);

else insert(rs[k],x);

return k;

}

void dfs(int x)

{

if(!x)return;

dfs(ls[x]);

printf("%d ",v[x]);

dfs(rs[x]);

}

int main()

{

n=read();

for(int i=1;i<=n;i++)

{

int x=read();

insert(rt,x);

}

dfs(rt);

return 0;

}

#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define mod 1000000
#define pi acos(-1)
#define inf 0x7fffffff
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int rt,cnt;
int t,n,ans;
int v[200005],ls[200005],rs[200005];
bool tag[200005];
int insert(int &k,int x)
{
    if(!k)
    {
        k=++cnt;
        v[k]=x;
        return k;
    }
    if(x<v[k])insert(ls[k],x);
    else insert(rs[k],x);
    return k;
}
void dfs(int x)
{
    if(!x)return;
    dfs(ls[x]);
    printf("%d ",v[x]);
    dfs(rs[x]);
}
int a[200005];
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
		a[i]=read();
		swap(a[i],a[rand()%i+1]);
	}
    for(int i=1;i<=n;i++)
        insert(rt,a[i]);
    dfs(rt);
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

#include<map>

#include<set>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define mod 1000000

#define pi acos(-1)

#define inf 0x7fffffff

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int rt,cnt;

int t,n,ans;

int v[200005],ls[200005],rs[200005];

bool tag[200005];

int insert(int &k,int x)

{

if(!k)

{

k=++cnt;

v[k]=x;

return k;

}

if(x<v[k])insert(ls[k],x);

else insert(rs[k],x);

return k;

}

void dfs(int x)

{

if(!x)return;

dfs(ls[x]);

printf("%d ",v[x]);

dfs(rs[x]);

}

int a[200005];

int main()

{

n=read();

for(int i=1;i<=n;i++)

{

a[i]=read();

swap(a[i],a[rand()%i+1]);

}

for(int i=1;i<=n;i++)

insert(rt,a[i]);

dfs(rt);

return 0;

}

#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define mod 1000000
#define pi acos(-1)
#define inf 0x7fffffff
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
bool flag;
int rt,cnt;
int t,n,ans;
int v[200005],ls[200005],rs[200005];
int a[200005];
int insert(int &k,int x,int depth)
{
	if(depth>1000)flag=1;
    if(!k)
    {
        k=++cnt;
        v[k]=x;
        return k;
    }
    if(x<v[k])insert(ls[k],x,depth+1);
    else insert(rs[k],x,depth+1);
    return k;
}
void dfs(int x)
{
    if(!x)return;
    dfs(ls[x]);
    printf("%d ",v[x]);
    dfs(rs[x]);
}
void rebuild(int &k,int l,int r)
{
	if(l>r)return;
	int mid=(l+r)>>1;
	k=mid;
	v[k]=a[mid];
	rebuild(ls[k],l,mid-1);
	rebuild(rs[k],mid+1,r);
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
		a[i]=read();
    for(int i=1;i<=n;i++)
    {
        insert(rt,a[i],0);
        if(flag)
		{
			for(int j=1;j<=i;j++)ls[j]=rs[j]=v[j]=0;
			rebuild(rt,1,i);
			flag=0;
		}
	}
    dfs(rt);
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

#include<map>

#include<set>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define mod 1000000

#define pi acos(-1)

#define inf 0x7fffffff

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

bool flag;

int rt,cnt;

int t,n,ans;

int v[200005],ls[200005],rs[200005];

int a[200005];

int insert(int &k,int x,int depth)

{

if(depth>1000)flag=1;

if(!k)

{

k=++cnt;

v[k]=x;

return k;

}

if(x<v[k])insert(ls[k],x,depth+1);

else insert(rs[k],x,depth+1);

return k;

}

void dfs(int x)

{

if(!x)return;

dfs(ls[x]);

printf("%d ",v[x]);

dfs(rs[x]);

}

void rebuild(int &k,int l,int r)

{

if(l>r)return;

int mid=(l+r)>>1;

k=mid;

v[k]=a[mid];

rebuild(ls[k],l,mid-1);

rebuild(rs[k],mid+1,r);

}

int main()

{

n=read();

for(int i=1;i<=n;i++)

a[i]=read();

for(int i=1;i<=n;i++)

{

insert(rt,a[i],0);

if(flag)

{

for(int j=1;j<=i;j++)ls[j]=rs[j]=v[j]=0;

rebuild(rt,1,i);

flag=0;

}

dfs(rt);

return 0;

}

#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define mod 1000000
#define pi acos(-1)
#define inf 0x7fffffff
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int q[200005],top;
int id,rt,cnt;
int t,n,ans;
int v[200005],ls[200005],rs[200005],size[200005],fa[200005];
int insert(int &k,int x,int f)
{
    if(!k)
    {
        k=++cnt;
        size[k]=1;
        fa[k]=f;
        return k;
    }
    if(x<v[k])insert(ls[k],x,k);
    else insert(rs[k],x,k);
    if(max(size[ls[k]],size[rs[k]])>size[k]*0.7)id=k;
    size[k]=size[ls[k]]+size[rs[k]]+1;
    return k;
}
void build(int &k,int l,int r)
{
	if(l>r)return;
	int mid=(l+r)>>1;
	k=q[mid]; 
	build(ls[k],l,mid-1);
	build(rs[k],mid+1,r);
	fa[ls[k]]=fa[rs[k]]=k;
	size[k]=size[ls[k]]+size[rs[k]]+1;
}
void dfs(int x)
{
    if(!x)return;
    dfs(ls[x]);
    q[++top]=x;
    dfs(rs[x]);
}
void solve(int x)
{
	int pre=fa[x];
	dfs(x);
	for(int i=1;i<=top;i++)
		ls[q[i]]=rs[q[i]]=fa[q[i]]=size[q[i]]=0;
	if(!pre)build(rt,1,top);
	else if(ls[pre]==x)build(ls[pre],1,top);
	else build(rs[pre],1,top);
	fa[ls[pre]]=fa[rs[pre]]=pre;
	top=id=0;
}
int main()
{
    n=read();
    int num=0;
    for(int i=1;i<=n;i++)
    {
        v[i]=read();
        insert(rt,v[i],0);
        if(id)
			solve(id);
    }
    dfs(rt);
    for(int i=1;i<=n;i++)printf("%d ",v[q[i]]);
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

#include<map>

#include<set>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define mod 1000000

#define pi acos(-1)

#define inf 0x7fffffff

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int q[200005],top;

int id,rt,cnt;

int t,n,ans;

int v[200005],ls[200005],rs[200005],size[200005],fa[200005];

int insert(int &k,int x,int f)

{

if(!k)

{

k=++cnt;

size[k]=1;

fa[k]=f;

return k;

}

if(x<v[k])insert(ls[k],x,k);

else insert(rs[k],x,k);

if(max(size[ls[k]],size[rs[k]])>size[k]*0.7)id=k;

size[k]=size[ls[k]]+size[rs[k]]+1;

return k;

}

void build(int &k,int l,int r)

{

if(l>r)return;

int mid=(l+r)>>1;

k=q[mid];

build(ls[k],l,mid-1);

build(rs[k],mid+1,r);

fa[ls[k]]=fa[rs[k]]=k;

size[k]=size[ls[k]]+size[rs[k]]+1;

}

void dfs(int x)

{

if(!x)return;

dfs(ls[x]);

q[++top]=x;

dfs(rs[x]);

}

void solve(int x)

{

int pre=fa[x];

dfs(x);

for(int i=1;i<=top;i++)

ls[q[i]]=rs[q[i]]=fa[q[i]]=size[q[i]]=0;

if(!pre)build(rt,1,top);

else if(ls[pre]==x)build(ls[pre],1,top);

else build(rs[pre],1,top);

fa[ls[pre]]=fa[rs[pre]]=pre;

top=id=0;

}

int main()

{

n=read();

int num=0;

for(int i=1;i<=n;i++)

{

v[i]=read();

insert(rt,v[i],0);

if(id)

solve(id);

}

dfs(rt);

for(int i=1;i<=n;i++)printf("%d ",v[q[i]]);

return 0;

}

hzwer.com _ Home | http://hzwer.com

分类目录

热门文章

Myfriends

近期评论