NextDream

数据结构与算法导论 排序算法 C++描述

ELLIAS

Released at Jan 1, 2021
views

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

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;
}

堆排序

手写版:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int data[maxn];

inline void swift(int rt, int len) {
	register int pos=rt<<1;
	while (pos<=len) {
		if(pos<len && data[pos|1]<data[pos]) pos |= 1;
		if (data[rt]<data[pos]) return;
		swapp(data[rt], data[pos]);
		rt = pos, pos=rt<<1;
	}
}

signed main () {
	register int n = read();
	for (register int i=1; i<=n; ++ i) data[i]=read();
	for (register int i=n>>1; i; -- i) swift(i, n);
	for (register int i=n; i; -- i) {
		write(data[1]); pt(' '); swapp(data[1], data[i]); swift(1, i-1);
	} 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")

内容遵循 Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License.

本文永久链接：https://brynhild.online/DSaAi/

Updated at Jun 7, 2021

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, viewers 丨 Loading... Loading...
MOE ICP 辽ICP备20009666号-1 | MOE ICP MOEICP备20211096号