//* * * * * * * * * * * * * * * * * * * * * * * *
//*CHAPTER          :7  (7_1)                   *
//*PROGRAM          :直接插入排序               *
//*CONTENT          :直接插入排序               *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 20 //排序表的最大容量
typedef struct           //定義排序表的結構
{int  elemword[MAXSIZE]; //數據元素關鍵字
 int count;            //表中當前元素的個數
}SqList;
void InitialSqList(SqList&); //初始化排序表
void InsertSort(SqList&);   //直接插入排序
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);
    InsertSort(L);
    PrintSqList(L);
    printf("繼續進行下一次排序嗎?(Y/N)");
    scanf(" %c",&j);
   }
 printf("程序運行結束!\n按任意鍵關閉窗口!\n");
 getchar();getchar();
}
void InitialSqList(SqList &L)
{//表初始化
 int i;
 printf("請輸入待排序的記錄的個數:");
 scanf("%d",&L.count);
 printf("請輸入待排序的記錄的關鍵字(整型數):\n");
 for(i=1;i<=L.count;i++) 
   scanf("%d",&L.elemword[i]);
}
void InsertSort(SqList &L)
{int i,j;
 for(i=2;i<=L.count;i++)
   if(L.elemword[i]<L.elemword[i-1])  //"<",需將L.elemword[i]插入有序子表
     { L.elemword[0]=L.elemword[i];   //復制為哨兵
       for(j=i-1;L.elemword[0]<L.elemword[j];--j)
          L.elemword[j+1]=L.elemword[j];  //記錄后移
       L.elemword[j+1]=L.elemword[0];     //插入到正確的位置
     }
}
void PrintSqList(SqList L)
{//顯示表所有元素
 int i;
 printf("已排好序的序列如下：\n");
 for(i=1;i<=L.count;i++) 
    printf("%4d",L.elemword[i]);
 printf("\n");
}