#include
#include
#include
#include
#define?LIST_INIT_SIZE?50000
int?bj1yd1n;
clock_t?start_tend_t;
typedef?struct?
{
?int?key;?
}ElemType;
typedef?struct?
{
?ElemType?*elem;
?int?length;
}SqList;
void?addlist（SqList?&L）
{
?int?i;
a:?printf（“請輸入你要輸入的個數:“）;
?scanf（“%d“&n）;
?if（n>50000）
?{
??printf（“超出范圍重新輸入!!!\n“）;
??goto?a;
?}
?L.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;
?if（!L.elem）exit（0）;
?L.length=0;
?for（i=1;i?{
b:??L.elem[i].key=rand（）;
??if（L.elem[i].key>30000）goto?b;
?????++L.length;
?}
}
void?SelectSort（SqList?&L）//選擇
{
?start_t=clock（）;
?int?ijkbj=0yd=0;
?for（i=1;i?{
??k=i;
??for（j=i+1;j??{
???bj++;
???if（L.elem[j].key??}
??if（i!=k）
??{
???L.elem[0].key=L.elem[i].key;
???L.elem[i].key=L.elem[k].key;
???L.elem[k].key=L.elem[0].key;
???yd+=3;
??}
?}
?end_t=clock（）;
?printf（“比較次數為???????%d移動次數為???????%d\n“bjyd）;
?printf（“排序用時為???????%f\n“float（end_t-start_t）/CLK_TCK）;
}
void?qipao（SqList?&L）//起泡
{
?start_t=clock（）;
?int?i=1jbj=0yd=0;
?while（i?{
??for（j=1;j??{
???bj++;
???if（L.elem[j].key>L.elem[j+1].key）
???{
????L.elem[0].key=L.elem[j].key;
????L.elem[j].key=L.elem[j+1].key;
????L.elem[j+1].key=L.elem[0].key;
????yd+=3;
???}
??}
??i++;
?}
?end_t=clock（）;
?printf（“比較次數為???????%d移動次數為???????%d\n“bjyd）;
?printf（“排序用時為???????%f\n“float（end_t-start_t）/CLK_TCK）;
}
void?InsertSort（SqList?&L）//直接插入
{
?start_t=clock（）;
?int?ijyd=0bj=0;
?for（i=2;i<=L.length;i++）
?{
??if（L.elem[i].key??{
???L.elem[0].key=L.elem[i].key;
???yd++;
???j=i-1;
???bj++;
???while（L.elem[0].key???{
????L.elem[j+1].key=L.elem[j].key;
????j--;
????yd++;
????bj++;
???}
???L.elem[j+1].key=L.elem[0].key;
???yd++;
??}
?}
?end_t=clock（）;
?printf（“比較次數為???????%d移動次數為???????%d\n“bjyd）;
?printf（“排序用時為???????%f\n“float（end_t-start_t）/CLK_TCK）;
}
void?xier（SqList?&L）//希爾
{
?start_t=clock（）;
?int?id=L.length/2jw=0kyd=0bj=0;
?while（w?{
??w=1;
??for（i=w;i??{
???k=i;
???for（j=i+d;j???{
????if（L.elem[i].key>L.elem[j].key）
????{
?????k=j;
?????bj++;
????}
???}
???if（i!=k）
???{
????L.elem[0].key=L.elem[i].key;
????L.elem[i].key=L.elem[k].key;
????L.elem[k].key=L.elem[0].key;
????yd+=3;
???}
???w++;
??}
??d=d/2;
??w=1;
?}
?end_t=clock（）