#define?CPP?C++
#define?MPP?M++
#define?MP2?M+=2
#define?MP3?M+=3

#include
#include?
#include
#include?
#include?
#include

const?int?maxsize=1000;
typedef?int?datatype;
typedef?struct{
	datatype?key;
}rectype;
typedef?rectype?list[maxsize+1];??????//排序表類型，0號單元不用

__int64?CM;?????????????????//比較和移動次數

void?check（list?Rint?n）?{???//檢驗排序結果
??int?i;
??for（i=2;i<=n;i++）
????if（R[i].key??cout<<“Correct!?“<}

void?disp（list?Rint?n）?{????//顯示數組中的數據
??int?i;
??for（i=1;i<=n;i++）?{
????cout<??}
??cout<}

/*int?random1（int?num）?{return?rand（）;}?//0~RAND_MAX=32767

int?random2（int?num）?{//素數模乘同余法0~M
??int?A=16807;??????//?1680739722040764261123630360016??48271?
??int?M=2147483647;?//有符號4字節最大素數2^31-1
??int?Q=M/A;
??int?R=M%A;
??static?int?x=1;???//seed（set?to?1）
??int?x1;
??x1=A*（x%Q）-R*（x/Q）;
??if（x1>=0）?x=x1;
??else??????x=x1+M;
??return?x;
}*/

void?InsertSort（list?R?int?n）??{??//有監視哨，直接插入排序
int?ij;
??for（i=2;i<=n;i++）?{???????????//依次插入R[2]R[3]…R[n]
????if（CPPR[i].key>=R[i-1].key）?continue;
????????????????????????????????//R[i]大于有序區最后一個記錄，則本趟不需插入
????MPPR[0]=R[i];??????????????//R[0]是監視哨
????j=i-1;
????do?{????????????????????????//查找R[i]的插入位置
??????MPPR[j+1]=R[j];j--;??????//記錄后移，繼續向前搜索
????}?while（CPPR[0].key????MPPR[j+1]=R[0];????????????//插入R[i]
??}
}

void?InsertSort0（list?R?int?n）{//直接插入排序，無監視哨
??int?ij;rectype?x;????????????//x為輔助量（用R[0]代替時間變長）
??for（i=2;i<=n;i++）?{???????????//進行n-1次插入
????if（CPPR[i].key>=R[i-1].key）?continue;
????MPPx=R[i];?????????????????//待排記錄暫存到x
????j=i-1;
????do?{????????????????????????//順序比較和移動
??????MPPR[j+1]=R[j];j--;
????}?while（j>=1?&&?（CPPx.key????MPPR[j+1]=x;???????????????//插入R[i]
??}
}

void?Shellinsert（list?R?int?n?int?h）{??????//shell排序的一趟排序過程，h為增量
	??int?ijk;
	??for（i=1;i<=h;i++）	{	
????for（j=i+h;j<=n;j+=h）?{
??????if（CPPR[j].key>=R[j-h].key）?continue;
??????MPPR[0]=R[j];	
??????k=j-h;		
??????do?{		
???????MPP?R[k+h]=R[k];k=k-h;
??????}?while（k>0?&&（CPP?R[0].key??????MPP?R[k+h]=R[0];
????}

}
}

void?ShellSort（list?Rint?nint?d[]int?t）{??????//d[]為增量序列，t為增量序列長度
	int?i;
???for（i=0;i??????Shellinsert（Rnd[i]）;
}

void?BubbleSort（list?Rint?n）?{//上升法冒泡排序
??int?ijflag;rectype?x;???????//x為輔助量（可用R[0]代替）
??for（i=1;i<=n-1;i++）?{?????????//做n-1趟掃描
????flag=0;?????????????????????//置未交換標志
????for（j=n;j>=i+1;j--）?????????//從下向上掃描
??????if（CPPR[j].key????????flag=1;
????????MP3x=R[j];R[j]=R[j-1];R[j-1]=x;//交換?
??????}
????if（!flag）?break;????????????//本趟未交換過記錄，排序結束
??}
}




void?BubbleSort0（list?R?int?n）{????????????//下沉法冒泡排序
int?ijflag;rectype?x;???????//x為輔助量（可用R[0]代替）
??for（i=1;i<=n-1;i++）?{?????????//做n-1趟掃描
????flag=0;?????????????????????//置未交換標