#include <stdlib.h>
#include <stdio.h>
//順序表表示的存儲結構
#define MAXNUM 100000
typedef int KeyType;
typedef int DataType;
typedef struct      
{                    
  KeyType key;        //排序碼字段
  DataType info;      //記錄的其他字段
}RecordNode;
typedef struct
{
  RecordNode record[MAXNUM];
  int n;              //n為文件中的記錄個數，n<=MAXNUM
}SortObject;
/**************************************************/
/*                Shell插入排序算法               */
/**************************************************/  
void shellSort(SortObject &pvector,int &com,int &mov)
{
   int i,j,increment;
    RecordNode temp;
     for(increment=4;increment>0;increment/=2)
      /*increment 為本趟Shell排序增量*/
      {
        for(i=increment;i<pvector.n;i++)
        {
		   
           temp=pvector.record[i];    /*保存待插入記錄Ri*/
           j=i-increment;
		   com++;
           while(j>=0&&temp.key<pvector.record[j].key)  /*查找插入位置*/
           {  
			  mov++;
              pvector.record[j+increment]=pvector.record[j]; /*記錄后移*/
              j-=increment;
			  if(j>=0)
			    com++;
           }
           pvector.record[j+increment]=temp;/*插入記錄Ri*/
        }
      }
}
/******************************************/
/*               堆排序算法               */
/******************************************/
/*篩選算法*/
#define leftChild(i) 2*(i)+1
void sift(SortObject &pvector,int i,int n,int &com,int &mov)
{
   int child;
   RecordNode temp;
   temp=pvector.record[i];
   child=leftChild(i);/*Rchild是R0的左子女*/
   while(child<n)
   {
      if(child<n-1)
	  {   com++;
		  if(pvector.record[child].key<pvector.record[child+1].key)
            child++;/*child指向Ri的左、右子女中排序碼較大的結點*/
	  }
	   com++;
      if(temp.key<pvector.record[child].key)
      {
         pvector.record[i]=pvector.record[child];
         /*將Rchild換到父結點位置，進入下一層繼續調整*/
		 mov++;
         i=child;
         child=leftChild(i);
      }
      else break;/*調整結束*/
   }
   pvector.record[i]=temp;/*將記錄Ri放入正確位置*/
}
/*堆排序算法*/
void heapSort(SortObject &pvector,int &C,int &M) /*對記錄R0到Rn-1進行堆排序*/
{
   int i,n;
   RecordNode temp;
   n=pvector.n;
   for(i=n/2-1;i>=0;i--)
     sift(pvector,i,n,C,M);  /*建立初始堆*/
   for(i=n-1;i>0;i--)    /*進行n-1趟堆排序*/
   {
	   M++;
      temp=pvector.record[0];  /*當前堆頂記錄和最后一個記錄互換*/
      pvector.record[0]=pvector.record[i];
      pvector.record[i]=temp;
        sift(pvector,0,i,C,M) ;  /*從R0到Ri-1重建堆*/
   }
}
/*****************************************/
/*              快速排序算法             */
/*****************************************/
void quickSort(SortObject &pvector,int l,int r,int &com,int &res)
{
  int i,j;
  RecordNode temp;
  if(l>=r)
    return;/*只有一個記錄或無記錄，則無需排序*/
  i=l;j=r;
  temp=pvector.record[i];
  while(i!=j)
  {
	  com++;
      while((pvector.record[j].key>=temp.key)&&(j>i))
	  {
		  j--;/*從右向左掃描，查找第l個排序碼小于temp.key的記錄*/
		  com++;
	  }
      if(i<j)
         pvector.record[i++]=pvector.record[j];
	     res++;
		 com++;
      while((pvector.record[i].key<=temp.key)&&(j>i))
	  {
		  i++;/*從左向左掃描，查找第l個排序碼大于temp.key的記錄*/
		  com++;
	  }
      if(i<j)
          pvector.record[j--]=pvector.record[i];
	      res++;
  }
  pvector.record[i]=temp;    /*找到Ri的最終位置*/
  quickSort(pvector,l,i-1, com, res);  /*遞歸處理左區間*/
  quickSort(pvector,i+1,r,com,res);  /*遞歸處理右區間*/
}
/*****************************************/
/*               冒泡排序算法            */
/*****************************************/
void bubbleSort(SortObject &pvector,int &com,int &mov )
{
   int i,j,noswap;
   RecordNode temp;
   for(i=0;i<pvector.n;i++)            /*做n-1次起泡*/
   {
      noswap=TRUE;
      for(j=0;j<pvector.n-i-1;j++)    /*置交換標志*/
	  {
		com++;
        if(pvector.record[j+1].key<pvector.record[j].key) /*從前向后掃描*/
        {
		  mov++;
          temp=pvector.record[j];                        /*交換記錄*/
          pvector.record[j]=pvector.record[j+1];
          pvector.record[j+1]=temp;
          noswap=FALSE;
        }
	  }
      if(noswap)
      break;  /*本趟起泡未發生記錄交換，算法結束*/
   }
}
/**************************************************/
/*               二分法插入排序算法               */
/**************************************************/  
void binSort (SortObject &pvector,int &com,int &mov)
{
	int i,j,left,mid,right;
	RecordNode temp;
    for (i=1;i<pvector.n;i++)
	{
	   temp=pvector.record[i];
	   left=0;right=i-1;         //置已排序區間的下、上界初值
	   while(left<=right)
	   {
		 mid=(left+right)/2;  //mid指向已排序區間的中間位置
		 if(temp.key<pvector.record[mid].key)
		 { com++;right=mid-1;}  //插入元素應在左子區間
		 else
			left=mid+1;      //插入元素應在右子區間
	   }
	    for(j=i-1;j>=left;j--)
		{
		pvector.record[j+1]=pvector.record[j];
		mov++;
		}
	    if(left!=i) 
		pvector.record[left]=temp;//將排序碼大于Ki的記錄后移
	}
}
/**************************************************/
/*              直接插入排序算法                  */
/**************************************************/  
void insertSort(SortObject &pvector,int &com,int &mov)
{ int i,j;                
  RecordNode temp;               
   for(i=1;i<pvector.n;i++)     //依次插入記錄R1、R2\......
  {
	  temp=pvector.record[i];
	  j=i-1;
	  com=i;
	  while((temp.key<pvector.record[j].key)&&(j>=0))//由后向前找插入位置
	  {
		  mov++;
		  pvector.record[j+1]=pvector.record[j];    //將排序碼大于Ki的記錄后移
		  j--;
	  }
	  if(j!=(i-1)) pvector.record[j+1]=temp;
  }
   com+=mov;
}
/*****************************************/
/*            直接選擇排序算法           */
/*****************************************/
void SelectSort(SortObject &pvector,int &com,int &mov)
{
	int i,j,k;
	RecordNode temp;
	 for(i=0;i<pvector.n;i++)//做n-1趟選擇排序
	 {
		 k=i;
		 for(j=i+1;j<pvector.n;j++)//在無序區內找出排序碼最小的記錄Rk;
		 {
			 com++;              //比較次數的統計
			 if(pvector.record[j].key<pvector.record[k].key) 
				 k=j;
		 }
		 if(k!=i)
		 {
			 mov++;               //移動次數的統計
			 temp=pvector.record[i];
			 pvector.record[i]=pvector.record[k];
			 pvector.record[k]=temp;
		 }
	 }
}