many sort algorithms

sort.cpp

#include <iostream.h>
#include <stdlib.h>
  /**/
const int NUM = 6;
void Swap(int &a,int &b)
{
  int t = 0;
  t = a;
  a = b;
  b = t;
}
void output(int data[])
{
   for(int i=0; i<NUM; i++)
   {
       cout<<data[i]<<" ";
   }
   cout<<endl;
}

void InsertSort(int  A[], int n)
{
   for(int i=1 ; i<n; i++)
  {
    int j = i;
    int temp = A[i];
    while (j > 0 && temp < A[j-1])
    {
      A[j] = A[j-1];
      j--;

    } //A[j] 与A[j]以前的一一比较  把比A[j]大的后移一位
      A[j] = temp;
      output(A);
   }
}
void ShellSort(int A[],int n )
{
  int i,j,t,d;
  d = n/2;
  while (d >= 1)
  {
    for (i=d; i<=n; i++)
    {
      t = A[i];
      j = i-d;
      while (j>=0 && t<A[j])   //A[i]  和  A[i-d]  比较
      {
        cout<<t<<" "<<A[j]<<" "<<j<<endl;
          A[j+d] = A[j];
          j = j-d;

      }
       A[j+d]=t;
       output(A);
    }
      d=d/2;
      cout<<d<<endl;
  }
}
void  BubbleSort(int A[],int n)
{
  int i,j,last;
  i = n-1;
  while( i > 0)   //直到没有移动为止
  {
    last = 0;
    for(j=0; j<i; j++)
    {
      if(A[j+1] < A[j])
      {
         Swap(A[j],A[j+1]);
         last = j;    //标记
      }
      output(A);
    }
      i = last;

  }    //endwhlie
}
void QSort(int A[],int left,int right)       //递归函数
{
  int i,j;
  if(left < right)
  {
     i = left;
     j = right + 1;
    do{
       do
          i++;
        while(A[i] < A[left]);
       do 
          j--;
         while(A[j] > A[left]);
       if(i<j) 
          Swap(A[i],A[j]);
}while(i < j);
Swap(A[left] ,A[j]);
    for(int i=0; i<NUM; i++)
   {
     cout<<A[i]<<"\t";
   }
   cout<<endl;
QSort(A,left,j-1);
QSort(A,j+1,right);
}
}
void QuickSort(int A[],int n)
{
  QSort(A,0,n-1);
}

void  SelectSort(int A[], int n)
{
 int small;
 for(int i=0; i<n-1; i++)
 {
   small = i;
   for(int j=i+1; j<n ; j++)
   if(A[j] < A[small])
        small = j;                 //找最小数
   Swap(A[i], A[small]);                      //不稳定
   output(A);
 }
}

void Sift(int A[],int i,int m)     //移动 A[i]
{
  int j;
  int  temp = 0;
  temp = A[i];
  j = 2*i;
  while (j<=m)
   {
     if ((j<m) && (A[j] < A[j+1]))
         j++;
     if (temp < A[j])
       {
         A[i]=A[j];
         i=j;
         j=2*i;
       }
     else break;
   }
  A[i] = temp;
  output(A);
}
void HeapSort(int A[],int n)
{
  int i;
  for(i=n/2; i>=1; i--)
     Sift(A,i,n);            //建堆
  output(A);cout<<"%"<<endl;
  for(i=n; i>=1; i--)
  {
     Swap(A[1],A[i]);
     Sift(A,1,i-1);
  }
 // output(A);
}

void Merge(int A[],int n,int swap[],int k)
{
	int m=0,upper1,lower2,i,j,upper2;
	
	int lower1 = 0;
	while(lower1+k <= n-1)
	{
		lower2 = lower1+k;
		upper1 = lower2-1;
		upper2 = (lower2+k-1 <= n-1) ? lower2+k-1 : n-1;
		
		for(i=lower1,j=lower2;(i<=upper1 && j<=upper2); m++)
		{
			if(A[i] <= A[j])
			{
                 cout<<k<<" "<<A[i]<<" "<<A[j]<<endl;
				swap[m] = A[i];

				i++;
			}
			else
			{
              cout<<k<<" "<<A[j]<<" "<<A[i]<<endl;
				swap[m] = A[j];
				j++;
			}
		}
		while(i<=upper1)
		{
           cout<<k<<"*"<<A[i]<<" "<<endl;
			swap[m] = A[i];
			m++;
			i++;
		}
		
		while(j<=upper2)
		{
          cout<<k<<"%"<<A[j]<<" "<<endl;
			swap[m] = A[j];
			m++;
			j++;
		}
		lower1 = upper2+1;
	}
	for(i=lower1; i<n; i++,m++)
           swap[m] = A[i];
    output(swap);                       //swap  是临时储存结果的
}
/*二路归并排序算法如下*/
void MergeSort(int A[],int n)
{
	int i,k=1;
	int  *swap;
	
	swap = new int[n];
	
	while( k < n)
	{
		Merge(A,n,swap,k);
		for(i=0; i<n; i++)
			A[i] = swap[i];        //copy?
		k = 2*k;                   //k 以2倍增长
	}
    delete swap;
}

int main(void)
{
   int  data[NUM+1] = {22,8,7,6,5,4,22};
   // int  data[NUM] = {3,2,2,5};    ShellSort killer
   //BubbleSort(data,NUM);
   //InsertSort(data,NUM);
   // ShellSort(data,NUM);
   // QuickSort(data,NUM);
  // SelectSort(data,NUM);
   // HeapSort(data,NUM);
   MergeSort (data,NUM);
    //output(data);
      system("PAUSE");
      return 0;
}