This article has been machine-translated from Chinese. The translation may contain inaccuracies or awkward phrasing. If in doubt, please refer to the original Chinese version.
Problem Set Master Index Study reference blogs: Data Structure Study Notes <8> Sorting, Iterative Implementation of Merge Sort (for reference)
09-Sort 1 Sorting (25 pts)
A platform for experimenting with various sorting algorithms. Have fun with it, then post your results in the forum — if you really can’t do it, you can look at the reference code provided. This is basic training, a must-do.
The results of various sorting algorithms tested in this problem are all written in the blog Data Structure Study Notes <8> Sorting. Here only the insertion sort code is provided.
Code
#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;
}Test Cases
09-Sort 2 Insert or Merge (25 pts)
2014 PAT Winter Exam real problem, for students preparing for the exam to practice. Optional.
Problem Summary
Given the initial sequence of integers and a sequence that is the result of several iterations of some sorting method, can you tell which sorting method we are using? (Insertion sort or merge sort)
Approach
Store the initial sequence in two arrays, then perform insertion sort. After each iteration, check if the sequence matches. If it matches, perform one more iteration and output. If it never matches, then it’s merge sort. Got stuck on merge sort for a long time — the recursive version is hard to handle, so the iterative version should be used. For the iterative merge sort, see: Iterative Implementation of Merge Sort (for reference)
Code
#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 - 2*len; i += 2*len)
//找每一对要归并的子序列 直到倒数第二对
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;
}Test Cases
09-Sort 3 Insertion or Heap Sort (25 pts)
2015 graduate school entrance exam real problem, for students preparing for the exam to practice. Optional.
Problem Summary
Similar to the previous problem, except merge sort is replaced with heap sort.
Code
#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;
}Test Cases
喜欢的话，留下你的评论吧～