北京邮电大学信息与通信工程学院

2020年数据结构与算法导论课实验题目C++描述

实验六 排序

实验目的

通过选择下面五个题目之一进行实现,掌握如下内容:

  1. 掌握各种排序算法的实现方法和算法优劣
  2. 学习使用排序算法解决实际问题的能力
  3. 举一反三,提升扩展现有排序技术优化解决方法

实验内容

题目1——基础实验

使用简单数组实现下面各种排序算法,并进行比较。

排序算法:

  1. 起泡排序
  2. 直接插入排序
  3. 简单选择排序
  4. 希尔排序
  5. 快速排序
  6. 堆排序
  7. 归并排序
  8. 计数排序
  9. 桶排序
  10. 基数排序

要求:

  1. 测试数据分成三类:正序、逆序、随机数据
  2. 对于这三类数据,比较上述排序算法中关键字的比较次数和移动次数(其中关键字交换计为3 次移动)
  3. 对于这三类数据,比较上述排序算法中不同算法的执行时间,精确到微秒
  4. 对2 和3 的结果进行分析,验证上述各种算法的时间复杂度

编写测试main()函数测试排序算法的正确性。

注意: 我写的都是从小到大排的.

冒泡排序

每次把最大的或最小的冒上去或者沉下来.

复杂度 $O(n^2)$, 在随机数据下比剩下俩$O(n^2)$的要快一点.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
signed main ()
{
register int n=readu(), tmpn=n-1, pos;
for (register int i=0; i^n; ++ i) data[i]=read();

register bool flag=true;
for (register int i=0; i^tmpn && flag; ++ i) {
flag = false, pos = tmpn-i;
for (register int j=0; j^pos; ++ j) {
if (data[j] > data[j+1]) {
swapp(data[j], data[j+1]); flag=true;
}
}
}

for (register int i=0; i^n; ++ i) write(data[i]), pt(' ');

return fwrite (but, 1, _p3-but, stdout), 0;
}

插入排序

维护一个有序列, 从无序列中依次挑元素插入到有序列中的相应位置.

复杂度 $O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
signed main ()
{
register int n=readu(), tmpn=n-1, pos, tmp;
for (register int i=0; i^n; ++ i) data[i]=read();

for (register int i=0; i^tmpn; ++ i) {
pos = i, tmp = data[i+1];
while (pos+1 && data[pos]>tmp) data[pos+1]=data[pos --];
data[pos+1] = tmp;
}

for (register int i=0; i^n; ++ i) write(data[i]), pt(' ');

return fwrite (but, 1, _p3-but, stdout), 0;
}

选择排序

维护一个有序列, 从无序列中选择元素依次加入到有序列的相应位置.

复杂度 $O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
signed main ()
{
register int n=readu(), tmpn=n-1, pos=0;
for (register int i=0; i^n; ++ i) data[i]=read();

for (register int i=0; i^tmpn; pos = ++ i) {
for (register int j=i+1; j^n; ++ j) {
pos = data[pos]<data[j]? pos:j;
} if (i^pos) swapp(data[i], data[pos]);
}

for (register int i=0; i^n; ++ i) write(data[i]), pt(' ');

return fwrite (but, 1, _p3-but, stdout), 0;
}

双向选择排序

常数小一点.

注意: 小心小区间内最大值和最小值是同一个.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
signed main ()
{
register int n=readu(), posl, posr;
register int l=0, r=n-1;
for (register int i=0; i^n; ++ i) data[i]=read();

while (l < r) {
posl = l, posr = r;
for (register int i=l; i<=r; ++ i) {
posl = data[posl]<data[i]? posl:i;
posr = data[posr]>data[i]? posr:i;
} posr = posr^l? posr:posl;
if (posl^l) swapp(data[posl], data[l]);
if (posr^r) swapp(data[posr], data[r]);
++l, -- r;
}

for (register int i=0; i^n; ++ i) write(data[i]), pt(' ');

return fwrite (but, 1, _p3-but, stdout), 0;
}

