Fork me on GitHub

PAT(甲级)渡劫(九)-Insertion or Heap Sort(25)


PAT(甲级)渡劫(九)-Insertion or Heap Sort(25)

题目大意:

题目就是给两个序列,第一个是排序前的,第二个是排序中的,判断它是采用插入排序还是堆排序,并且输出下一次操作后的序列。

  1. 插入排序的特点就是,前面是从小到大排列的,后面就与原序列相同。
  2. 堆排序的特点就是,后面是从小到大排列的最大的几个数p~n-1,前面第一位则是p-1。

  所以只要先按照插入排序的特点来判断是否为插入排序,接下来再进行操作就可以了,这里要手动写下最大堆的更新操作。

代码如下:

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
#include <iostream>
#include <cstdio>
using namespace std;

int heap[101] = {200};
int a[101],b[101]; // a保存原始序列,b保存排序中的序列

void Print(int a[],int n){
for(int i = 1 ; i <= n ; i++){
printf("%d",a[i]);
if(i != n) printf(" ");
}
}

void HeapAdjust(int heap[],int s,int e){
int temp = heap[s]; // 保存要调整的结点数据
int parent = s,child;
while(2*parent <= e){
child = 2*parent;
if(child != e && heap[child] < heap[child+1])
child++; // 在左右孩子中挑选最大的
if(temp > heap[child]) break; // 若当前结点大于左右孩子结点,则符合堆的定义,直接退出
else heap[parent] = heap[child]; // 否则当前结点被赋值
parent = child; // 遍历后序结点
}
heap[parent] = temp;
}

void CreatHeap(int heap[],int n){
int i = n/2;
while(i >= 1){
HeapAdjust(heap,i,n);
i--;
}
}

int main(){
//freopen("in.txt","r",stdin);
int n;
scanf("%d",&n);
for(int i = 1 ; i <= n ; i++){
scanf("%d",&a[i]);
heap[i] = a[i];
}
for(int i = 1 ; i <= n ; i++){
scanf("%d",&b[i]);
}

int index = 1;
while(index < n && b[index] <= b[index+1]) // 插入排序前面的序列按递增序列排列
index++;

int find = index+1; // 记录第一个不递增的位置
while(find <= n && b[find] == a[find]) // 插入排序后面的序列与原序列相同
find++;

if(find == n+1){
printf("Insertion Sort\n");
int e = b[index+1]; // 保存该值便于插入
while(index >= 1 && e <= b[index]){ // 找位置插入数字
b[index+1] = b[index];
index--;
}
b[index+1] = e;
Print(b,n);
}else{
printf("Heap Sort\n");
CreatHeap(heap,n);
int e;
index = n;
while((e = heap[1]) == b[index]){
heap[1] = heap[index];
heap[index--] = e;
HeapAdjust(heap,1,index); // index记录已经执行了多少次堆排序
}
heap[1] = heap[index]; // 再多执行一次堆排序
heap[index--] = e;
HeapAdjust(heap,1,index);
Print(heap,n);
}
return 0;
}

运行结果:

坚持原创技术分享,您的支持将鼓励我继续创作
-------------本文结束感谢您的阅读-------------
0%