1098. Insertion or Heap Sort (25)

只有部分正确，苦思凝想也没弄清楚剩下的那两分是什么地方没有考虑到，欢迎各位大神指点！

#include <iostream> using namespace std; #define N 110 int num[N],pSorted[N],n,hnum[N]; bool isSame(int a[],int b[]) { for(int i=1;i<=n;++i) { if( a[i] != b[i] ) return false; } return true; } void printArray(int num[]) { for( int i=1;i<=n;++i ) { if( i == n ) cout<<num[i]<<endl; else cout<<num[i]<<" "; } } void insertSorted ( int position ) { int temp = num[position]; for( int i=position-1;i>=1;--i ) { if( temp > num[position-1] ) { break; } else if( i == 1 ) { for( int j = position-1;j>=i;--j ) num[j+1] = num[j]; num[i] = temp; break; } else if( num[i] >num[position] && num[i-1] < num[position] ) { for( int j=position-1;j>=i;--j ) num[j+1] = num[j]; num[i] = temp; break; } } } void downAdjust( int low,int high ) { int i = low,j=i*2; while (j<=high) { if( (j+1)<=high && hnum[j+1] > hnum[j] ) //找到孩子节点中较大值 { ++j; } if( hnum[j] > hnum[i] ) { //如果孩子节点较大，则把孩子节点和父亲节点交换 int temp = hnum[j]; hnum[j]=hnum[i]; hnum[i]=temp; //交换之后有可能破坏下层节点的顺序，所以进行检查 i = j; j = 2*i; } else break; } } void heapSort() { for( int i=n/2;i>=1;--i ) downAdjust(i,n); for( int i=n;i>1;--i ) { int temp=hnum[1]; hnum[1] = hnum[i]; hnum[i] = temp; // cout<<"第"<<n-i+1<<"趟："; // printArray(hnum); downAdjust(1,i-1); //调整zui if( isSame(hnum,pSorted) == true ) { --i; //进行下一步的"排序" int temp=hnum[1]; hnum[1] = hnum[i]; hnum[i] = temp; downAdjust(1,i-1); cout<<"Heap Sort"<<endl; printArray(hnum); break; } } } int main () { cin>>n; for(int i=1;i<=n;++i) { cin>>num[i]; hnum[i] = num[i]; } for(int i=1;i<=n;++i) { cin>>pSorted[i]; } int i; for( i=1;i<=n;++i ) { insertSorted(i); // cout<<"第"<<i<<"趟："; // printArray(num); if( isSame(num,pSorted) == true ) //如果相等，则为插入排序 { cout<<"Insertion Sort"<<endl; if( n == 1 ) ; else insertSorted(i+1); printArray(num); break; } } if( i == n+1 ) //则为zui排序 { heapSort(); } return 0; }

知道错在哪了，插入排序写错了，如下所示：

for( i=2;i<=n;++i ) //插入排序需要进行n-1趟排序，以前i从1开始的 { insertSorted(i); // cout<<"第"<<i<<"趟："; // printArray(num); if( isSame(num,pSorted) == true ) //如果相等，则为插入排序 { cout<<"Insertion Sort"<<endl; if( n == 1 ) ; else insertSorted(i+1); printArray(num); break; } }

提交情况： 完整代码如下：

#include <iostream> using namespace std; #define N 110 int num[N],pSorted[N],n,hnum[N]; bool isSame(int a[],int b[]) //检查两个数组是否相同 { for(int i=1;i<=n;++i) { if( a[i] != b[i] ) return false; } return true; } void printArray(int num[]) //输出数组 { for( int i=1;i<=n;++i ) { if( i == n ) cout<<num[i]<<endl; else cout<<num[i]<<" "; } } void insertSorted ( int position ) //插入排序 { int temp = num[position]; for( int i=position-1;i>=1;--i ) //这一层循环寻找temp应该放的位置 { if( temp > num[position-1] ) //若temp（即num[position]） 比它前边的元素大，则直接结束 { break; } else if( i == 1 ) //若比较到第一个位置，则说明带插入元素是最小的，应该放在第一个位置上 { for( int j = position-1;j>=i;--j ) num[j+1] = num[j]; num[i] = temp; break; } else if( num[i] >num[position] && num[i-1] < num[position] ) //检查待排序元素是否放在中间的某个位置上 { for( int j=position-1;j>=i;--j ) num[j+1] = num[j]; num[i] = temp; break; } } } void downAdjust( int low,int high ) { int i = low,j=i*2; while (j<=high) { if( (j+1)<=high && hnum[j+1] > hnum[j] ) //找到孩子节点中较大值 { ++j; } if( hnum[j] > hnum[i] ) { //如果孩子节点较大，则把孩子节点和父亲节点交换 int temp = hnum[j]; hnum[j]=hnum[i]; hnum[i]=temp; //交换之后有可能破坏下层节点的顺序，所以进行检查 i = j; j = 2*i; } else break; } } void heapSort() { for( int i=n/2;i>=1;--i ) //从第n/2个位置开始，建立初始堆 downAdjust(i,n); for( int i=n;i>1;--i ) { int temp=hnum[1]; //交换第一个位置和第i个位置的元素 hnum[1] = hnum[i]; hnum[i] = temp; // cout<<"第"<<n-i+1<<"趟："; // printArray(hnum); downAdjust(1,i-1); //交换元素之后调整堆 if( isSame(hnum,pSorted) == true ) //检查是否和部分排完序的数组相等， { //若相等，则进行下一次排序并输出 --i; //进行下一步的"排序" int temp=hnum[1]; hnum[1] = hnum[i]; hnum[i] = temp; downAdjust(1,i-1); cout<<"Heap Sort"<<endl; printArray(hnum); break; } } } int main () { cin>>n; for(int i=1;i<=n;++i) //输入待排序的数组 { cin>>num[i]; //num数组用于插入排序 hnum[i] = num[i]; //hnum数组用于堆排序 } for(int i=1;i<=n;++i) { cin>>pSorted[i]; //输入部分排序的数组 } int i; for( i=2;i<=n;++i ) //插入排序需要进行n-1趟排序，以前i从1开始的 { insertSorted(i); // cout<<"第"<<i<<"趟："; // printArray(num); if( isSame(num,pSorted) == true ) //如果相等，则为插入排序 { cout<<"Insertion Sort"<<endl; insertSorted(i+1); printArray(num); break; } } if( i == n+1 ) //上边的循环结束后，若不是插入排序，则i最后的值为n+1，由此可判断为堆排序 { heapSort(); //进行堆排序 } return 0; }