希尔排序

更快的插入排序

插入排序的最好情况: 序列已经有序, 理想复杂度为 $O(n)$. 故先使用一些手段使序列基本有序.

将序列分为不相连的若干子区间(设间隔为gap, 为了方便处理), 在子区间内进行插入排序, 接着逐渐缩小gap直到gap=1进行最后一次插入排序.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
signed main ()
{
register int n=readu(), tmpn=n-1, pos, tmp, grpcnt;
for (register int i=0; i^n; ++ i) data[i]=read();

register int gap=n>>1;
while (gap) {
grpcnt = n-gap;
for (register int i=0; i^grpcnt; ++ i) {
pos = i, tmp = data[i+gap];
while (pos>=0 && data[pos]>tmp) data[pos+gap]=data[pos], pos-=gap;
data[pos+gap] = tmp;
} gap >>= 1;
}

for (register int i=0; i^n; ++ i) write(data[i]), pt(' ');

return fwrite (but, 1, _p3-but, stdout), 0;
}

快速排序

通过一次排序将一个序列分为两部分, 其中一部分的数据都比另外一部分中的小, 然后对两个子序列继续进行快速排序.

复杂度 $O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
inline void qsort (register int L, register int R)
{
register int l=L, r=R, mid=data[(L+R)>>1];
while (l < r) {
while (data[l] < mid) ++ l;
while (data[r] > mid) -- r;
if (l <= r) swap(data[l ++], data[r --]);
}
if (l < R) qsort (l, R);
if (r > L) qsort (L, r);
}

