题目集总目录
学习指路博客数据结构学习笔记＜8＞排序、归并排序循环实现（存用）

# 09 - 排序 1 排序 (25 分)

本题链接

一个实验各种排序算法的平台，好好玩哈，然后去论坛晒结果 —— 实在不行可以看给出的参考代码。这是基本训练，一定要做

本题测试的各种排序算法的结果都在博客数据结构学习笔记＜8＞排序里边写了，这里仅给出插入排序的代码

# 代码

	#include <iostream>
	#include <cstdio>
	using namespace std;
	typedef long long ll;
	const int maxn = 100005;
	const int inf = 0x3f3f3f;
	int N;
	ll a[maxn];
	void Insertion_Sort(ll a[], int N) {
	for(int P = 1; P < N; P++) {
	ll t = a[P];// 摸下一张牌
	int i;
	for(i = P; i > 0 && a[i-1] > t; --i)
	a[i] = a[i-1]; // 移出空位直到前面那个这个元素小于当前元素
	a[i] = t; // 新牌落位
	}
	}
	int main(){
	scanf("%d", &N);
	for(int i = 0; i < N; ++i)
	scanf("%lld", &a[i]);
	Insertion_Sort(a, N);
	for(int i = 0; i < N; ++i)
	printf(" %lld"+!i, a[i]);
	return 0;
	}

# 测试点

在这里插入图片描述

# 09 - 排序 2 Insert or Merge (25 分)

本题链接

2014 年 PAT 冬季考试真题，供备考的同学练练手，选做；

# 题目大意

现在给出整数的初始序列，以及一个序列，这是一些排序方法的多次迭代的结果，你能分辨出我们使用的是哪种排序方法吗？（插入排序还是归并排序）

# 思路

初始序列存在两个数组里，先进行插入排序在每次，在每次迭代后判断序列是否相同，若相同则再做一次迭代后输出，若一直判断不相同则是归并排序。归并排序卡了半天，用递归版的不好处理，得用循环版的，循环版归并排序看这儿：归并排序循环实现（存用）

# 代码

	#include <iostream>
	#include <cstdio>
	#include <queue>
	using namespace std;
	typedef long long ll;
	const int maxn = 110;
	const int inf = 0x3f3f3f;
	int N;
	ll a[maxn],A[maxn],Copya[maxn];
	void swap(ll &a, ll &b){// 交换 a,b 的值
	int tmp = a;
	a = b;
	b = tmp;
	}
	bool isSame(ll a[], int N) {
	for(int i = 0; i < N; ++i)
	if(a[i] != A[i]) return false;
	return true;
	}
	void Merge(ll a[],ll tmp[], int s, int m, int e) {
	// 将数组 a 的局部 a [s,m-1] 和 a [m,e] 合并到数组 tmp, 并保证 tmp 有序
	int pb = s;
	int p1 = s, p2 = m;//p1 指向前一半 p2 指向后一半
	while (p1 <= m-1 && p2 <= e) {
	if (a[p1] <= a[p2])
	tmp[pb++] = a[p1++];
	else
	tmp[pb++] = a[p2++];
	}
	while(p1 <= m-1)
	tmp[pb++] = a[p1++];
	while(p2 <= e)
	tmp[pb++] = a[p2++];
	for (int i = 0; i < e-s+1; ++i)
	a[s+i] = tmp[i];
	}
	void Merge_Pass(ll a[], ll b[], int N, int len) {
	// 将 a 数组按 len 长度切分归并到 b
	//len 为当前有序子列的长度
	int i;
	for(i = 0; i <= N - 2len; i += 2len)
	// 找每一对要归并的子序列直到倒数第二对
	Merge(a, b, i, i+len, i+2*len-1); // 将 a
	if(i+len < N) // 最后有 2 个子列
	Merge(a, b, i, i+len, N-1);
	else // 最后只剩 1 个有序子列
	for(int j = i; j < N; ++j) b[j] = a[j];
	}
	void Merge_Sort(ll a[], int N) {
	bool flag = false;
	int len = 1;// 初始化有序子列的长度
	ll tmp[maxn];
	while(len < N) {
	Merge_Pass(a, tmp, N, len);
	len *= 2;
	if(isSame(tmp, N)) flag = true;
	else if(flag) return;
	Merge_Pass(tmp, a, N, len);
	len *= 2;
	if(isSame(a, N)) flag = true;
	else if(flag) return;
	}
	}
	bool Insertion_Sort(ll a[], int N) {
	bool flag = false;
	for(int P = 1; P < N; P++) {
	ll t = a[P];// 摸下一张牌
	int i;
	for(i = P; i > 0 && a[i-1] > t; --i)
	a[i] = a[i-1]; // 移出空位直到前面那个这个元素小于当前元素
	a[i] = t; // 新牌落位
	if(flag)
	return true;
	if(isSame(a, N)) {
	flag = true;
	continue;
	}
	}
	return false;
	}
	int main(){
	scanf("%d", &N);
	for(int i = 0; i < N; ++i) {
	scanf("%lld", &a[i]);
	Copya[i] = a[i];
	}
	for(int i = 0; i < N; ++i)
	scanf("%lld", &A[i]);
	if(Insertion_Sort(a, N)) {
	printf("Insertion Sort\n");
	} else {
	for(int i = 0; i < N; ++i)
	a[i] = Copya[i];
	Merge_Sort(a, N);
	printf("Merge Sort\n");
	}
	for(int i = 0; i < N; ++i) {
	printf(" %lld"+!i, a[i]);
	}
	return 0;
	}

