2016年408算法大题

已知由n（n>=2）个正整数构成的集合A ，将其划分成两个不相交的子集A1和A2，元素个数分别为n1和n2，A1和A2中元素之和分别为S1和S2。设计一个尽可能高效的划分算法，满足|n1-n2|最小且|S1-S2|最大。要求：

1）给出算法的基本设计思想。

2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

3）说明你所设计算法的平均时间复杂度和空间复杂度。

【解析】

（1）根据快速排序的思想，把找到最佳的划分，把最小的[n/2]个数放到A1，其余的数放到A2。分组结果即为题意所求。

算法步骤：

1）若i=[n/2]，则划分结束。

2）若i<[n/2]，则枢轴及之前的所有元素均属于A1，继续对i之后的元素进行划分。

3）若i>[n/2]，则枢轴及之后的所有元素均属于A2，继续对i之前的元素进行划分。

  

   

    

     

    
    

     

      int setPartition(int a[],int n){
     
    
   

    

     

    
    

     
    int pivotkey,low=0,low0=0,high=n-1,high0=n-1,flag=1,k=n/2,i;
     
    
   

    

     

    
    

     
    int s1=0,s2=0;
     
    
   

    

     

    
    

     
    while(flag){
     
    
   

    

     

    
    

     

              pivotkey=a[low]; //选择枢轴
     
    
   

    

     

    
    

     
        while(low<high){  //基于枢轴对数据记性划分
     
    
   

    

     

    
    

     
            while(low<high && a[high]>=pivotkey) --high;
     
    
   

    

     

    
    

     
            if(low!=high) a[low]=a[high];
     
    
   

    

     

    
    

     
            while(low<high && a[low]<=pivotkey) ++low;
     
    
   

    

     

    
    

     
            if(low!=high) a[high]=a[low];
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

              a[low]=pivotkey;
     
    
   

    

     

    
    

     
        if(low==k-1) //若枢轴是第n/2个元素，划分成功
     
    
   

    

     

    
    

     

              flag=0；
     
    
   

    

     

    
    

     
        else if(low<k-1){
     
    
   

    

     

    
    

     

                  low0=++low;
     
    
   

    

     

    
    

     

                  high=high0;
     
    
   

    

     

    
    

     

              }else{
     
    
   

    

     

    
    

     

                  high0=--high;
     
    
   

    

     

    
    

     

                  low=low0;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          } 
     
    
   

    

     

    
    

     
    for(i=0;i<k;i++) s1+=a[i];
     
    
   

    

     

    
    

     
    for(i=k;i<n;i++) s2+=a[i];
     
    
   

    

     

    
    

     
    return s2-s1;
     
    
   

    

     

    
    

     

      }
     
    
  
 

（3）算法的平均时间复杂度为O(n),空间复杂度为O(1).

【注意】时间复杂度不要误以为是O（logn）

附：快速排序模板（牢记）

  

   

    

     

    
    

     

      void Quiksort(ElemType A[],int low,int high){
     
    
   

    

     

    
    

     
    if(low<high){
     
    
   

    

     

    
    

     
        //Partition()是划分操作，将原表划分成2表
     
    
   

    

     

    
    

     
        int pivot=Partition(A,low,high);//划分
     
    
   

    

     

    
    

     
        QuickSort(A,low,pivot-1);
     
    
   

    

     

    
    

     
        QuickSort(A,pivot,high);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int Partition(ElemType A[],int low,int high){
     
    
   

    

     

    
    

     

          ElemType pivot=A[low];//将当前表中第一个元素设为枢轴，对表进行划分
     
    
   

    

     

    
    

     
    while(low<high){  //循环跳出条件
     
    
   

    

     

    
    

     
        while(low<high&&A[high]>=pivot) --high;
     
    
   

    

     

    
    

     

              A[low]=A[high];//将比枢轴小的元素移动到左端
     
    
   

    

     

    
    

     
        while(low<high&&A[low]<=pivot)  ++low;
     
    
   

    

     

    
    

     

              A[high]=A[low];//将比数轴大的元素移动到左端
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

          A[low]=pivot;//枢轴元素存放到最终位置
     
    
   

    

     

    
    

     
    return low;//返回存放枢轴的最终位置
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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