#include<stdio.h>
/*定義待排序數組的最大長度*/
#define MAX 100
/*———————————————————————直接插入排序——————————————————————————*/
void InsertSort(int *R,int n)
{ 
		/* 對數組R中的元素R[1]..R[n-1]按遞增序進行插入排序*/
    int i,j;
    /*空出哨位R[0]*/
    for(i=n;i>=1;i--)
			R[i]=R[i-1];
    /* 依次插入R[2]，…，R[n] */
    for(i=2;i<=n;i++)
    /* 若R[i]大于等于有序區中所有的R，則R[i]應在原有位置上，否則進行插入*/ 
    if(R[i]<R[i-1])
    {
    	/* R[0]是哨兵，保存R[i] */
      R[0]=R[i];
      j=i-1; 
      /* 從右向左在有序區R[0]..R[-1]中查找R[i]的插入位置 */
      while(1)
      { 
      	/* 將關鍵字大于R[i]的記錄后移 */
       	R[j+1]=R[j]; 
        j--;
     	 /* 當R[i]≥R[j]時終止 */
        if(R[0]>=R[j])
        	break;
      }
      /* R[i]插入到正確的位置上 */ 
      R[j+1]=R[0]; 
    }
    /*元素復位*/
    for(i=0;i<n;i++)
			R[i]=R[i+1];
}
/*——————————————————————— 希爾排序 ——————————————————————————*/
void ShellSort(int *R,int n)//希爾排序
{
	int i,j,k;
	 /*空出暫存單元R[0]*/
	for(i=n;i>=1;i--)
		R[i]=R[i-1];
	k=n/2;
	while(k>=1)
	{
		/* 希爾排序中的一趟排序，k為當前增量 */
		/* 將R[d+1．．n]分別插入各組當前的有序區 */
		for(i=k+1;i<=n;i++)
		{
			/* R[0]只是暫存單元，不是哨兵 */
			R[0]=R[i];
			j=i-k;
			/* 查找R[i]的插入位置 */
			while((R[j]>R[0])&&(j>=0))
			{
				/* 后移記錄 */
				R[j+k]=R[j];
				/* 查找前一記錄 */
				j=j-k;
			}
			/* 插入R[i]到正確的位置上 */
			R[j+k]=R[0];
		}
		/* 求下一增量 */
		k=k/2;
	}
	/*元素復位*/
	for(i=0;i<n;i++)
		R[i]=R[i+1];
}
/*——————————————————————— 冒泡排序 ——————————————————————————*/
void BubbleSort(int *R,int n)
{ 
	 /* R[l]..R[n]是待排序的文件，采用自下向上掃描，對R做冒泡排序 */
   int i,j;
   /* 交換標志 */
   int flag; 
   /*空出暫存單元R[0]*/
	 for(i=n;i>=1;i--)
		 R[i]=R[i-1];
   for(i=1;i<n;i++)
   { /* 最多做n-1趟排序 */
       flag=0; /* 本趟排序開始前，交換標志應為假 */
       for(j=n-1;j>=i;j--) /* 對當前無序區R[i..n]自下向上掃描 */
        /* 交換記錄 */
        if(R[j+1]<R[j])
        {
        	/* R[0]不是哨兵，僅做暫存單元 */
          R[0]=R[j+1]; 
          R[j+1]=R[j];
          R[j]=R[0];
          /* 發生了交換，將交換標志置為真 */
          flag=1; 
        }
       /* 本趟排序未發生交換，提前終止算法 */
       if(!flag) 
       {
       	   /*元素復位*/
       	  for(i=0;i<n;i++)
				  	R[i]=R[i+1];
	        return;
	     }
     }
}
/*——————————————————————— 快速排序 ——————————————————————————*/
/* 分區處理函數,調用PartitionQuick(R,l,h)時，
對R[l..h]做劃分,并返回樞軸的位置 */
int PartitionQuick(int *R,int l,int h)
{
	int i,j;
	int x;
	i=l;
	j=h;
	/* 用區間的第1個記錄作為基準 */
	x=R[i];
	/* 從區間兩端交替向中間掃描，直至i=j為止 */
	while(i<j)
	{
		/*從右向左掃描，查找第1個關鍵字小于x的記錄R[j] */
		while((i<j)&&(R[j]>=x))
			j--;
		/*找到的R[j]的關鍵字小于x*/
		if(i<j)
		{
			/*交換R[i]和R[j]，交換后i指針加1*/
			R[i]=R[j];
			i++;
		}
		/*從左向右掃描，查找第1個關鍵字大于x的記錄R[i]*/
		while((i<j)&&(R[i]<=x))
			i++;
		/*表示找到了R[i]，使R[i]>x*/
		if(i<j)
		{
			/*交換R[i]和R[j]，交換后j指針減1*/
			R[j]=R[i];
			j--;
		}
	}
	/*基準記錄被最后定位*/
	R[i]=x;
	return i;
}
void QuickSort(int *R,int l,int h)
{
	/*i是劃分后的基準記錄的位置*/
	int i;
	/*僅當區間長度大于1時才須排序*/
	if(l<h)
	{
		/*對R[l..h]做劃分*/
		i=PartitionQuick(R,l,h);
		/*對左區間遞歸排序*/
		QuickSort(R,l,i-1);
		/*對右區間遞歸排序*/
		QuickSort(R,i+1,h);
	}
}
/*——————————————————————— 選擇排序 ——————————————————————————*/
void SelectSort(int *R,int n)
{
   int i,j,k;
    /*空出暫存單元R[0]*/
	 for(i=n;i>=1;i--)
		 R[i]=R[i-1];
	 /*進行n-1趟選擇排序*/
   for(i=1;i<n;i++)
   {
   	 /* 做第i趟排序(1≤i≤n-1) */
   	 /* k記下目前找到的最小元素所在的位置 */
     k=i;
     /* 在當前無序區R[i..n]中選最小的記錄R[k] */
     for(j=i+1;j<=n;j++) 
       if(R[j]<R[k])
         k=j; 
       if(k!=i)
       { 
       	 /*交換R[i]和R[k],R[0]作暫存單元使用*/
         R[0]=R[i]; 
         R[i]=R[k]; 
         R[k]=R[0]; 
       } 
     } 
     /*元素復位*/
     for(i=0;i<n;i++)
				R[i]=R[i+1];
} 
/*————————————————————————— 堆排序 ————————————————————————————*/
void HeapAdjust(int *R,int i,int n)
{ 
	 /*對R[1..n]進行堆調整*/
   int j,temp;
   temp=R[i];
   j=2*i;
   while (j<=n)
   {
	   if (R[j]>R[j+1]&&j<n) 
	  	 j++;
	   if (temp<R[j]) 
	  	 j=n+1;
	   else
	   {
	   	 R[i]=R[j];
     	 i=j;
    	 j=2*i;
     }
   }
   R[i]=temp;
}
void HeapSort(int *R,int n)
{ /* 對R[1..n]進行堆排序，用R[0]做暫存單元*/
    int i;
    /*空出暫存單元R[0]*/
	  for(i=n;i>=1;i--)
		 R[i]=R[i-1];
    /* 將R[1-n]建成初始堆*/
    for(i=n/2;i>0;i--)
      HeapAdjust(R,i,n); 
    /*進行n-1趟堆排序*/
    for(i=n;i>1;i--)
    { 
    	/* 將堆頂和堆中最后一個記錄交換 */
    	R[0]=R[1]; 
    	R[1]=R[i];
    	R[i]=R[0]; 
    	/* 將R[1]..R[i-1]重新調整為堆*/
    	HeapAdjust(R,1,i-1); 
    }
    /*元素復位*/
    for(i=0;i<n;i++)
			R[i]=R[i+1];
} 
int main()
{
	/*排序使用的數組*/
	int R[MAX]={1,82,63,4,65,69,37,98,39,46};
	int i;
	char c;
	clrscr();
	printf("***************************************\n");
	printf("|  Please choose the method to sort:  |\n");
	printf("|           i :  InsertSort           |\n");
	printf("|           l :  ShellSort            |\n");
  printf("|           b :  BubbleSort           |\n");
  printf("|           q :  QuickSort            |\n");
  printf("|           s :  SelectSort           |\n");
  printf("|           h :  HeapSort             |\n");
  printf("***************************************\n");
  while(1)
  {
    switch(getch())
    {
      case 'i':
        InsertSort(R,10);
        printf("\nThe result of InsertSort is:\n");
        break;
      case 'l':
        ShellSort(R,10);
        printf("\nThe result of ShellSort is:\n");
        break;
      case 'b':
        BubbleSort(R,10);
        printf("\nThe result of InsertSort is:\n");
        break;
      case 'q':
        QuickSort(R,0,9);
        printf("\nThe result of BubbleSort is:\n");
        break;
      case 's':
        SelectSort(R,10);
        printf("\nThe result of SelectSort is:\n");
        break;
      case 'h':
        HeapSort(R,10);
        printf("\nThe result of HeapSort is:\n");
        break;
      default:
        return 0;	
    }
    /*輸出插入排序的結果*/
	  for(i=0;i<10;i++)
		  printf("%3d",R[i]);
		printf("\n");
	}
}