内部排序算法比较Word格式.docx

1、时间复杂度O（n2），空间复杂度O（1）直接插入排序：希尔排序：时间复杂度O（n1.3），空间复杂度O（1）快速排序：时间复杂度O（nlog2n），空间复杂度O（nlog2n）归并排序：时间复杂度O（nlog2n），空间复杂度O（n）2 本程序包含8个模块：（1）伪随机产生数据模块：本程序要求数据是要用伪随机产生程序产生，再用不同排序算法进行排序。（2）简单选择排序模块：运用简单选择排序法对伪随机产生的数据进行排序。（3） 起泡排序模块：运用起泡排序法对伪随机产生的数据进行排序。（4）直接插入排序模块：运用直接插入排序法对伪随机产生的数据进行排序。（5）希尔排序模块：运用希尔排序法对伪随机产生

2、的数据进行排序。（6）快速排序：运用快速排序法对伪随机产生的数据进行排序。（7）归并排序：运用归并排序法对伪随机产生的数据进行排序。（8）条形图表示比较结果：统计6种排序算法的比较结果，用条形图表示出来。三调试分析（1）本题采用结构体储存数据，使相关信息紧密相联系，便于编辑和输出。（2）通过这道题，让我深入理解了内部排序算法，获益良多。调试编码过程中产生的小错误，让我的编程习惯有所改善。四用户使用说明（1）本程序的运行环境为VS2010。（2）进入演示程序后可得到结果。五测试结果点击运行，首先出现的是要输入伪随机产生数据的数目，如图9所示。图9 输入界面输入数据个数然后回车，可显示出不同排序算

3、法的比较次数、移动次数和排序用时。如图10所示。图10 显示比较结果界面显示比较次数的条形图。如图11所示。图11 比较次数条形图界面显示移动次数条形图。如图12所示图12 移动次数条形图界面显示排序用时条形图。如图13所示图13 排序用时条形图界面六、附录 #include#includestring.hmath.htime.h#define LIST_INIT_SIZE 30000int bj1,yd1,n,com,mov;long int A5,B5;double t0,t1,t2,t3,t4,t5,C5;clock_t start_t,end_t;void addlist（SqList

4、 &L） int i;a: printf（请输入你要输入的个数:）; scanf（%d,&n）; if（n20000） 超出范围重新输入!n goto a; L.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType）; if（!L.elem）exit（0）; L.length=0; for（i=1;i20000）goto b; +L.length;void SelectSort（SqList &L） /简单选择排序 start_t=clock（）; int i,j,k,com=0,mov=0;L.length; k=i; for（j=i+1

5、;jj+） com+; if（L.elemj.keyL.elemk.key）k=j; if（i!=k） L.elem0.key=L.elemi.key; L.elemi.key=L.elemk.key; L.elemk.key=L.elem0.key; mov+=3; end_t=clock（）;比较次数为 %d移动次数为 %dn,com,mov）; t0=（double）（end_t-start_t）/CLK_TCK;排序用时为 %fn,t0）; A0=com; B0=mov; C0=t0;void bubblesort（SqList &L） /起泡排序 int i=1,j,com=0,mo

6、v=0; while（iL.elemj+1.key） L.elem0.key=L.elemj.key; L.elemj.key=L.elemj+1.key; L.elemj+1.key=L.elem0.key; i+; t1=（double）（end_t-start_t）/CLK_TCK;,t1）; A1=com; B1=mov; C1=t1;void InsertSort（SqList &L） /直接插入排序 int i,j,com=0,mov=0; for（i=2;=L.length; if（L.elemi.keyL.elemi-1.key） mov+; j=i-1; while（L.el

7、em0.keyL.elemj.key） L.elemj+1.key=L.elemj.key; j-; t2=（double）（end_t-start_t）/CLK_TCK;,t2）; A2=com; B2=mov; C2=t2;void xier（SqList &L） /希尔排序 int i,d=L.length/2,j,w=0,k,com=0,mov=0; while（wd） 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）; A3=com; B3=mov;

8、 C3=t3;void BeforeSort（） yd1=0,bj1=0;void display（int m,int n）,m,n）;int Partition（SqList L,int low,int high） /快速排序 int pivotkey; L.elem0=L.elemlow; yd1+; pivotkey=L.elemlow.key; while （lowhigh） while（low=pivotkey） -high; L.elemlow=L.elemhigh; bj1+;L.elemlow.key+low; L.elemhigh=L.elemlow; L.elemlow=L

9、.elem0; return low;void QSort（SqList &L,int low,int high） int pivotloc; if（lowhigh） pivotloc=Partition（L,low,high）; QSort（L,low,pivotloc-1）; QSort（L,pivotloc+1,high）;void QuickSort（SqList & BeforeSort（）; QSort（L,1,L.length）; display（bj1,yd1）; t4=（double）（end_t-start_t）/CLK_TCK;,t4）; A4=bj1; B4=yd1;

10、C4=t4;void Merge（ElemType R,ElemType R1,int low,int m,int high） /归并排序 int i=low, j=m+1, k=low;=m&=high） if（Ri.key=Rj.key） R1k=Ri; k+; else R1k=Rj; j+;=m） while（jvoid MergePass（ElemType R,ElemType R1,int length, int n） int i=0,j; while（i+2*length-1n） Merge（R,R1,i,i+length-1,i+2*length-1）; i=i+2*lengt

11、h; if（i+length-1n-1） Merge（R,R1,i,i+length-1,n-1）; for（j=i;n; R1j=Rj;void MSort（ElemType R,ElemType R1,int n） int length=1; while （length MergePass（R,R1,length,n）; length=2*length; MergePass（R1,R,length,n）;void MergeSort（SqList & MSort（L.elem,L.elem,L.length）; t5=（double）（end_t-start_t）/CLK_TCK;,t5）

12、; A5=bj1; B5=yd1; C5=t5;void printf（SqList &long int d6;int i,n;printf（n比较次数nn=nfor（i=0;5; di= sqrt （Ai/A5）;n 归并排序： * printf（ 选择排序： for（n=0,i=0;n=di;n+）* 冒泡排序： for（n=0,i=1; 直插排序： for（n=0,i=2; 希尔排序： for（n=0,i=3; 快排排序： for（n=0,i=4;n移动次数n double e6; for（i=0;6; ei= sqrt （Bi/B3）;n 希尔排序：=ei; 归并排序： for（n=0,i=5;n排序用时n double f6; fi= sqrt （Ci/0.001）;=fi; Int main（） SqList L; 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）;