浙江大学数据结构MOOC-课后习题-第九讲-排序1 排序

题目汇总
浙江大学数据结构MOOC-课后习题-拼题A-代码分享-2024

题目描述

冒泡排序

void buble_Sort()
{	
	int A[MAXSIZE];
	int N;

	std::cin >> N;
	for (int i = 0; i < N; i++)
		std::cin >> A[i];

	bool flag = false;
	int temp;
	for (int j = N - 1; j > 0; j--)
	{	
		flag = false;
		for (int i = 0; i < j; i++)
		{
			if (A[i] > A[i + 1])
			{
				temp = A[i];
				A[i] = A[i + 1];
				A[i + 1] = temp;
				flag = true;
			}
		}
		if (flag == false) break;
	}
	for (int i = 0; i < N; i++)
	{
		if (i == 0)
			std::cout << A[i];
		else
			std::cout << ' ' << A[i];
	}
	return;
}

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

插入排序

#include <iostream>
#define MAXSIZE 100000

void insertion_Sort()
{	
	/* 初始化 */
	int A[MAXSIZE];
	int N;
	std::cin >> N;
	for (int i = 0; i < N; i++)
		std::cin >> A[i];
	/* 算法 */
	int i, j, temp;
	for (i = 1; i < N; i++)
	{
		temp = A[i];	/* 摸牌 */
		for (j = i; j > 0 && A[j - 1] > temp; j--)
			A[j] = A[j - 1];
		A[j] = temp;
	}

	/* 打印 */
	for (int i = 0; i < N; i++)
	{
		if (i == 0)
			std::cout << A[i];
		else
			std::cout << ' ' << A[i];
	}

}

int main()
{	
	insertion_Sort();
	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 <iostream>

#define MAXSIZE 100000

void shell_Sort()
{	
	/* 初始化 */
	int A[MAXSIZE];
	int N;
	std::cin >> N;
	for (int i = 0; i < N; i++)
		std::cin >> A[i];
	
	/* 算法 */
		//Sedgewick序列
	int Sedgewick[] = { 929, 505, 209, 109, 41, 19, 5, 1, 0 };
	int i, j, Si, D, temp;
	/* 选取初始增量 */
	for (Si = 0; Sedgewick[Si] >= N; Si++);
	/* 开始排序 */
	for (D = Sedgewick[Si]; D > 0 ; D = Sedgewick[Si++])/* 增量变动 */
	{	
		/* 插入排序 */
		for (i = D; i < N; i++)/* 从第二堆中开始抽牌 */
		{
			temp = A[i];
			//for (j = i; j >= D && A[j - D] > temp; j -= D)

			for (j = i; j > D && A[j - D] > A[i]; j -= D)
			{
				A[j] = A[j - D];
			}
			A[j] = temp;
		}
	}
	/* 打印 */
	for (i = 0; i < N; i++)
	{
		if (i == 0)
			std::cout << A[i];
		else
			std::cout << ' ' << A[i];
	}

}

int main()
{	
	shell_Sort();
	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

堆排序

#include <iostream>
typedef int ElementType;
#define MAXSIZE 100000

void swap(int A[], int i, int j)
{
	int temp = A[i];
	A[i] = A[j];
	A[j] = temp;
}
void PercDown(int A[], int p, int N)
{/* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */
	int parent, child;
	int r = A[p]; /* 存放根节点的值 */

	for (parent = p; (parent * 2 + 1) < N; parent = child)
	{
		child = parent * 2 + 1;
		if (child != N - 1 && A[child] < A[child + 1])
			child++;	/* child指向左右孩子中较大者 */
		if (r >= A[child]) break;	/* 找到恰当的位置 */
		else A[parent] = A[child];	
	}
	/* 找到恰当的值，或者遍历完节点了 */
	A[parent] = r;
}


void heap_Sort()
{	
	/* 初始化 */
	int A[MAXSIZE];
	int N;
	std::cin >> N;
	for (int i = 0; i < N; i++)
		std::cin >> A[i];
	
	/* 算法 */
	//建立最大堆
	for(int i = N / 2; i >= 0; i--)
		PercDown(A, i, N);
	/* 删除最大堆堆顶 */
	for (int i = N - 1; i > 0; i--)
	{
		swap(A, 0, i);
		PercDown(A, 0, i);
	}
	/* 打印 */
	for (int i = 0; i < N; i++)
	{
		if (i == 0)
			std::cout << A[i];
		else
			std::cout << ' ' << A[i];
	}

}

int main()
{	
	heap_Sort();
	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

归并排序

#include <cstdlib>
#include <iostream>
typedef int ElementType;
#define MAXSIZE 100000

void Merge(int A[], int tempA[], int L, int R, int rightEnd)
{
	int leftEnd = R - 1;
	int length = rightEnd - L + 1;
	int i = L;
	while (L <= leftEnd && R <= rightEnd)
	{
		if (A[L] < A[R])
			tempA[i++] = A[L++];
		else
			tempA[i++] = A[R++];
	}
	while(L <= leftEnd)
		tempA[i++] = A[L++];
	while(R <= rightEnd)
		tempA[i++] = A[R++];
}

void Merge_pass(int A[], int tempA[], int N, int length)
{	
	int i = 0;
	for (i = 0; i <= N - 2 * length; i += 2 * length)
		Merge(A, tempA, i, i + length, i + 2 * length - 1);
	if (i + length < N)
		Merge(A, tempA, i, i + length, N - 1);
	else
	{
		for (; i < N; i++)
			tempA[i] = A[i];
	}
}


void Mergy_Sort()
{	
	/* 初始化 */
	int A[MAXSIZE];
	int N;
	std::cin >> N;
	for (int i = 0; i < N; i++)
		std::cin >> A[i];
	
	/* 算法 */
	int* tempA = (int*)malloc(N * sizeof(int));
	int length = 1;
	if (tempA != NULL)
	{
		while (length < N)
		{
			Merge_pass(A, tempA, N, length);
			length *= 2;
			Merge_pass(tempA, A, N, length);
			length *= 2;
		}
		free(tempA);
	}
	else std::cout << "ERROR";
	
	/* 打印 */
	for (int i = 0; i < N; i++)
	{
		if (i == 0)
			std::cout << A[i];
		else
			std::cout << ' ' << A[i];
	}

}

int main()
{	
	Mergy_Sort();
	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