v2-ee773dffaae76cde8c7ec1fd86b49513_r.jpg
根据维基百科的定义：
插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。
堆排序也是将输入分为有序和无序两部分，迭代地从无序部分找出最大元素放入有序部分。它利用了大根堆的堆顶元素最大这一特征，使得在当前无序区中选取最大元素变得简单。
现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？
输入格式：
输入在第一行给出正整数 N (≤100)；随后一行给出原始序列的 N 个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。
输出格式：
首先在第 1 行中输出Insertion Sort表示插入排序、或Heap Sort表示堆排序；然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格。
v2-9538b827342a9354a66f467d663651ee_1440w.jpg
思路 ：
这道题通常能够想到的方法就是按部就班的来，先将序列进行插入排序，每次迭代都和中间序列进行比较，如果吻合就是插入排序，不吻合就是堆排序，然后再进行一次迭代。
我们不妨先将这种想法放到一边，仔细观察一下两种排序所产生的中间序列。由于堆排序利用了大根堆的堆顶元素最大这一特征，因此不难发现，堆排序所产生的中间序列 0 位置的元素总会比 1 位置的元素大。而在本题中插入排序是从前往后进行性迭代，逐步形成有序序列，所以 0 位置的元素会小于 1 位置的元素。
利用这个特点我们就可以抖一个小机灵，快速判断是用了插入排序还是堆排序，然后找到迭代进行到了哪一步，再往下进行一步就解决了。
下面看代码：
#include <stdio.h>
void swap(int *arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
void heapify(int *arr,int index,int size){
int left = index * 2 + 1;
while (left < size) {
int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
largest = arr[largest] > arr[index] ? largest : index;
if (largest == index) {
break;
}
swap(arr, largest, index);
index = largest;
left = index * 2 + 1;
}
}
int main(){
int n;
scanf("%d", &n);
int arr1[n];
int arr2[n];
for (int i = 0; i < n; ++i) {
scanf("%d", &arr1[i]);
}
for (int j = 0; j < n; ++j) {
scanf("%d", &arr2[j]);
}
if (arr2[0] > arr2[1]) {
//HeapSort
printf("Heap Sort\n");
int step=0;
for (int i = 1; i < n; ++i) {
if (arr2[0] < arr2[i]) {
step = i;
break;
}
}
int former = step-1;
int size = former;
swap(arr2, 0, former);
heapify(arr2, 0, size);
} else {
//Insertion sort
printf("Insertion Sort\n");
int step=0;
for (int i = 0; i < n; ++i) {
if (arr2[i] > arr2[i + 1]) {
step = i;
break;
}
}
for (int j = step; j >= 0 && arr2[j] > arr2[j + 1]; j--) {
swap(arr2, j, j + 1);
}
}
for (int k = 0; k < n-1; ++k) {
printf("%d ", arr2[k]);
}
printf("%d", arr2[n - 1]);
return 0;
}
v2-f0149510f1847ac29a0600649a276770_r.jpg
网友评论