内部排序算法比较Word格式.docx
《内部排序算法比较Word格式.docx》由会员分享，可在线阅读，更多相关《内部排序算法比较Word格式.docx（22页珍藏版）》请在冰点文库上搜索。
时间复杂度O（n2），空间复杂度O
（1）
直接插入排序：
希尔排序：
时间复杂度O（n1.3），空间复杂度O
（1）
快速排序：
时间复杂度O（nlog2n），空间复杂度O（nlog2n）
归并排序：
时间复杂度O（nlog2n），空间复杂度O（n）
2．本程序包含8个模块：
（1）伪随机产生数据模块：
本程序要求数据是要用伪随机产生程序产生，再用不同排序算法进行排序。
（2）简单选择排序模块：
运用简单选择排序法对伪随机产生的数据进行排序。
（3）起泡排序模块：
运用起泡排序法对伪随机产生的数据进行排序。
（4）直接插入排序模块：
运用直接插入排序法对伪随机产生的数据进行排序。
（5）希尔排序模块：
运用希尔排序法对伪随机产生的数据进行排序。
（6）快速排序：
运用快速排序法对伪随机产生的数据进行排序。
（7）归并排序：
运用归并排序法对伪随机产生的数据进行排序。
（8）条形图表示比较结果：
统计6种排序算法的比较结果，用条形图表示出来。
三．调试分析
（1）本题采用结构体储存数据，使相关信息紧密相联系，便于编辑和输出。
（2）通过这道题，让我深入理解了内部排序算法，获益良多。
调试编码过程中产生的小错误，让我的编程习惯有所改善。
四．用户使用说明
（1）本程序的运行环境为VS2010。
（2）进入演示程序后可得到结果。
五．测试结果
点击运行，首先出现的是要输入伪随机产生数据的数目，如图9所示。
图9输入界面
输入数据个数然后回车，可显示出不同排序算法的比较次数、移动次数和排序用时。
如图10所示。
图10显示比较结果界面
显示比较次数的条形图。
如图11所示。
图11比较次数条形图界面
显示移动次数条形图。
如图12所示
图12移动次数条形图界面
显示排序用时条形图。
如图13所示
图13排序用时条形图界面
六、附录
#include<
stdio.h>
#include<
stdlib.h>
string.h>
math.h>
time.h>
#defineLIST_INIT_SIZE30000
intbj1,yd1,n,com,mov;
longintA[5],B[5];
doublet0,t1,t2,t3,t4,t5,C[5];
clock_tstart_t,end_t;
voidaddlist（SqList&
L）
inti;
a:
printf（"
请输入你要输入的个数:
"
）;
scanf（"
%d"
&
n）;
if（n>
20000）
{
超出范围重新输入!
!
\n"
gotoa;
}
L.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;
if（!
L.elem）exit（0）;
L.length=0;
for（i=1;
i<
n+1;
i++）
b:
L.elem[i].key=rand（）;
if（L.elem[i].key>
20000）gotob;
++L.length;
}
voidSelectSort（SqList&
L）//简单选择排序
start_t=clock（）;
inti,j,k,com=0,mov=0;
L.length;
k=i;
for（j=i+1;
j<
j++）
com++;
if（L.elem[j].key<
L.elem[k].key）k=j;
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;
mov+=3;
end_t=clock（）;
比较次数为%d移动次数为%d\n"
com,mov）;
t0=（double）（end_t-start_t）/CLK_TCK;
排序用时为%f\n"
t0）;
A[0]=com;
B[0]=mov;
C[0]=t0;
voidbubblesort（SqList&
L）//起泡排序
inti=1,j,com=0,mov=0;
while（i<
L.length）
for（j=1;
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;
i++;
t1=（double）（end_t-start_t）/CLK_TCK;
t1）;
A[1]=com;
B[1]=mov;
C[1]=t1;
voidInsertSort（SqList&
L）//直接插入排序
inti,j,com=0,mov=0;
for（i=2;
=L.length;
if（L.elem[i].key<
L.elem[i-1].key）
mov++;
j=i-1;
while（L.elem[0].key<
L.elem[j].key）
L.elem[j+1].key=L.elem[j].key;
j--;
t2=（double）（end_t-start_t）/CLK_TCK;
t2）;
A[2]=com;
B[2]=mov;
C[2]=t2;
voidxier（SqList&
L）//希尔排序
inti,d=L.length/2,j,w=0,k,com=0,mov=0;
while（w<
d）
w=1;
for（i=w;
i=i+d）
for（j=i+d;
j=j+d）
k=j;
w++;
d=d/2;
t3=（double）（end_t-start_t）/CLK_TCK;
t3）;
A[3]=com;
B[3]=mov;
C[3]=t3;
voidBeforeSort（）
yd1=0,bj1=0;
voiddisplay（intm,intn）
m,n）;
intPartition（SqListL,intlow,inthigh）//快速排序
intpivotkey;
L.elem[0]=L.elem[low];
yd1++;
pivotkey=L.elem[low].key;
while（low<
high）
while（low<
high&
&
L.elem[high].key>
=pivotkey）
{
--high;
L.elem[low]=L.elem[high];
bj1++;
L.elem[low].key<
++low;
L.elem[high]=L.elem[low];
L.elem[low]=L.elem[0];
returnlow;
voidQSort（SqList&
L,intlow,inthigh）
{
intpivotloc;
if（low<
high）
pivotloc=Partition（L,low,high）;
QSort（L,low,pivotloc-1）;
QSort（L,pivotloc+1,high）;
voidQuickSort（SqList&
BeforeSort（）;
QSort（L,1,L.length）;
display（bj1,yd1）;
t4=（double）（end_t-start_t）/CLK_TCK;
t4）;
A[4]=bj1;
B[4]=yd1;
C[4]=t4;
voidMerge（ElemTypeR[],ElemTypeR1[],intlow,intm,inthigh）//归并排序
inti=low,j=m+1,k=low;
=m&
=high）
if（R[i].key<
=R[j].key）
R1[k]=R[i];
k++;
else
R1[k]=R[j];
j++;
=m）
while（j<
voidMergePass（ElemTypeR[],ElemTypeR1[],intlength,intn）
inti=0,j;
while（i+2*length-1<
n）
Merge（R,R1,i,i+length-1,i+2*length-1）;
i=i+2*length;
if（i+length-1<
n-1）
Merge（R,R1,i,i+length-1,n-1）;
for（j=i;
n;
R1[j]=R[j];
voidMSort（ElemTypeR[],ElemTypeR1[],intn）
intlength=1;
while（length<
MergePass（R,R1,length,n）;
length=2*length;
MergePass（R1,R,length,n）;
voidMergeSort（SqList&
MSort（L.elem,L.elem,L.length）;
t5=（double）（end_t-start_t）/CLK_TCK;
t5）;
A[5]=bj1;
B[5]=yd1;
C[5]=t5;
voidprintf（SqList&
longintd[6];
inti,n;
printf（"
\n★★★★★★比较次数★★★★★★\n"
\n=====================\n"
for（i=0;
5;
d[i]=sqrt（A[i]/A[5]）;
\n归并排序：
*"
printf（"
选择排序：
"
for（n=0,i=0;
n<
=d[i];
n++）
*"
冒泡排序：
for（n=0,i=1;
直插排序：
for（n=0,i=2;
希尔排序：
for（n=0,i=3;
快排排序：
for（n=0,i=4;
\n★★★★★★移动次数★★★★★★\n"
doublee[6];
for（i=0;
6;
e[i]=sqrt（B[i]/B[3]）;
\n希尔排序：
=e[i];
归并排序：
for（n=0,i=5;
\n★★★★★★排序用时★★★★★★\n"
doublef[6];
f[i]=sqrt（C[i]/0.001）;
=f[i];
}
Intmain（）
SqListL;
addlist（L）;
\n选择排序:
\n"
SelectSort（L）;
\n起泡排序:
bubblesort（L）;
\n直插排序:
InsertSort（L）;
addlist（L）;
\n希尔排序:
xier（L）;
\n快速排续:
QuickSort（L）;
\n归并排序:
MergeSort（L）;
printf（L）;
升级会员 