signed main ()
{
register int n=readu();
for (register int i=0; i^n; ++ i) data[i]=read();

qsort (0, n-1);

for (register int i=0; i^n; ++ i) write(data[i]), pt(' ');

return fwrite (but, 1, _p3-but, stdout), 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
signed main ()
{
register int n=readu();
for (register int i=0; i^n; ++ i) data[i]=read();

register int l, r, mid;
pair<int, int> stp;
stack<pair<int, int> > s;
s.push(make_pair(0, n-1));

while (!s.empty()) {
stp = s.top (); s.pop ();
l=stp.first, r=stp.second, mid=data[(l+r)>>1];
while (l < r) {
while (data[l] < mid) ++ l;
while (data[r] > mid) -- r;
if (l <= r) swap(data[l ++], data[r --]);
}
if (l < stp.second) s.push (make_pair(l, stp.second));
if (r > stp.first ) s.push (make_pair(stp.first , r));
}

for (register int i=0; i^n; ++ i) write(data[i]), pt(' ');

return fwrite (but, 1, _p3-but, stdout), 0;
}

堆排序

懒得手写了(其实是不会), 遂用STL实现

1
2
3
4
5
6
7
8
9
10
11
12
signed main ()
{
register int n=readu();
register vector<int> vac;

for (register int i=0; i^n; ++ i) vac.push_back(read ());
make_heap (vac.begin(), vac.end());
sort_heap (vac.begin(), vac.end(), cmp);
for (register auto at=vac.begin(); at!=vac.end(); ++ at) {
write(*at), pt(' ');
} return fwrite (but, 1, _p3-but, stdout), 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
inline void merge (register int L, register int R)
{
register int mid=((L+R++)>>1)+1, l=L, r=mid, pos=L;
while (l^mid && r^R) tmp[pos ++] = data[l]<data[r]? data[l ++]:data[r ++];
while (l^mid) tmp[pos ++] = data[l ++];
while (r ^ R) tmp[pos ++] = data[r ++];
for (register int i=L; i^R; ++ i) data[i]=tmp[i];
}

inline void mergeSort (register int L, register int R)
{
if (!(L ^ R)) return;
if (!((R-L) ^ 1)) {
if (data[L]>data[R]) swapp(data[L], data[R]);
return;
} mergeSort(L, (L+R)>>1), mergeSort(((L+R)>>1)+1, R);
merge (L, R);
}

signed main ()
{
register int n=readu();
for (register int i=0; i^n; ++ i) data[i]=read();

mergeSort (0, n-1);

for (register int i=0; i^n; ++ i) write(data[i]), pt(' ');

return fwrite (but, 1, _p3-but, stdout), 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
inline void merge (register int L, register int mid, register int R)
{
register int l=L, r=mid, pos=L;
while (l^mid && r^R) tmp[pos ++] = data[l]<data[r]? data[l ++]:data[r ++];
while (l^mid) tmp[pos ++] = data[l ++];
while (r ^ R) tmp[pos ++] = data[r ++];
for (register int i=L; i^R; ++ i) data[i]=tmp[i];
}

signed main ()
{
register int n=readu();
for (register int i=0; i^n; ++ i) data[i]=read();

register int top, sst;
for (register int stp=1, pos=0; stp<n; stp<<=1, pos=0) {
sst = stp<<1, top = n - sst;
while (pos < top) merge(pos, pos+stp, pos+sst), pos += sst;
if (pos < n-stp) merge(pos, pos+stp, n);
}

for (register int i=0; i^n; ++ i) write(data[i]), pt(' ');

return fwrite (but, 1, _p3-but, stdout), 0;
}

计数排序&桶排序

1
2
3
4
5
6
7
8
9
10
signed main ()
{
register int n=readu();
register map<int, int> M;
for (register int i=0; i^n; ++ i) ++ M[read()];

for (register std::map<int,int>::iterator i=M.begin(); i!=M.end(); ++ i) {
while (i->second --) write(i->first), pt(' ');
} return fwrite (but, 1, _p3-but, stdout), 0;
}

桶排就不写了.

基数排序

提取每一个数的特定数位, 并按照数位比较, 维护末端有序.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
signed main ()
{
register int n=readu(), maxx=0;
for (register int i=0; i^n; ++ i) data[i]=read(), maxx=maxx>data[i]? maxx:data[i];

for (register int base=1; base<=maxx; base*=10) {
for (register int i=0; i^10; ++ i) cnt[i] = 0;
for (register int i=0; i^ n; ++ i) ++ cnt[dir[i]=(data[i]/base)%10];
for (register int i=1; i^10; ++ i) cnt[i] += cnt[i-1];
for (register int i=n-1; ~i; -- i) tmp[-- cnt[dir[i]]] = data[i];
for (register int i=0; i^ n; ++ i) data[i] = tmp[i];
}

for (register int i=0; i^n; ++ i) write(data[i]), pt(' ');

return fwrite (but, 1, _p3-but, stdout), 0;
}

松式基排

以$256$为底, 能塞进L1高速缓存.

CPU-Z

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
signed main () {
register int n=readu(), maxa=0;
register int data[maxn], tmpa[maxn], cnt[U]={0};
for (register int i=0; i^n; ++ i) data[i]=read(), maxa=data[i]>maxa? data[i]:maxa;

register int top = 1;
while (maxa >>= BIT) ++ top;

for (register int base=0; base^top; ++ base) {
for (register int i=0; i^U; ++ i) cnt[i] = 0;
for (register int i=0; i^n; ++ i) ++ cnt[getd(data[i], base)];
for (register int i=1; i^U; ++ i) cnt[i] += cnt[i-1];
for (register int i=n-1;~i; --i) tmpa[-- cnt[getd(data[i], base)]]=data[i];
for (register int i=0; i^n; ++ i) data[i] = tmpa[i];
}

for (register int i=0; i^n; ++ i) write(data[i]), pt(' ');

return fwrite (but, 1, _p3-but, stdout), 0;
}

BUG

如果写成如下形式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
signed main () {
register int n=readu(), maxa=0;
register int data[maxn], tmpa[maxn], cnt[U]={0};
for (register int i=0; i^n; ++ i) data[i]=read(), maxa=data[i]>maxa? data[i]:maxa;

for (register int base=0; maxa>>(BIT*base); ++ base) {
write(base), pt(' '), write(maxa>>(BIT*base)), pt('\n');
for (register int i=0; i^U; ++ i) cnt[i] = 0;
for (register int i=0; i^n; ++ i) ++ cnt[getd(data[i], base)];
for (register int i=1; i^U; ++ i) cnt[i] += cnt[i-1];
for (register int i=n-1;~i; --i) tmpa[-- cnt[getd(data[i], base)]]=data[i];
for (register int i=0; i^n; ++ i) data[i] = tmpa[i];
}

for (register int i=0; i^n; ++ i) write(data[i]), pt(' ');

return fwrite (but, 1, _p3-but, stdout), 0;
}

就会出现一些奇怪的状况导致循环无法结束.

例如:

输入数据

1
2
3
4
5
6
5
3264236
2346
23462346
2346
2346

输出数据为以下形式的循环:

1
2
3
4
410672 23462346
410673 91649
410674 358
410675 1

怀疑是由于右移次数过多导致. 目前原因不明, 有望大佬指点!

附录 常用模板

输入输出

fast IO

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
87
88
89
90
91
92
#pragma GCC optimize (2)
#pragma G++ optimize (2)
#pragma GCC optimize (3)
#pragma G++ optimize (3)
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse3","sse2","sse")
#pragma GCC target ("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target ("f16c")
#pragma G++ target ("sse3","sse2","sse")
#pragma G++ target ("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma G++ target ("f16c")

#include <cstdio>

using namespace std;

const int ELAS = 1<<14;
static char buf[ELAS],but[ELAS],*_p1=buf,*_p2=buf,*_p3=but,*_p4=but+ELAS;
static int bit[20];
#define gc() ((_p1==_p2)&&(_p2=(_p1=buf)+fread(buf,1,ELAS,stdin),_p1==_p2)?EOF:*_p1++)
inline void pt(char c) {
(_p3==_p4)?(fwrite(_p3=but, 1, ELAS, stdout), *_p3++=c):(*_p3++=c);
}
inline long long read () {
register long long x=0ll; register char c=gc(); register bool m=false;
while ((c < '0' || c > '9') && (c ^ '-')) c = gc();
if (!(c ^ '-')) c = gc(), m = true;
while (c>='0'&&c<='9') x = (x << 3) + (x << 1) + (c ^ '0'), c = gc();
return m? -x:x;
}
inline long long readu () {
register long long x=0ll; register char c=gc();
while (c < '0' || c > '9') c = gc();
while (c >='0' && c <='9') x = (x << 3) + (x << 1) + (c ^ '0'), c = gc();
return x;
}
inline long double readdou () {
register long double x=0.0; register char c=gc(); register bool m=false;
while ((c < '0' || c > '9') && (c ^ '-')) c = gc();
if (!(c ^ '-')) c = gc(), m = true;
while (c>='0'&&c<='9') x = x * 10.0 + (c ^ '0'), c = gc();
if (!(c ^ '.')) {
register long double s=0.1; c=gc();
while (c>='0' && c<='9') x = x + (c ^ '0') * s, s/=10.0, c=gc();
} return m? -x : x;
}
inline long double readudou () {
register long double x=0.0; register char c=gc();
while (c < '0' || c > '9') c = gc();
while (c>='0'&&c<='9') x = x * 10.0 + (c ^ '0'), c = gc();
if (!(c ^ '.')) {
register long double s=0.1; c=gc();
while (c>='0' && c<='9') x = x + (c ^ '0') * s, s/=10.0, c=gc();
} return x;
}
template <typename T>
inline void write (T x) {
if (!x) {pt('0'); return;}
register int pos=0;
if (x < 0) x = -x, pt ('-');
for (; x; x/=10) bit[++ pos] = x%10;
for (register int i=pos; i; --i) pt(bit[i]^'0');
}
inline long long qpow (long long a, long long t) {
register long long base = a, ret = 1ll;
while (t) {
if (t&1) ret = ret * base;
base = base * base, t >>= 1;
} return ret;
}
inline void writedou (long double x, int res=9) {
if (x == 0.0) {
pt('0'), pt('.');
for (register int i=0; i^res; ++i) pt ('0');
return;
} else {
if (x < 0.0) x=-x, pt('-');
register long long clf=qpow(10, res);
register long long flt=(long long)(x * clf) % clf;
write ((long long) x); pt ('.');
register int pos = 0;
for (; pos^res; flt/=10) bit[++ pos] = flt%10;
for (register int i=pos; i; --i) pt(bit[i]^'0');
}
}

signed main ()
{
//主程序代码内容
fwrite (but, 1, _p3-but, stdout);
return 0;
}

数据操作

swap

警告: 不能自己换自己

1
#define swapp(x, y) ((x)^=(y)^=(x)^=(y))

a * b % mo

1
2
3
4
5
inline long long mul_mod (register long long a,register long long b,register long long mo) {
register long long ret;
__asm__ __volatile__ ("\tmull %%ebx\n\tdivl %%ecx\n" : "=d"(ret):"a"(a),"b"(b),"c"(mo));
return ret;
}

编译指令

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
#pragma GCC optimize (2)
#pragma GCC optimize ("inline")
#pragma GCC optimize ("-fgcse")
#pragma GCC optimize ("-fgcse-lm")
#pragma GCC optimize ("-fipa-sra")
#pragma GCC optimize ("-ftree-pre")
#pragma GCC optimize ("-ftree-vrp")
#pragma GCC optimize ("-fpeephole2")
#pragma GCC optimize ("-ffast-math")
#pragma GCC optimize ("-fsched-spec")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("-falign-jumps")
#pragma GCC optimize ("-falign-loops")
#pragma GCC optimize ("-falign-labels")
#pragma GCC optimize ("-fdevirtualize")
#pragma GCC optimize ("-fcaller-saves")
#pragma GCC optimize ("-fcrossjumping")
#pragma GCC optimize ("-fthread-jumps")
#pragma GCC optimize ("-funroll-loops")
#pragma GCC optimize ("-freorder-blocks")
#pragma GCC optimize ("-fschedule-insns")
#pragma GCC optimize ("inline-functions")
#pragma GCC optimize ("-ftree-tail-merge")
#pragma GCC optimize ("-fschedule-insns2")
#pragma GCC optimize ("-fstrict-aliasing")
#pragma GCC optimize ("-falign-functions")
#pragma GCC optimize ("-fcse-follow-jumps")
#pragma GCC optimize ("-fsched-interblock")
#pragma GCC optimize ("-fpartial-inlining")
#pragma GCC optimize ("no-stack-protector")
#pragma GCC optimize ("-freorder-functions")
#pragma GCC optimize ("-findirect-inlining")
#pragma GCC optimize ("-fhoist-adjacent-loads")
#pragma GCC optimize ("-frerun-cse-after-loop")
#pragma GCC optimize ("inline-small-functions")
#pragma GCC optimize ("-finline-small-functions")
#pragma GCC optimize ("-ftree-switch-conversion")
#pragma GCC optimize ("-foptimize-sibling-calls")
#pragma GCC optimize ("-fexpensive-optimizations")
#pragma GCC optimize ("inline-functions-called-once")
#pragma GCC optimize ("-fdelete-null-pointer-checks")

#pragma GCC optimize ("Ofast", 3)
#pragma GCC target ("sse3","sse2","sse")
#pragma GCC target ("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target ("f16c")

代码分析

Comments

Please contact the Administrator directly for emergency.





GitHub release (latest by date including pre-releases) GitHub release (latest by date including pre-releases) GitHub repo size GitHub repo size PictureBed PictureBed

Blog content follows the Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License

Copyright 2017-2021 ELLIAS views, viewersLoading... Loading...
MOE ICP 辽ICP备20009666号-1 | MOE ICP MOEICP备20201096号