//* * * * * * * * * * * * * * * * * * * * * * * *
//*CHAPTER          :7  (7_7)                   *
//*PROGRAM          :歸并排序                     *
//*CONTENT          :歸并排序                     *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 30 //排序表的最大容量
typedef struct           //定義排序表的結構
{int  elemword[MAXSIZE]; //數據元素關鍵字
 int length;            //表中當前元素的個數
}SqList;
void InitialSqList(SqList&);       //初始化排序表
void MergeSort(SqList &);          //歸并排序
void MSort(int [],int [],int,int); //歸并排序遞歸子程序
void Merge(int [],int [],int,int,int); //兩個子序列歸并
void PrintSqList(SqList);          //顯示表中的所有元素
void main()
{SqList L;  //聲明表L
 char j='y';
 textbackground(3);  //設定屏幕顏色
 textcolor(15);
 clrscr();
 //-------------------------程序說明-------------------------------
 printf("本程序將演示歸并排序的操作。\n");
 //----------------------------------------------------------------
 while(j!='n'&&j!='N')
   {InitialSqList(L);    //待排序列初始化
    MergeSort(L);         //歸并排序
    PrintSqList(L);      //顯示排序結果
    printf("繼續進行下一次排序嗎?(Y/N)");
    scanf(" %c",&j);
   }
 printf("程序運行結束!\n按任意鍵關閉窗口!\n");
 getchar();getchar();
}
void InitialSqList(SqList &L)
{//表初始化
 int i;
 printf("請輸入待排序的記錄的個數:");
 scanf("%d",&L.length);
 printf("請輸入待排序的記錄的關鍵字(整型數):\n");
 for(i=1;i<=L.length;i++)
   scanf("%d",&L.elemword[i]);
}
void MergeSort(SqList &L)
{//對順序表L做歸并排序。
 MSort(L.elemword,L.elemword,1,L.length);
}
void MSort(int SR[],int TR1[],int s,int t)
{//將SR[s..t]歸并排序為TR1[s..t]。
 int m;
 int TR2[MAXSIZE];
 if(s==t) TR1[s]=SR[s];
 else
   {m=(s+t)/2;           //將SR[s..t]平分為SR[s..m]和SR[m+1..t]
    MSort(SR,TR2,s,m);   //遞歸地將SR[s..m]歸并為有序的TR2[s..m]
    MSort(SR,TR2,m+1,t); //遞歸地將SR[m+1..t]歸并為有序的TR2[m+1..t]
    Merge(TR2,TR1,s,m,t);//將TR2[s..m]和TR2[m+1..t]歸并到TR1[s..t]
   }
}
void Merge(int SR[],int TR[],int i,int m,int n)
{//將有序的SR[i..m]和SR[m+1..n]歸并為有序的TR[i..n]
 int j,k,p;
 for(j=m+1,k=i;i<=m&&j<=n;++k) //將SR中的記錄有小到大地并入TR
   {if(SR[i]<SR[j]) TR[k]=SR[i++];
    else TR[k]=SR[j++];
   }
 if(i<=m)
   for(p=k;p<=n;p++) //將剩余的SR[i..m]復制到TR
     {TR[p]=SR[i];   
      i++;
     }
 if(j<=n)
   for(p=k;p<=n;p++) //將剩余的SR[j..n]復制到TR
     {TR[p]=SR[j];
      j++;
     }
}
void PrintSqList(SqList L)
{//顯示表中所有元素
 int i;
 printf("已排好序的序列如下：\n");
 for(i=1;i<=L.length;i++)
    printf("%4d",L.elemword[i]);
 printf("\n");
}