# 测试点

在这里插入图片描述

# 09 - 排序 3 Insertion or Heap Sort (25 分)

本题链接

2015 年考研复试上机真题，供备考的同学练练手，选做。

# 题目大意

跟上题差不多，不过归并变成了堆排序

# 代码

	#include <iostream>
	#include <cstdio>
	#include <queue>
	using namespace std;
	typedef long long ll;
	const int maxn = 110;
	const int inf = 0x3f3f3f;
	int N;
	ll a[maxn],A[maxn],Copya[maxn];
	void swap(ll &a, ll &b){// 交换 a,b 的值
	int tmp = a;
	a = b;
	b = tmp;
	}
	bool isSame(ll a[], int N) {
	for(int i = 0; i < N; ++i)
	if(a[i] != A[i]) return false;
	return true;
	}
	void PercDown(ll a[], int N, int rt) {
	// 将 N 个元素的数组中以 a [now] 为根的子堆调整为最大堆
	int father, son;
	ll tmp = a[rt];
	for(father = rt; (father*2+1) < N; father = son) {
	son = father * 2 + 1;// 左儿子
	if(son != N-1 && a[son] < a[son+1]) // 右儿子存在且比左儿子大
	son++;
	if(tmp >= a[son]) break;// 找到该放的地方
	else a[father] = a[son];// 下滤
	}
	a[father] = tmp;
	}
	inline void BuildHeap(ll a[], int N) {
	for(int i = N/2-1; i >= 0; --i) {
	PercDown(a, N, i);
	}
	}
	void Heap_Sort(ll a[], int N) {
	bool flag = false;
	BuildHeap(a, N);
	for(int i = N-1; i > 0; --i) {
	swap(a[0], a[i]);// 最大堆顶 a [0] 与 a [i] 交换
	PercDown(a, i, 0);// 删除后进行调整
	if(flag) return;
	if(isSame(a,N)) flag = true;
	}
	}
	bool Insertion_Sort(ll a[], int N) {
	bool flag = false;
	for(int P = 1; P < N; P++) {
	ll t = a[P];// 摸下一张牌
	int i;
	for(i = P; i > 0 && a[i-1] > t; --i)
	a[i] = a[i-1]; // 移出空位直到前面那个这个元素小于当前元素
	a[i] = t; // 新牌落位
	if(flag)
	return true;
	if(isSame(a, N)) {
	flag = true;
	continue;
	}
	}
	return false;
	}
	int main(){
	scanf("%d", &N);
	for(int i = 0; i < N; ++i) {
	scanf("%lld", &a[i]);
	Copya[i] = a[i];
	}
	for(int i = 0; i < N; ++i)
	scanf("%lld", &A[i]);
	if(Insertion_Sort(a, N)) {
	printf("Insertion Sort\n");
	} else {
	for(int i = 0; i < N; ++i)
	a[i] = Copya[i];
	Heap_Sort(a, N);
	printf("Heap Sort\n");
	}
	for(int i = 0; i < N; ++i) {
	printf(" %lld"+!i, a[i]);
	}
	return 0;
	}

# 测试点

在这里插入图片描述

# 09 - 排序 1 排序 (25 分)

# 代码

# 测试点

# 09 - 排序 2 Insert or Merge (25 分)

# 题目大意

# 思路

# 代码

# 测试点

# 09 - 排序 3 Insertion or Heap Sort (25 分)

# 题目大意

# 代码

# 测试点

归并排序循环实现（存用）

PTA数据结构题目集 第十周——排序（下）

PTA数据结构题目集第十周——排序（下）