According to Wikipedia:
Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
Heap sort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. it involves the use of a heap data structure rather than a linear-time search to find the maximum.
Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?
[编程题]1098. Insertion or Heap Sort (
- 热度指数：5245 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
输入描述:
Each input file contains one test case. For each case, the first line gives a positive integer N (<=100). Then in the next line, N integers are given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.
输出描述:
For each test case, print in the first line either "Insertion Sort" or "Heap Sort" to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resuling sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.
示例1
输入
10 3 1 2 8 7 5 9 4 6 0 1 2 3 7 8 5 9 4 6 0
输出
Insertion Sort 1 2 3 5 7 8 9 4 6 0
总体思路：
几个点：
1. 判断是插入排序还是堆排
2. 求下一状态
对于第1点，由于题中说了结果唯一，可以根据插入排序
已排序部分在前面为非递减顺序，未排序部分中间状态和起始状态相同。 所以如果是这样便是插入排序，否则为堆排
对于第2点， 如果是插入排序，根据排序区和未排序区的分界点向后接着排，跟中间状态不同就是下一状态。
如果是堆排，由于堆排的已排序部分在后面，从后向前找，找到未排序部分的最后一个元素的下标，进行一次 调整堆，就是下一状态。
代码如下：
#include <iostream> #include <vector> #include <algorithm> using namespace std; void HeapAdjust(vector<int>& numbers, int idx, int length); int main() { ios::sync_with_stdio(false); // 输入数据 int N; cin >> N; vector<int> firstState(N, 0); vector<int> midState(N, 0); for(int i=0; i<N; i++) { cin >> firstState[i]; } for(int i=0; i<N; i++) { cin >> midState[i]; } // 判断是哪种排序 int same = N-1; // 记录起始状态和中间状态尾部相同区域的第一元素的下标 while(same>=0 && midState[same]==firstState[same]) { same--; } bool isInsertion = true; for(int i=0; i<same; i++) { if(midState[i] > midState[i+1]) { isInsertion = false; break; } } // 求下一状态 vector<int> nextState = midState; if(isInsertion) { for(int i=same+1; i<N; i++) { sort(nextState.begin(), nextState.begin()+i); if(nextState != midState) { break; } } } else { // 找到堆排未排序区的最后一个元素的下标 int last = N-1; while(last>=0 && midState[last] >= midState[0]) { last--; } swap(nextState[0], nextState[last]); HeapAdjust(nextState, 0, last); } // 输出结果 if(isInsertion) { cout << "Insertion Sort" << endl; } else { cout << "Heap Sort" << endl; } for(int i=0; i<N-1; i++) { cout << nextState[i] << " "; } cout << nextState[N-1]; return 0; } void HeapAdjust(vector<int>& numbers, int idx, int length) { // 根结点的序号为0而不是1，所以i结点左孩子和右孩子分别为2i+1和2i+2 for(int i=2*idx+1; i<length; i=2*idx+1) { if(i+1<length && numbers[i]<numbers[i+1]) i++; if(numbers[idx] > numbers[i]) break; swap(numbers[idx], numbers[i]); idx = i; } }
发表于 2015-11-11 15:59:02
回复(1)
其实我想说c++ stl里面有建堆 调整堆之类的诶=。=居然好像没人用，是不是太作弊了一点（不过其实大家也用了sort swap之类的啦，也没差=。=），其实手动建堆也不是什么大事啦，附上我的AC代码供参考
#include<iostream>
#include<cstdio>
#include<cstdio>
#include<algorithm>
using namespace std;
int inse_arr[105],heap_arr[105],res_arr[105];
int n;
int equal_arr(int *a,int *b)//判断两个数组是否相等
{
for(int i=0;i<n;i++)
if(a[i]!=b[i])
return 0;
return 1;
}
void next_inse(int i)//下一个插排序列
{
for(int j=i;j>0&&inse_arr[j]<inse_arr[j-1];j--)
swap(inse_arr[j],inse_arr[j-1]);
}
void next_heap(int i)//下一个堆排序列
{
pop_heap(heap_arr,heap_arr+n-i+1);
push_heap(heap_arr,heap_arr+n-i);
}
void print_arr(int *a)//打印数组
{
printf("%d",a[0]);
for(int i=1;i<n;i++)
printf(" %d",a[i]);
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&inse_arr[i]);//输入插排和堆排
heap_arr[i]=inse_arr[i];
}
make_heap(heap_arr,heap_arr+n);//建堆
for(int i=0;i<n;i++)
scanf("%d",&res_arr[i]);
for(int i=1;i<n;i++)
{
next_inse(i);
if(equal_arr(inse_arr,res_arr))//判断下一个插排序列是否相等
{
printf("Insertion Sort\n");
next_inse(i+1);
print_arr(inse_arr);
return 0;
}
if(equal_arr(heap_arr,res_arr))//判断下一个堆排序列是否相等，放在这是不知道建堆算不算第一步
{
printf("Heap Sort\n");
next_heap(i);
print_arr(heap_arr);
return 0;
}
next_heap(i);
}
return 0;
}
编辑于 2019-01-16 16:29:36
回复(1)
//思路：直接暴力判断是否是Insertion Sort。是，再执行一次插入排序，不是再执行一次堆排序。
#include <bits/stdc++.h>
using namespace std;
int n,A[105],B[105];
vector<int> vec1,vec2,vec3;
void Heap_Adjust(){
int i=n;
for(;i>=1;--i)
if(B[1]>B[i]) break;
swap(B[1],B[i]);
int N=i-1,it=1;
while(2*it<=N){
int tmp=2*it;
if(2*it+1<=N){
if(B[2*it+1]>B[2*it]) tmp=2*it+1;
}
if(B[it]<B[tmp]) swap(B[it],B[tmp]),it=tmp;
else break;
}
}
int main(){
scanf("%d",&n);
for(int i=1,x;i<=n;++i)
scanf("%d",&x),A[i]=x,vec1.push_back(x);
for(int i=1,x;i<=n;++i)
scanf("%d",&x),B[i]=x,vec2.push_back(x);
int ok=0,k;
for(int i=1;i<=n;++i){
auto it=lower_bound(vec3.begin(),vec3.end(),A[i]);
vec3.insert(it,A[i]);
vector<int> tmp=vec3;
for(int j=i+1;j<=n;++j)
tmp.push_back(A[j]);
if(tmp==vec2){
ok=1;k=i+1;break;
}
}
if(ok){
printf("Insertion Sort\n");
auto it=lower_bound(vec3.begin(),vec3.end(),A[k]);
vec3.insert(it,A[k]);
vector<int> tmp=vec3;
for(int j=k+1;j<=n;++j)
tmp.push_back(A[j]);
for(int i=0;i<tmp.size();++i)
if(i==0) printf("%d",tmp[i]);
else printf(" %d",tmp[i]);
}else{
printf("Heap Sort\n");
Heap_Adjust();
for(int i=1;i<=n;++i)
if(i==1) printf("%d",B[i]);
else printf(" %d",B[i]);
}
return 0;
}
发表于 2018-03-04 15:31:53
回复(0)
#include <iostream>
using namespace std;
#define MAX 1000
int N, a[MAX], A[MAX], b[MAX];
bool identical(int* x, int* y) {
for (int i = 1; i <= N; ++i)
if (x[i] != y[i])return false;
return true;
}
bool insertSort() {
bool t = false;
for (int i = 2; i <= N; ++i) {
if (a[i - 1] > a[i]) {
a[0] = a[i];
int j = i - 1;
for (; j > 0 && a[0] < a[j]; --j)
a[j + 1] = a[j];
a[j + 1] = a[0];
}
if (identical(a, b)) t = true;
else if (t)break;
}
return t;
}
void percolateDown(int i, int& n) {
A[0] = A[i];
int j;
while (1 <= i && i <= n / 2) {
if (2 * i + 1 <= n)
j = (A[2 * i] >= A[2 * i + 1]) ? 2 * i : 2 * i + 1;
else j = 2 * i;
if (A[0] >= A[j])break;
else { A[i] = A[j]; i = j; }
}
A[i] = A[0];
}
bool heapSort() {
for (int i = N / 2; i >= 1; --i)percolateDown(i, N);
int tmp = N; bool t = false;
for (int i = N; i >= 2; --i) {
swap(A[i], A[1]);
percolateDown(1, --N);
if (identical(A, b)) t = true;
else if (t)break;
}
N = tmp; return t;
}
int main()
{
cin >> N; a[0] = b[0] = -1;
for (int i = 1; i <= N; ++i) { cin >> a[i]; A[i] = a[i]; }
for (int i = 1; i <= N; ++i)cin >> b[i];
if (insertSort()) {
cout << "Insertion Sort" << endl;
for (int i = 1; i <= N; ++i) {
cout << a[i]; if (i < N)cout << " ";
}
}
else if (heapSort()) {
cout << "Heap Sort" << endl;
for (int i = 1; i <= N; ++i) {
cout << A[i]; if (i < N)cout << " ";
}
}
}
发表于 2021-02-19 13:40:56
回复(1)
认真分析插入排序和堆排序的特点即可，
第一次用STL的堆操作，想不到这么好用。😘
#pragma warning(disable : 4996)
(1164)#include<iostream>
#include<vector>
(721)#include<algorithm>
#define ARRAY vector<int> //下标从0开始有效
using namespace std;
int main(){
int size;
//获取数据输入
cin >> size;
ARRAY before(size), after(size);
for (int i = 0; i < size; i++) {
cin >> before[i];
}
for (int i = 0; i < size; i++) {
cin >> after[i];
}
//判断是否插入排序
int sortIdx, sameIdx = size - 1;
for (sortIdx = 0; sortIdx + 1 < size && after[sortIdx] <= after[sortIdx + 1]; sortIdx++);
for (sameIdx = size - 1; sameIdx >= 0 && after[sameIdx] == before[sameIdx]; sameIdx--);
if (sortIdx == sameIdx){ //是插入排序
cout << "Insertion Sort" << endl;
sort(after.begin(), after.begin() + sortIdx + 2);
}
else{ //堆排序
sort(before.begin(), before.end());
for (sortIdx = size -1; sortIdx>=0 && after[sortIdx]==before[sortIdx]; sortIdx--);
make_heap(after.begin(), after.begin() + sortIdx +1 );
swap(after[0], after[sortIdx]);
make_heap(after.begin(), after.begin() + sortIdx);
cout << "Heap Sort" << endl;
}
//输出再迭代一轮后的数组
for (auto i = after.begin(); i < after.end(); i++){
cout << *i << (i + 1 == after.end() ? '\n' : ' ');
}
return 0;
}
发表于 2020-03-03 22:07:34
回复(0)
/*检查大顶堆性质判断是否为堆排序，是就找出末尾位置，调整一次，不是就插入排序来一次*/
#include <bits/stdc++.h>
using namespace std ;
const int AX = 1e2 + 66 ;
int a[AX] ;
int b[AX] ;
int n ;
void print(){
for( int i = 1 ; i <= n ; i++ ){
printf("%d",b[i]);
if( i < n ) printf(" ");
}
}
void adjust_heap( int len ){
int i = 1 ;
int temp = b[i] ;
for( int k = i * 2 ; k < len ; k *= 2 ){
if( k + 1 < len && b[k] < b[k+1] ) k ++ ;
if( b[k] > temp ){
b[i] = b[k];
i = k ;
}else break ;
}
b[i] = temp ;
}
int main(){
scanf("%d",&n);
for( int i = 1 ; i <= n ; i++ ){
scanf("%d",&a[i]);
}
for( int i = 1 ; i <= n ; i++ ){
scanf("%d",&b[i]);
}
int f = 1 ;
sort( a + 1 , a + n + 1 ) ;
int k = n ;
while( k > 0 && a[k] == b[k--] ) ; //找堆顶与每次调整后的末尾元素交换次数，即后几个元素排好序了
k ++ ;
for( int i = 1 ; i <= n ; i++ ){
int x = 2 * i ;
int y = x + 1 ;
if( ( x < k && b[i] < b[x] ) || ( y < k && b[i] < b[y] ) ){ // 检查大顶堆->升序
f = 0 ; break ;
}
}
if( f ){
printf("Heap Sort\n");
swap( b[1] , b[k] );
adjust_heap(k);
print();
}else{
printf("Insertion Sort\n");
for( int i = 2 ; i <= n ; i++ ){
if( b[i] < b[i-1] ){
while( i > 1 && b[i] < b[i-1] ){
swap( b[i] , b[i-1] );
i -- ;
}
break ;
}
}
print();
}
return 0 ;
}
发表于 2020-02-17 16:30:59
回复(0)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
void adjust(vector<int> &number, int start, int end)
{ if(start*2+1 > end) return ; int maxIndex = start*2+1; if(maxIndex+1 > end) { if(number[start] < number[maxIndex]) { swap(number[start], number[maxIndex]); adjust(number, maxIndex, end); } }else{ if(number[maxIndex+1] > number[maxIndex]) maxIndex = maxIndex + 1; if(number[start] < number[maxIndex]) { swap(number[start], number[maxIndex]); adjust(number, maxIndex, end); } }
}
void visited(vector<int> &number)
{ for(int i=0;i<number.size()-1;i++) cout<<number[i]<<" "; cout<<number.back();
}
int main()
{ int n; cin>>n; vector<int> number(n,0); vector<int> result(n,0); for(int i=0;i<n;i++) cin>>number[i]; for(int i=0;i<n;i++) cin>>result[i]; int index = 0; while(index<n && result[index]<=result[index+1]) index++; index++; int mid = index; while(index<n && result[index]==number[index]) index++; if(index==n) { cout<<"Insertion Sort"<<endl; sort(number.begin(), number.begin()+mid+1); visited(number); }else{ cout<<"Heap Sort"<<endl; index = n-1; while(result[index] > result[0]) index--; swap(result[0], result[index]); adjust(result, 0, index-1); visited(result); } return 0;
}
发表于 2018-02-14 15:54:31
回复(0)
/*
思路：
分别进行插入排序和堆排序，每排序一次和输入的结果进行比较，如果符合则再执行一步之后
跳出
*／
#include <iostream>
#include <algorithm>
using namespace std;
int B[1000];
bool Insertion_Sort(int a[],int n){
int Tmp,i;
bool done = false;
for(int p=2;p<=n;p++){
bool flag = true;
Tmp = a[p];
for( i = p;i>0&&a[i-1]>Tmp;i--){
a[i]=a[i-1];
}
a[i] = Tmp;
for(int i = 1;i<=n;i++){
if(a[i]!=B[i])
flag = false;
}
if(flag){
done = true;
continue;
}
if(done){
return true;
}
}
return false;
}
void sink(int a[],int i,int n){
int lc = 2*i;
int rc = lc + 1;
int mc = i;
if(i<=n/2){
if(lc<=n&&a[lc]>a[mc])
mc = lc;
if(rc<=n&&a[rc]>a[mc])
mc = rc;
}
if(mc!=i){
swap(a[i],a[mc]);
sink(a,mc,n);
}
}
bool Heap_Sort(int A[],int N){
//heapify
bool done = false;
for(int i = N/2;i>=1;i--)
sink(A,i,N);
for(int i = N;i>=1;i--){
bool flag = true;
swap(A[1],A[i]);
sink(A,1,i-1);
for(int j = 1;j<=N;j++){
if(A[j]!=B[j])
flag = false;
}
if(flag){
done = true;
continue;
}
if(done){
return true;
}
}
return false;
}
int main(){
int N;
cin>>N;
int A[101];
int A2[101];
for(int i = 1;i<=N;i++){
cin>>A[i];
A2[i]=A[i];
}
for(int i = 1;i<=N;i++){
cin>>B[i];
}
//Heap_Sort(A,N);
if(Insertion_Sort(A,N)){
cout<<"Insertion Sort"<<endl;
for(int i = 1;i<=N;i++){
cout<<A[i];
if(i!=N)
cout<<" ";
}
}
if(Heap_Sort(A2,N)){
cout<<"Heap Sort"<<endl;
for(int i = 1;i<=N;i++){
cout<<A2[i];
if(i!=N)
cout<<" ";
}
}
return 0;
}
编辑于 2016-12-02 11:57:51
回复(0)
#include <cmath>
#include <iostream>
using namespace std;
int init[101], cur[101], n;
void insert(int i) {
while (i > 1 && cur[i] < cur[i - 1]) {
swap(cur[i], cur[i - 1]);
i--;
}
}
void heap() {
int i = n;
while (i > 1 && cur[i] >= cur[1]) i--;
swap(cur[1], cur[i]);
int root = 1, son = root * 2;
while (son < i) {
if (son + 1 < i && cur[son + 1] > cur[son])
son = son + 1;
if (cur[son] > cur[root]) {
swap(cur[son], cur[root]);
root = son;
son = root * 2;
} else {
break;
}
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &init[i]);
for (int i = 1; i <= n; i++) scanf("%d", &cur[i]);
int k = 2;
while(k <= n && cur[k-1] <= cur[k]) k++;
int index = k;
while(k <= n && cur[k] == init[k]) k++;
if (k == n + 1) {
insert(index);
printf("Insertion Sort\n");
} else {
heap();
printf("Heap Sort\n");
}
for (int i = 1; i < n; i++) printf("%d ", cur[i]);
printf("%d", cur[n]);
return 0;
}
发表于 2023-04-05 10:40:52
回复(0)
#include<bits/stdc++.h>
using namespace std;
const int Max=110;
int ori[Max],tem[Max],change[Max];
int n;
bool same(int* a,int* b) {
for(int i=1; i<=n; i++) {
if(*(a+i)!=*(b+i)) {
return 0;
}
}
return 1;
}
void Printf(int* a) {
for(int i=1; i<=n; i++) {
printf("%d",*(a+i));
if(i<n) printf(" ");
}
printf("\n");
}
bool Insert() {
bool flag=0;
for(int i=2; i<=n; i++) {
if(i!=2&&same(tem,change)) {
flag=1;
}
sort(tem+1,tem+i+1);
if(flag) {
return 1;
}
}
return 0;
}
void down(int low,int high) {
int i=low,j=i*2;
while(j<=high) {
if(j+1<=high&&ori[j]<ori[j+1]) {
j=j+1;
}
if(ori[j]>ori[i]) {
swap(ori[j],ori[i]);
i=j;
j=i*2;
} else {
break;
}
}
}
void Heap() {
bool flag=0;
for(int i=n/2; i>=1; i--) {
down(i,n);
}
for(int i=n; i>1; i--) {
if(i!=n&&same(ori,change)) {
flag=1;
}
swap(ori[i],ori[1]);
down(1,i-1);
if(flag) {
Printf(ori);
return ;
}
}
}
int main() {
scanf("%d",&n);
for(int i=1; i<=n; i++) {
scanf("%d",&ori[i]);
tem[i]=ori[i];
}
for(int i=1; i<=n; i++) {
scanf("%d",&change[i]);
}
if(Insert()) {
printf("Insertion Sort\n");
Printf(tem);
} else {
printf("Heap Sort\n");
Heap();
}
return 0;
}
发表于 2022-11-27 23:02:00
回复(0)
更多PAT甲级题解尽在我的个人博客--acking-you.github.io
题目
题目大意
- 有很多题目实际不需要看懂题目，只需要看懂输入和输出，比如这题。
此题虽然题目较为学术，且比较长，实际总结下来就是，通过给你一个原数组序列，还有一个用插入排序或者是堆排序排了几轮的数组序列，你要根据这个序列判断所使用的排序方式，并且再以该排序方式往下排一轮。
解题代码拆解
这次由于我使用的接口化函数设计，也就是传入指针进行操作，没有采用全局变量，所以直接input操作写在main函数里面，省空间。
关键的判断函数
isInsert()
设计思路：假设为插入排序后的序列，通过一次循环，找到下一个要被排序的元素位置，按理来说，没有被排序的位置应该和原数组的序列情况一致，如果不一致，则不是插入排序。
//用于确定是否为插入排序，顺便返回此时待插入处理的位置
int isInsert(int* nums, int len) {
int i = 1;
for (; i < len; i++) {
if (nums[i - 1] > nums[i])
break;
}
for (int j = i; j < len; j++) {
if (original[j] != nums[j])
return -1;
}
return i;
} 堆排序和插入排序
插入排序
插入排序很简单，我这里直接写插入排序的每一轮处理函数来代替。
//插入排序的单步处理
void InsertSort(int* nums, int numSize, int i) {
int j = i;
int temp = nums[i];
for (; j > 0 && nums[j - 1] > temp; j--) {
nums[j] = nums[j - 1];
}
nums[j] = temp;
} 堆排序
对于一个完整的堆排序，分为两个过程：堆化+维持堆化。
建立大根堆，每次堆化找到最大值，为了位置堆的结构和排序，将堆顶与最后一个元素交换，然后更新对的范围到0~i-1再次堆化，又能找到这个堆中的最大值，长此以往，便完成了排序。
- 对于堆排序中的每一轮：堆排中的每一轮都是缩小堆的范围，并继续维持大根堆，在堆范围以外的元素就是被排好的元素。所以重点在于从后往前找到已经排到了哪个位置，再进行一次交换和堆化便可完成一轮排序。
用于固定范围堆化的函数：sift_down()
//堆化，得到大根堆
//对于从0开始编号的二叉堆:
/* iparent = (i-1)/2,
ilchild = i*2+1,
irchild = i*2+2 */
void sift_down(int arr[], int start, int end) { // 计算父结点和子结点的下标
int parent = start;
int child = parent * 2 + 1;
while (child <= end) { // 子结点下标在范围内才做比较
// 先比较两个子结点大小，选择最大的
if (child + 1 <= end && arr[child] < arr[child + 1]) child++;
// 如果父结点比子结点大，代表调整完毕，直接跳出函数
if (arr[parent] >= arr[child]) return;
else {
// 否则交换父子内容，子结点再和孙结点比较
swap(arr[parent], arr[child]);
parent = child;
child = parent * 2 + 1;
}
}
} 不断堆化得到最大值进行排序：heap_sort()
void heap_sort(int arr[], int len) {
// 从最后一个节点的父节点开始 sift down 以完成堆化 (heapify)
for (int i = (len - 1 - 1) / 2; i >= 0; i--)
sift_down(arr, i, len - 1);
// 先将第一个元素和已经排好的元素前一位做交换，再重新调整（刚调整的元素之前的元素），直到排序完毕
for (int i = len - 1; i > 0; i--) {
swap(arr[0], arr[i]);
sift_down(arr, 0, i - 1);
}
} 确定堆排序到哪个位置的函数：findP
//用于找出堆排已经拍到了哪个位置的最大值。
int findP(int* nums, int len) {
int i = 0;
for (; i < len; i++) {
int val = *max_element(nums, nums + len - i);
if (nums[len - 1 - i] != val)
break;
}
return len - 1 - i;
} 整合代码进行提交
效率还行！
#include <bits/stdc++.h>
using namespace std;
int* original = nullptr;
//插入排序的单步处理
void InsertSort(int* nums, int numSize, int i) {
int j = i;
int temp = nums[i];
for (; j > 0 && nums[j - 1] > temp; j--) {
nums[j] = nums[j - 1];
}
nums[j] = temp;
}
//堆排序
void sift_down(int arr[], int start, int end) { // 计算父结点和子结点的下标
int parent = start;
int child = parent * 2 + 1;
while (child <= end) { // 子结点下标在范围内才做比较
// 先比较两个子结点大小，选择最大的
if (child + 1 <= end && arr[child] < arr[child + 1]) child++;
// 如果父结点比子结点大，代表调整完毕，直接跳出函数
if (arr[parent] >= arr[child]) return;
else {
// 否则交换父子内容，子结点再和孙结点比较
swap(arr[parent], arr[child]);
parent = child;
child = parent * 2 + 1;
}
}
}
// void heap_sort(int arr[], int len) {
// // 从最后一个节点的父节点开始 sift down 以完成堆化 (heapify)
// for (int i = (len - 1 - 1) / 2; i >= 0; i--)
// sift_down(arr, i, len - 1);
// // 先将第一个元素和已经排好的元素前一位做交换，再重新调整（刚调整的元素之前的元素），直到排序完毕
// for (int i = len - 1; i > 0; i--) {
// swap(arr[0], arr[i]);
// sift_down(arr, 0, i - 1);
// }
// }
//用于找出堆排已经拍到了哪个位置的最大值。
int findP(int* nums, int len) {
int i = 0;
for (; i < len; i++) {
int val = *max_element(nums, nums + len - i);
if (nums[len - 1 - i] != val)
break;
}
return len - 1 - i;
}
//用于确定是否为插入排序，顺便返回此时待插入处理的位置
int isInsert(int* nums, int len) {
int i = 1;
for (; i < len; i++) {
if (nums[i - 1] > nums[i])
break;
}
for (int j = i; j < len; j++) {
if (original[j] != nums[j])
return -1;
}
return i;
}
//统一打印结果函数
void print(int* nums, int len) {
cout << nums[0];
for (int i = 1; i < len; i++) {
cout << ' ' << nums[i];
}
}
int main() {
//@输入处理
ios::sync_with_stdio(false);
int N;
cin >> N;
int org[N], nums[N];
for (int i = 0; i < N; ++i) {
cin >> org[i];
} for (int i = 0; i < N; ++i) {
cin >> nums[i];
}
//@根据不同的排序方式进行答案的打印
original = org;
int flag = isInsert(nums, N);
if (flag != -1) {
cout << "Insertion Sort" << endl;
InsertSort(nums, N, flag);
print(nums, N);
} else {
cout << "Heap Sort" << endl;
int pos = findP(nums, N);
swap(nums[0], nums[pos]);
sift_down(nums, 0, pos - 1);
print(nums, N);
}
return 0;
}
发表于 2021-09-21 00:50:48
回复(0)
#include<iostream>
#include<algorithm>
//知识点：堆排序，每次从前面的堆取出最大，放到已排好的序列里，再调整原堆
using namespace std;
int N, a[101],in[101];
bool check(int A[], int B[]) {//检查两数组相等，方便后续使用
int i;
for (i = 0; i < N; i++)if (A[i] != B[i])break;
return i == N;
}
int main() {
int i, j, k;
cin >> N;
for (i = 0; i < N; i++)cin >> in[i];
for (i = 0; i < N; i++)cin >> a[i];
for (i = 2; i <= N; i++) {
sort(in, in + i);
if (check(a, in)) {
sort(in, in + i+1);
if (check(a, in))continue;//如果下一轮不变，**重来**这是一个陷阱
cout << "Insertion Sort" << endl;
for (i = 0; i < N; i++) {
if (i)cout << ' ';
cout << in[i];
}
return 0;
}
}
cout << "Heap Sort"<<endl;
int temp[101];
for (i = 0; i < N; i++)temp[i] = a[i];
sort(temp, temp + N);
for (i = N - 1; i >= 0; i--)
if (temp[i] != a[i])break;//找到排完序的部分i+1~N-1
swap(a[0], a[i]);//当前a[0]是最大的，应放到a[i]的位置
//----------------------------------下面需要重新构建大顶堆---------------
for (j = 0; j < i;) {
k = 2 * j + 1; //先令k=左孩子
if (k >= i)break; //此时左子树出界
if (k + 1 < i && a[k + 1] > a[k])k++;//左孩子没出界，找到最大的孩子
if (a[k] < a[j])break; //已经结束
swap(a[j], a[k]); //没有结束，把当前节点和最大孩子交换
j = k; //迭代，令当前节点 = 交换后所处位置
}
for (i = 0; i < N; i++) {
if (i)cout << ' ';
cout << a[i];
}
return 0;
}
发表于 2021-02-25 22:17:57
回复(0)
堆排序的时候要构建堆，交换后，再调整过后再与输入中的比较，否则会找不到答案。可能这才叫一次iteration吧
判断是否与题目给出的序列相等要在迭代之前判断，因为可能初始序列就去给出的序列相同，如果迭代之后再判断就会找不到了。。
#include<iostream> #include<vector> #include<algorithm> using namespace std; vector<int>initialV; vector<int>middleV; vector<int>currentV; void InsertSort(int n) { bool flag = false; for (int i = 0; i < n; i++) { int temp = initialV[i]; for (int j = 0; j < i; j++) { if (initialV[j] > temp) { initialV.erase(initialV.begin() + i); initialV.insert(initialV.begin() + j, temp); if (flag) { for (int i = 0; i < initialV.size(); i++) { if (i == 0) { printf("%d", initialV[i]); } else { printf(" %d", initialV[i]); } } exit(0); } break; } } if (initialV == middleV && !flag) { cout << "Insertion Sort\n"; flag = true; } } } void buildHeap(int start, int n) { int it = start; while (2 * it + 1 < n) { int tmp = 2 * it + 1; if (2 * it + 2 < n) { if (initialV[2 * it + 1] < initialV[2 * it + 2]) tmp = 2 * it + 2; } if (initialV[it] < initialV[tmp]) { swap(initialV[it], initialV[tmp]); it = tmp; } else break; } } void HeapSort(int n) { bool flag = false; for (int k = n - 1; k >= 0; k--) { //先构建一个堆 buildHeap(k, n); //k为调整结点的最小下标 } for (int i = n - 1; i >= 0; i--) { if (initialV == middleV) { flag = true; cout << "Heap Sort\n"; } swap(initialV[0], initialV[i]); buildHeap(0, i); //将第一个与最后一个交换后，重新进行构建堆，此时需要调整第一个元素，因此只需调整一次。 if (flag) { for (int i = 0; i < initialV.size(); i++) { if (i == 0) { printf("%d", initialV[i]); } else { printf(" %d", initialV[i]); } } exit(0); } } } int main() { //freopen("C:Users47Desktop1.txt", "r", stdin); int n, m; cin >> n; int number = n; while (number--) { cin >> m; initialV.push_back(m); } number = n; while (number--) { cin >> m; middleV.push_back(m); } currentV = initialV; InsertSort(n); initialV = currentV; HeapSort(n); }
编辑于 2020-04-19 15:42:21
回复(0)
头疼，这里过了，PTA那里差第三个数据点，看了好几遍代码没看出有什么问题，又看不到数据，烦死了。
STL里有堆操作，有印象，查了一下api，不知道考试的时候有没有代码提示用。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void){
int N;
cin >> N;
vector<int> init(N), partial(N);
for(int i = 0; i < N; i++){
cin >> init[i];
}
for(int i = 0; i < N; i++){
cin >> partial[i];
}
vector<int> xs = init, ys = init;
auto check = [&](vector<int>& v){
for(int i = 0; i < N; i++){
if(v[i] != partial[i]) return false;
}
return true;
};
auto print = [=](vector<int>& ans){
for(int i = 0; i < N; i++){
if(i) cout << " ";
cout << ans[i];
}
cout << endl;
};
auto is_sorted = [](vector<int>& v){
int len = v.size();
for(int i = 0; i < len - 1; i++){
if(v[i] > v[i + 1]) return false;
}
return true;
};
int insert_cnt = 0;
auto insert_sort = [&](vector<int>& v){
if(is_sorted(v)) return;
int pivot = insert_cnt;
while(pivot > 0){
if(v[pivot] < v[pivot - 1]){
swap(v[pivot], v[pivot - 1]);
}
pivot--;
}
// print(v);
insert_cnt++;
};
int heap_cnt = 0;
make_heap(begin(ys), end(ys));
auto heap_sort = [&](vector<int>& v){
if(is_sorted(v)) return;
pop_heap(begin(v), end(v) - heap_cnt);
// print(v);
heap_cnt++;
};
int which = -1;
while(true){
bool check_xs = check(xs);
bool check_ys = check(ys);
if(check_xs && !check_ys){
which = 1;
break;
}
if(!check_xs && check_ys){
which = 2;
break;
}
insert_sort(xs);
heap_sort(ys);
}
// while(!is_sorted(xs)){
// insert_sort(xs);
// if(check(xs)){
// which = 1;
// break;
// }
// }
// while(!is_sorted(ys)){
// heap_sort(ys);
// if(check(ys)){
// which = 2;
// break;
// }
// }
if(which == 1){
cout << "Insertion Sort" << endl;
insert_sort(xs);
print(xs);
}
else if(which == 2){
cout << "Heap Sort" << endl;
heap_sort(ys);
print(ys);
}
else{
cout << "Unexpected result" << endl;
}
}
发表于 2019-08-23 00:34:19
回复(0)
我太傻了！！！没看清楚题意 以为就是简单的堆排序和插入排序。。。没想到居然还有迭代。。。佛了
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100;
int A[maxn],B[maxn],C[maxn],D[maxn];
int n;
int flag,flag1;
int k = 0,l = 0;
void insertSort(){
int i;
for( i = 2;i <=n;i++){
int temp = A[i];
int j = i;
while(j > 1 && temp < A[j - 1]){
A[j] = A[j - 1];
j--;
}
A[j] = temp;
flag = 0;
for(int j = 1;j <= n;j++){
if(A[j] != B[j]){
flag = 1;
k = i;
break;
}
}if(flag == 0){
i++;
temp = A[i];
j = i;
while(j > 1 && temp < A[j - 1]){
A[j] = A[j - 1];
j--;
}A[j] = temp;
break;
}
}
}
void downAdjust(int low,int high){
int num = 0;
int i = low,j = i * 2;
while(j <= high){
if(j + 1 <= high && D[j + 1] > D[j]){
j = j + 1;
}
if(D[j] > D[i]){
int temp = D[j];
D[j] = D[i];
D[i] = temp;
i = j;
j = i * 2;
}else break;
}
}
void createHeap(){
for(int i = n / 2;i >= 1;i--){
downAdjust(i,n);
}
}
void heapSort(){
int i;
createHeap();
for(int i = n;i > 1;i--){
int temp = D[i];
D[i] = D[1];
D[1] = temp;
downAdjust(1,i - 1);
flag1 = 0;
for( int j = 1;j <= n;j++){
if(D[j] != B[j]){
flag1 = 1;
break;
}
}
if(flag1 == 0){
i--;
temp = D[i];
D[i] = D[1];
D[1] = temp;
downAdjust(1,i - 1);
break;
}
}
}
int main(){
cin >> n;
for(int i = 1;i <= n;i++){
cin >> A[i];
D[i] = A[i];
}
for(int i = 1;i <= n;i++){
cin >> B[i];
}
insertSort();
heapSort();
if(flag == 0 ){
cout << "Insertion Sort" << endl;
for(int i = 1;i <= n;i++){
if(i != n)cout << A[i] << " ";
else cout << A[i] << endl;
}
}
if(flag1 == 0){
cout << "Heap Sort" << endl;
for(int i = 1;i <= n;i++){
if(i!= n)cout << D[i] << " ";
else cout << D[i] << endl;
}
}
return 0;
}
发表于 2019-08-22 21:30:59
回复(0)
思想：要找准中间状态下已排序部分和未排序部分的分界点，然后根据插入排序和堆排序的各自排序特性去判断。
#include<iostream>
#include<iostream>
#include<algorithm>
using namespace std;
//堆调整函数
void HeapAdjust(intarr[], intstart, intend) {
intdad = start;
intson = dad * 2+ 1; //左孩子节点
while(son <= end) {
if(son + 1<= end && arr[son + 1] > arr[son]) //存在右子节点
son++;
if(arr[dad] >= arr[son]) //父节点大于最大的孩子节点,调整完毕，直接跳出函数
break;
else{
swap(arr[dad], arr[son]);
dad = son;
son = dad * 2+ 1;
}
}
}
int main() {
inti,n,j,index=0,a[100],b[100];
bool flag = true; //默认插入排序
cin >> n;
for(i = 0; i < n; i++)
cin >> a[i];
for(i = 0; i < n; i++)
cin >> b[i];
for(i = 0; i < n-1; i++) {
if(b[i] > b[i+1]) {
index = i + 1; //插入排序下一步要插入的元素的索引
break;
}
}
for(int i = index; i < n; i++) {
if(a[i] != b[i]) {
flag = false; //不是插入排序
break;
}
}
if(flag) { //插入排序
cout << "Insertion Sort"<< endl;
intkey = b[index];
j = index - 1;
while(j >= 0&& b[j] > key) {
b[j + 1] = b[j];
j--;
}
b[j + 1] = key;
for(i = 0; i < n - 1; i++)
cout << b[i] << ' ';
cout << b[n - 1] << endl;
}
if(!flag) { //堆排序
cout << "Heap Sort"<< endl;
for(i = n - 1; i >= 0; i--) {
if(b[i] < b[0]) {
index = i;
break;
}
}
swap(b[0], b[index]);
HeapAdjust(b, 0, index-1);
for(i = 0; i < n - 1; i++)
cout << b[i] << ' ';
cout << b[n - 1] << endl;
}
}
发表于 2019-07-06 20:15:53
回复(0)
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int N;
int IsInsertion( int raw[], int nw[] ) { //插入排序的规律是：有序部分从小到大排列，待排序部分和原数组
int idx = 2, p; //的值一一对应
while( idx <= N && nw[idx - 1] <= nw[idx] ) {
idx++;
}
p = idx;
while( idx <= N && nw[idx] == raw[idx] ) {
idx++;
}
if( idx > N ) return p;
return 0;
}
void Next_Insertion( int nw[], int end ) {
int i = end - 1;
nw[0] = nw[end];
for(; nw[0] < nw[i]; i--) {
nw[i+1] = nw[i];
}
nw[i+1] = nw[0];
return;
}
void Next_Heap( int nw[], int end ) {
nw[0] = nw[end];
nw[end] = nw[1];
nw[1] = nw[0];//大顶堆的首项与末尾交换
int i = 1, j = 2 * i;
int head = nw[i];
for(;j <= end - 1; j = 2 * j) {//索引下沉的方式依照二叉树的结构
if(j < end - 1 && nw[j] < nw[j + 1]) j += 1;// j 表示数值较大项的索引
if(head > nw[j]) break; // 不符合下沉条件，直接退出
nw[i] = nw[j]; //较大的元素上浮
i = j; //i指向孩子，等待下一轮的操作
}
nw[i] = head;//大顶堆的首项最终降落在适合的位置
}
int main() {
scanf("%d", &N);
int *raw = (int *)calloc(sizeof(int), (N+1));
int *a = (int *)calloc(sizeof(int), (N+1));//动态数组
raw[0] = 0;
a[0] = 0;
for(int i = 1; i <= N; i++) {
scanf("%d", raw + i);
}
for(int i = 1; i <= N; i++) {
scanf("%d", a + i);
}
int p = IsInsertion(raw, a);//判断是否是插入排序
if(p) {
printf("Insertion Sort\n");
Next_Insertion(a, p);//执行下一步插入排序
}
else {
printf("Heap Sort\n");
int idx = N;
while( idx > 2 && a[idx] >= a[1] ) {idx--;}
Next_Heap(a, idx);//执行下一步堆排序操作
}
for(int i = 1; i <= N; i++) {
cout<<a[i]<<" ";
}
return 0;
}
#include <iostream>
#include <algorithm>
using namespace std;
int N;
int IsInsertion( int raw[], int nw[] ) { //插入排序的规律是：有序部分从小到大排列，待排序部分和原数组
int idx = 2, p; //的值一一对应
while( idx <= N && nw[idx - 1] <= nw[idx] ) {
idx++;
}
p = idx;
while( idx <= N && nw[idx] == raw[idx] ) {
idx++;
}
if( idx > N ) return p;
return 0;
}
void Next_Insertion( int nw[], int end ) {
int i = end - 1;
nw[0] = nw[end];
for(; nw[0] < nw[i]; i--) {
nw[i+1] = nw[i];
}
nw[i+1] = nw[0];
return;
}
void Next_Heap( int nw[], int end ) {
nw[0] = nw[end];
nw[end] = nw[1];
nw[1] = nw[0];//大顶堆的首项与末尾交换
int i = 1, j = 2 * i;
int head = nw[i];
for(;j <= end - 1; j = 2 * j) {//索引下沉的方式依照二叉树的结构
if(j < end - 1 && nw[j] < nw[j + 1]) j += 1;// j 表示数值较大项的索引
if(head > nw[j]) break; // 不符合下沉条件，直接退出
nw[i] = nw[j]; //较大的元素上浮
i = j; //i指向孩子，等待下一轮的操作
}
nw[i] = head;//大顶堆的首项最终降落在适合的位置
}
int main() {
scanf("%d", &N);
int *raw = (int *)calloc(sizeof(int), (N+1));
int *a = (int *)calloc(sizeof(int), (N+1));//动态数组
raw[0] = 0;
a[0] = 0;
for(int i = 1; i <= N; i++) {
scanf("%d", raw + i);
}
for(int i = 1; i <= N; i++) {
scanf("%d", a + i);
}
int p = IsInsertion(raw, a);//判断是否是插入排序
if(p) {
printf("Insertion Sort\n");
Next_Insertion(a, p);//执行下一步插入排序
}
else {
printf("Heap Sort\n");
int idx = N;
while( idx > 2 && a[idx] >= a[1] ) {idx--;}
Next_Heap(a, idx);//执行下一步堆排序操作
}
for(int i = 1; i <= N; i++) {
cout<<a[i]<<" ";
}
return 0;
}
发表于 2019-03-15 16:57:53
回复(0)
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string>
#include<vector>
#include<unordered_map>
using namespace std;
int a[105], c[105], num;
vector<int> v;
void insert_sort(int n)
{// printf("m=%d",n);
int tmp = a[n + 1], i;
for (i = 1; i <= num; i++)
v.push_back(a[i]);
for (i = 1; i <= n; i++)
if (a[i] > tmp)
break;
v.erase(v.begin() + n);
v.insert(v.begin() + i - 1, tmp);
}
void heap_sort(int low, int high)
{
int i = low, j = i * 2, tmp = a[i];
while (j <= high)
{
if (j < high&&a[j] < a[j + 1])
j++;
if (tmp < a[j])
{
a[i] = a[j];
i = j;
j = 2 * i;
}
else
break;
}
a[i] = tmp;
}
int main()
{
scanf("%d", &num);
int i;
for (i = 1; i <= num; i++)
scanf("%d", &c[i]);
for (i = 1; i <= num; i++)
scanf("%d", &a[i]);
for (i = num; i >= 1; i--)
if (a[i] != c[i])
break;
sort(c + 1, c + 1 + i);
bool flag = true;
for (int k = 1; k <= i; k++)
if (a[k] != c[k])
{
flag = false;
break;
}
if (!flag)
{
printf("Heap Sort\n");
int j, tmp;
sort(c + 1, c + 1 + num);
for (j = num; j >= 1; j--)
if (a[j] != c[j])
break;
tmp = a[1];
a[1] = a[j];
a[j] = tmp;
heap_sort(1, j - 1);
for (int i = 1; i <= num; i++)
{
if (i != 1)
printf(" ");
printf("%d", a[i]);
}
}
else
{
printf("Insertion Sort\n");
insert_sort(i);
for (int i = 0; i < num; i++)
{
if (i != 0)
printf(" ");
printf("%d", v[i]);
}
}
}
编辑于 2019-02-15 13:48:38
回复(0)
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=110;
int n,key,index,flag=0;
int origin[maxn],temp[maxn],ans[maxn];
bool isSame(int a[],int b[]){ //判断两数组是否相同
for(int i=1;i<=n;i++){
if(a[i]!=b[i]) return false;
}
return true;
}
void print(int a[]){ //输出数组
for(int i=1;i<=n;i++){
if(i!=n) cout<<a[i]<<" ";
else cout<<a[i]<<endl;
}
}
void downAdjust(int low,int high){ //大根堆向下调整
int i=low,j=i*2; //j为i左子女
while(j<=high){ //存在子女(i为非叶结点时）
if(j+1<=high&&temp[j+1]>temp[j]) j=j+1; //两子女中选出大者
if(temp[j]>temp[i]){
swap(temp[j],temp[i]); //交换父结点与较大的子结点
i=j;
j=i*2;
}
else break; //子结点均比夫结点小，不用继续调整
}
}
void heapSort(){
for(int i=n/2;i>=1;i--) //建堆
downAdjust(i,n);
for(int i=n;i>1;i--){
if(1!=n && isSame(temp,ans)) flag=1; //此时数组（在非原始数组时）与目标数组相同
swap(temp[i],temp[1]);
downAdjust(1,i-1);
if(flag==1) break;
}
}
bool insertionSort(){ //判断是否为插入排序
for(index=2;index<=n;index++){
sort(origin+1,origin+index+1);
if(isSame(origin,ans)) return true;
}
return false;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>origin[i];
temp[i]=origin[i];
}
for(int i=1;i<=n;i++)
cin>>ans[i];
if(insertionSort()){
cout<<"Insertion Sort"<<endl;
if(index!=n) sort(origin+1,origin+index+2);
print(origin);
}
else{
cout<<"Heap Sort"<<endl;
heapSort();
print(temp);
}
return 0;
}
发表于 2019-01-27 19:06:36
回复(0)
问题信息
难度：
29条回答
11收藏
11214浏览
通过挑战的用户
-
2023-03-11 13:40:02
-
2023-02-27 17:49:42 -
2023-02-27 14:05:44
-
2023-02-25 15:31:10
-
2023-02-24 16:16:12
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
