【1098】Insertion or Heap Sort (25 分)

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm> 
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue> 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     

      //和A1089类似，注意堆排序
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      const int N=111;
     
    
   

    

     

    
    

     

      int origin[N],tempOri[N],changed[N];  //原始数组、原始数组备份、目标数组
     
    
   

    

     

    
    

     

      int n;  //元素个数
     
    
   

    

     

    
    

     

      bool isSame(int A[],int B[]){ //判断数组A和数组B是否相同
     
    
   

    

     

    
    

     
	for(int i=1;i<=n;i++){
     
    
   

    

     

    
    

     
		if(A[i]!=B[i])  return false;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return true;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void showArray(int A[]){  //输出数组
     
    
   

    

     

    
    

     
	for(int i=1;i<=n;i++){  
     
    
   

    

     

    
    

     
		printf("%d",A[i]);
     
    
   

    

     

    
    

     
		if(i<n)  printf(" ");
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	printf("\n");
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      bool insertSort(){  //插入排序
     
    
   

    

     

    
    

     
	bool flag=false;  //记录是否存在数组中间步骤与changed数组相同
     
    
   

    

     

    
    

     
	for(int i=2;i<=n;i++) {  //进行n-1趟排序
     
    
   

    

     

    
    

     
		if(i != 2 && isSame(tempOri,changed)){  
     
    
   

    

     

    
    

     

      			flag=true;  //中间步骤与目标相同，且不是初始序列
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		//插入部分直接用sort代替
     
    
   

    

     

    
    

     
		sort(tempOri,tempOri+i+1);//注意要加上1，因为后面要输出下一步序列
     
    
   

    

     

    
    

     
		if(flag == true){
     
    
   

    

     

    
    

     
			return true;  //如果flag为true，则说明已达到目标数组，返回true
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return false;  //无法达到目标数组，返回false
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      //对heap数组在[low,high]范围进行调整
     
    
   

    

     

    
    

     

      //其中为欲调整结点的数组下标，high一般为堆的最后一个元素的数组下标
     
    
   

    

     

    
    

     

      void downAdjust(int low,int high){ 
     
    
   

    

     

    
    

     
	int i=low,j=i*2; //i为欲调整的结点，j为其左孩子结点
     
    
   

    

     

    
    

     
	while(j <= high) {  //存在孩子结点
     
    
   

    

     

    
    

     
		//如果右孩子结点存在，且右孩子结点的值大于左孩子结点
     
    
   

    

     

    
    

     
		if(j+1 <=high && tempOri[j+1] > tempOri[j]){  
     
    
   

    

     

    
    

     

      			j=j+1;  //让j存储右孩子结点下标
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		//如果孩子结点(此处为右孩子)中最大的权值比父亲结点大
     
    
   

    

     

    
    

     
		if(tempOri[j] > tempOri[i]){
     
    
   

    

     

    
    

     
			swap(tempOri[j],tempOri[i]);  //交换最大权值的孩子结点与父亲结点
     
    
   

    

     

    
    

     

      			i=j;  //令i为j，令j为i的!!左!!孩子结点，进入下一层
     
    
   

    

     

    
    

     

      			j=i*2; 
     
    
   

    

     

    
    

     

      		}else {
     
    
   

    

     

    
    

     
			break;  //孩子结点的权值均比父亲结点的小，调整结束
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void heapSort(){  //堆排序
     
    
   

    

     

    
    

     
	bool flag=false;
     
    
   

    

     

    
    

     
    for(int i=n/2;i>=1;i--){
     
    
   

    

     

    
    

     
		downAdjust(i,n);  //建堆
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	for(int i=n;i>1;i--){ 
     
    
   

    

     

    
    

     
		if(i != n && isSame(tempOri,changed)){ 
     
    
   

    

     

    
    

     

      			flag = true; //中间步骤与目标相同，且不是初始序列
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		swap(tempOri[i],tempOri[1]);  //交换heap[i]与堆顶
     
    
   

    

     

    
    

     
		downAdjust(1,i-1);  //调整堆顶
     
    
   

    

     

    
    

     
		if(flag == true){  
     
    
   

    

     

    
    

     
			showArray(tempOri);  //已达到目标数组，返回true
     
    
   

    

     

    
    

     
			return;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main(){   
     
    
   

    

     

    
    

     
	scanf("%d",&n);
     
    
   

    

     

    
    

     
	for(int i=1;i<=n;i++){ 
     
    
   

    

     

    
    

     
		scanf("%d",&origin[i]);  //输入起始数组
     
    
   

    

     

    
    

     

      		tempOri[i]=origin[i];  //tempOri数组为备份，排序在tempOri上进行
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	for(int i=1; i<=n;i++){  
     
    
   

    

     

    
    

     
		scanf("%d",&changed[i]);  //目标数组
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	if(insertSort()){  //如果插入排序中找到目标数组
     
    
   

    

     

    
    

     
		printf("Insertion Sort\n"); 
     
    
   

    

     

    
    

     
		showArray(tempOri);
     
    
   

    

     

    
    

     

      	}else{  //到达此时一定是堆排序
     
    
   

    

     

    
    

     
		printf("Heap Sort\n");
     
    
   

    

     

    
    

     
		for(int i=1;i<=n;i++){
     
    
   

    

     

    
    

     

      			tempOri[i]=origin[i];  //还原tempOri数组
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		heapSort();  //堆排序
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	system("pause");
     
    
   

    

     

    
    

     
    return 0;   
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/99556455