堆排还是插入
- 堆排(假设是小根堆)的时候后面是有序的,前面是一个堆,堆顶元素是当前未排序的最小的元素。每排序到一个就放到当前最后一位,因此最后得到的序列是倒序的
-
在这道题里面其使用的是大根堆进行排序,那么
down
操作要跟模板题的down
操作相反。 -
这道题想要判断是否为插入排序的话要搞清楚以下两点
-
插入排序进行 $k$ 次之后前 $k+1$ 个元素是有序的
- 插入排序时后面部分元素与原数列相同。
因此,做这道题的时候首先把前面有序的部分扫一遍,把 $p$ 指向第一个未排序的元素。 while (p <= n && after[p] >= after[p - 1]) p ++ ;
。然后把这个 p
记录下来,这就是插入的次数,然后 while (p <= n && origin[p] == after[p]) p ++ ;
把后面和原数列一样的元素扫一遍。如果可以扫到 n + 1
的位置,说明这个数列是原数列通过插入得到的。
- 插入排序的代码
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
int n;
int main()
{
int a[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
for (int i = 1; i < (sizeof a) / 4; i ++ )
{
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key)
{
a[j + 1] = a[j];
j -- ;
}
a[j + 1] = key;
}
for (int i = 0; i < 10; i ++ ) cout << a[i] << " ";
}
-
在判断出是插入排序之后只需要把
1~k+1
sort
一遍就可以。 -
完整代码如下
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = 110;
int n;
int origin[N], after[N];
int t[N];
void insert_sort(int times)
{
memcpy(t, origin, sizeof t);
int ct = 0;
for (int i = 2; i <= n; i ++ )
{
ct ++ ;
int key = t[i];
int j = i - 1;
while (j >= 1 && t[j] > key)
{
t[j + 1] = t[j];
j -- ;
}
t[j + 1] = key;
if (ct == times) break;
}
for (int i = 1; i <= n; i ++ ) cout << t[i] << " ";
}
void down(int u, int cnt)
{
int t = u;
if (u * 2 <= cnt && after[u * 2] > after[t]) t = u * 2;
if (u * 2 + 1 <= cnt && after[u * 2 + 1] > after[t]) t = u * 2 + 1;
if (t != u)
{
swap(after[t], after[u]);
down(t, cnt);
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> origin[i];
for (int i = 1; i <= n; i ++ ) cin >> after[i];
// 判断是否为插排不需要每次比较。
// 因为插排的前半部分是有序的,后半部分是与原来相同
// 的,因此只需要扫一遍,如果按照这个规则能扫到最后一位说明
// 是插排。
int p = 2;
while (p <= n && after[p] >= after[p - 1]) p ++ ;
int k = p; // 存放下插排的次数
while (p <= n && origin[p] == after[p]) p ++ ;
// 能扫到最后
if (p == n + 1)
{
cout << "Insertion Sort" << endl;
sort(after + 1, after + k + 1);
for (int i = 1; i < n; i ++ ) cout << after[i] << " ";
cout << after[n];
}
else
{
cout << "Heap Sort" << endl;
p = n;
while (after[1] <= after[p]) p -- ;
swap(after[1], after[p]); // 交换
down(1, p - 1); // p是size
for (int i = 1; i < n; i ++ ) cout << after[i] << " ";
cout << after[n];
}
return 0;
}