C++中的几种排序算法

SortAlgorithm::SortAlgorithm(intvectorSize)
{
   size=(vectorSize>0?vectorSize:10);//validatevectorSize
   srand(time(0));//seedusingcurrenttime

  //fillvectorwithrandomintsinrange10-99
   for(inti=0;i<size;i++)
          source.push_back(10+rand()%90);//10-99

   temp=source;
}

voidSortAlgorithm::insertSort()
{
   intinsert;
   for(intnext=1;next<size;next++){
       insert=temp[next];
       intmoveItem=next;

       while((moveItem>0)&&(temp[moveItem-1]>insert)){
           temp[moveItem]=temp[moveItem-1];
           moveItem--;
       }

       temp[moveItem]=insert;
   }
}

voidSortAlgorithm::selectSort()
{
   intloop=size-1;
   intsmallest;

   for(inti=0;i<loop;i++){
       smallest=i;

       for(intj=i+1;j<size;j++){
           if(temp[j]<temp[smallest])
               smallest=j;
       }

       swap(temp[i],temp[smallest]);
   }
}

voidSortAlgorithm::mergeSort()
{
   sortSubVector(0,size-1);
}

voidSortAlgorithm::bubbleSort()
{
      intcomp;//usedtocontrolforloopandforsubscripts
      boolswapCheck=true;//wasaswapmade?

   for(intpass=1;pass<size&&swapCheck;pass++){
       swapCheck=false;//assumenoswapswillbemade

     //traverseandcompareunsortedpartofvector
       for(comp=0;comp<size-pass;comp++){

        //compareadjacentvectorelements
           if(temp[comp]>temp[comp+1]){
               swap(temp[comp],temp[comp+1]);
               swapCheck=true;
                }//endif

       }//endinnerfor
   }//endouterfor
}

voidSortAlgorithm::quickSort(intfirst,intlast)
{
  intcurrentLocation;

  if(first>=last)
     return;

  currentLocation=partition(first,last);//placeanelement
  quickSort(first,currentLocation-1);//sortleftside
  quickSort(currentLocation+1,last);//sortrightside
}//endfunctionquickSortHelper

//partitionthevectorintomultiplesections
intSortAlgorithm::partition(intleft,intright)
{
  intposition=left;

  //loopthroughtheportionofthevector
  while(true)
  {
  //first:fromrightroleft
     while(temp[position]<=temp[right]&&position!=right)
        --right;

     if(position==right)
        returnposition;

     if(temp[position]>temp[right])
     {
        swap(temp[position],temp[right]);
        position=right;
     }//endif
  //second:fromlefttoright
     while(temp[left]<=temp[position]&&left!=position)
        ++left;

     if(position==left)
        returnposition;

     if(temp[left]>temp[position])
     {
        swap(temp[position],temp[left]);
        position=left;
     }//endif
  }//endwhile
}//endfunctionpartition

voidSortAlgorithm::sortSubVector(intlow,inthigh)
{
   if((high-low)>=1){
       intmiddle1=(low+high)/2;
       intmiddle2=middle1+1;

       /*cout<<"split:  ";
       displaySubVector(low,high);
       cout<<endl<<"      ";
       displaySubVector(low,middle1);
       cout<<endl<<"      ";
       displaySubVector(middle2,high);
       cout<<endl<<endl;*/

       sortSubVector(low,middle1);
       //cout<<"Stophere1.low="<<low<<",middle1="<<middle1<<endl;
       sortSubVector(middle2,high);
       //cout<<"Stophere2.middle2="<<middle2<<",high="<<high<<endl;

       merge(low,middle1,middle2,high);

   }
}

voidSortAlgorithm::merge(intleft,intmiddle1,intmiddle2,intright)
{
   intleftIndex=left;
   intrightIndex=middle2;
   intcombinedIndex=left;
   vector<int>combined(size);

   /*cout<<"merge:  ";
   displaySubVector(left,middle1);
   cout<<endl<<"      ";
   displaySubVector(middle2,right);
   cout<<endl;*/

   while(leftIndex<=middle1&&rightIndex<=right){
       if(temp[leftIndex]<=temp[rightIndex])
           combined[combinedIndex++]=temp[leftIndex++];
       else
           combined[combinedIndex++]=temp[rightIndex++];
   }

   if(leftIndex==middle2){
       while(rightIndex<=right)
           combined[combinedIndex++]=temp[rightIndex++];
   }
   else{
       while(leftIndex<=middle1)
           combined[combinedIndex++]=temp[leftIndex++];
   }

   for(inti=left;i<=right;i++)
       temp[i]=combined[i];

   /*cout<<"      ";
   displaySubVector(left,right);
   cout<<endl<<endl;*/
}

voidSortAlgorithm::swap(int&x,int&y)
{
   intt;

   t=x;
   x=y;
   y=t;
}

voidSortAlgorithm::displayVector()
{
   for(inti=0;i<size;i++){
       cout<<""<<temp[i];
       if((i+1)%10==0)
           cout<<endl;
   }

   cout<<endl;

   temp=source;
}