浙江大学数据结构MOOC-课后习题-第九讲-排序2 Insert or Merge

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

题目描述

测试点

思路分析

刚开始我打算想推出一个规律，来判断是否是归并排序，但实在太过于复杂，我很难去想出这样的规律…因此，参考了其他博主的思路——每做一次排序就和给定的序列比较一次，这样的话只需要在现有的插入和归并算法上稍作添加即可，具体可参考insertion_Sort()和Merge_Sort()部分的代码

代码展示

/*
*	一遍遍执行插入排序或者归并排序
*   每次比较是否和给定的序列相同
*/
#include <cstdlib>
#include <iostream>
#define MAXSIZE 100
typedef int ElementType;

void print(int A[], int N)
{
	for (int i = 0; i < N; i++)
	{
		if (i == 0)
			std::cout << A[i];
		else
			std::cout << ' ' << A[i];
	}
}
bool isSame(int A[], int input[], int N)
{
	for (int i = 0; i < N; i++)
	{
		if (A[i] != input[i])
			return false;
	}
	return true;
}
bool insertion_Sort(int A[], int input[], int N)
{
	/* 算法 */
	int i, j, temp;
	bool flag = false;
	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;

		if (flag == true)
		{
			print(A, N);
			return true;;
		}
		if (isSame(A, input, N))
		{
			std::cout << "Insertion Sort" << std::endl;
			flag = true;
		}
	}
	return false;
}

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


bool Merge_Sort(int A[], int input[], int N)
{
	/* 算法 */
	int* tempA = (int*)malloc(N * sizeof(int));
	int length = 1;
	if (tempA != NULL)
	{
		while (length < N)
		{
			Merge_pass(A, tempA, N, length);
			length *= 2;
			if (isSame(tempA, input, N))
			{
				std::cout << "Merge Sort" << std::endl;
				Merge_pass(tempA, A, N, length);
				print(A, N);
				return true;
			}
			Merge_pass(tempA, A, N, length);
			length *= 2;
			if (isSame(A, input, N))
			{
				std::cout << "Merge Sort" << std::endl;
				Merge_pass(A, tempA, N, length);
				print(tempA, N);
				return true;
			}
		}
		free(tempA);
	}
	else std::cout << "ERROR";
	
	return false;
}


void check(int A[], int input[], int N)
{
	int copyA[MAXSIZE];
	for (int i = 0; i < N; i++)
		copyA[i] = A[i];
	if (Merge_Sort(copyA, input, N))
		return;
	else
	{
		for (int i = 0; i < N; i++)
			copyA[i] = A[i];
		insertion_Sort(copyA, input, N);
		return;
	}
}

int main()
{
	int A[MAXSIZE];
	int input[MAXSIZE];
	int N;

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

	check(A, input, N);
	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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

心路历程

从12号开始的数据结构学习，本来给自己定的DDL是27号，但是到28号早上9:13，我只完成了28道习题，还差9道
实在是高估了自己的实力，也低估了题目的难度，重新定个DDL吧——在30号中午前完成所有题，平均每天3道题，加油加油加油，学完这个就去学操作系统啦