数据结构课程设计实验报告内部排序算法比较Word格式.docx
《数据结构课程设计实验报告内部排序算法比较Word格式.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计实验报告内部排序算法比较Word格式.docx（36页珍藏版）》请在冰点文库上搜索。
L->
length;
i++）
{
L->
r[0]=L->
r[1];
for（j=1;
j<
N-i;
j++）
if（L->
r[0].key>
=L->
r[j+1].key）
L->
r[j]L->
r[j+1];
//交换两记录的位置
else
//保证L->
r[0]始终为较大的记录
L->
r[j+1]=L->
r[0];
//把最大的记录放到祠堂排序的最高位置
}
printf（L->
r[MAXSIZE]）;
//输出排序后数组和相关数据
}
②直接插入排序本算法的思路是，把L->
r[0]设置为哨兵，排序时把第i个记录复制给哨兵，并于其前的i-1个记录进行比较，找到第一个比起大的记录，利用循环让记录后移，把其放到第一个比起大的记录前面。
voidinsertSort（Sqlist*L）//直接插入排序
for（i=2;
{
if（（L->
r[i].key<
L->
r[i-1].key））
{
r[0]=L->
r[i];
//复制哨兵
r[i]=L->
r[i-1];
for（j=i-2;
（L->
r[0].key<
r[j].key）;
j--）
r[j+1]=L->
r[j];
//纪录后移
//插入到正确位置
}
③简单选择排序基本思想是在第i趟选择排序时：
通过n-i次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1≦i≦n）个记录交换之
voidSelectSort（Sqlist*L）//简单选择排序
{
for（i=1;
i<
++i）//选择第i小的记录，并交换到位
j=i;
for（k=i+1;
k<
k++）//从L.r[i..L.length]中选key最小的
r[k].key）
{
r[k];
j=k;
}
if（i!
=j）
L.r[i]←→L.r[j];
//与第i个记录交换
④快速查找排序其基本思想为，通过一趟排序将带排序记录分割成两部分，其中一部分记录的关键字均小于另一部分的关键字，再利用递归分别对分割所得到的子序列进行快速排序。
其中一趟快速排序的算法为：
intserchSort（Sqlist*L,intlow,inthigh）//快速排序单次排序
pivotkey=L->
r[low].key;
//枢轴纪录关键字
while（low<
high）
while（low<
high&
&
r[high].key>
=pivotkey）high--;
r[low]L->
r[high];
//将比枢轴纪录小的纪录移到底端
r[low].key<
=pivotkey）low++;
r[high]L->
r[low];
//将比枢轴纪录大的纪录移到高端
returnhigh;
//返回枢轴所在位置
递归算法为：
voidQSort（Sqlist*L,intlow,inthigh）//快速排序
if（low<
high）
{//长度大于1
pivotloc=serchSort（L,low,high）;
//调用serchSort（）将L.r[low..high]一分为二
QSort（L,low,pivotloc-1）;
//对低子表递归排序，pivotloc是枢轴位置
QSort（L,pivotloc+1,high）;
//对高子表递归排序
⑤希尔排序基本思路是先将整个待排序的记录分割成若干个子序列进行直接排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次全体直接插入排序
voidShellSort（Sqlist*L,intdlta[],intt）//希尔排序
for（k=1;
=t;
k++）
dlta[k]=（int）pow（2,t-k+1）-1;
//doublepow（doublebase,doubleexp）;
函数返回以参数base为底的exp次幂
for（i=dlta[k]+1;
r[i-dlta[k]].key）
for（j=i-dlta[k];
j>
0&
（L->
j-=dlta[k]）
L->
r[j+dlta[k]]=L->
⑥堆排序基本思想是使记录序列按关键字非递减有序排列，则再对排序的算法中先建立一个“大顶堆”，即先选得一个关键字为最大的记录与序列中最后一个记录交换，然后再对序列中前n-1记录进行筛选，重新将它调整为“大顶堆“，如此反复直至排序结束。
voidHeapAdjust（Sqlist*L,ints,intm）{//已知L.r[s..m]中记录的关键字除L.r[s].key之外均满足堆的定义，本函数调整L.r[s]的关键字，使L.r[s..m]成为一个大顶堆（对其中记录的关键字而言）
rc=L->
r[s];
for（j=2*s;
j<
=m;
j*=2）{//沿key较大的孩子结点向下筛选
if（j<
m&
r[j].key<
r[j+1].key）++j;
//j为key较大记录的下标
if（rc.key>
=L->
r[j].key）break;
//rc应插入在位置s上
r[s]=L->
s=j;
r[s]=rc;
//插入
voidHeapSort（Sqlist*L）//堆排序
for（i=L->
length/2;
i>
0;
i--）//把H->
r[…]建成大顶堆
HeapAdjust（L,i,L->
length）;
1;
i--）
r[i]L->
//将堆顶记录和当前未经排序子序列L.r[1…i]中
//最后一个记录相互交换
HeapAdjust（L,1,i-1）;
//将H.r[1..i-1]重新调整为大顶堆
⑦菜单程序利用dowhile循环实现对菜单的正确选择，并返回选择的操作代码
intmenu_select（）//菜单目录
intnu;
chars;
printf（"
************************************************\n"
）;
*****菜单*****\n"
1.BubbleSort\n"
//冒泡排序
2.insertSort\n"
//直接插入排序
3.SelectSort\n"
//简单选择排序
4.QSort\n"
//查找排序
5.ShellSort\n"
//希尔排序
6.HeapSort\n"
//堆排序
7.退出程序\n"
请输入数字：
1-7选择相应的排序方式或操作：
\n"
do
s=getchar（）;
nu=（int）s-48;
}while（nu<
0||nu>
55）;
return（nu）;
⑧主函数是程序的入口，包括两个for循环，一个用来实现随机数产生与输出；
另一个用来实现菜单的选择的连续；
第二个for循环中包含一个switch循环，作用是根据菜单程序的返回值选择相应的操作，随后作相应的修改使待排序数据分别为正序和逆序，以实现本设计的目的。
voidmain（）
输出待排序的数据:
"
for（;
;
）
switch（menu_select（））//选择相应的排序操作
case1:
BubbleSort（&
A）;
break;
case2:
insertSort（&
B）;
case3:
SelectSort（&
C）;
case4:
QSort（&
L,1,L.length）;
break;
case5:
ShellSort（&
D,dlta,t）;
case6:
HeapSort（&
E）;
case7:
exit（0）;
运行结果：
第一组随机数据及其运行结果如下：
第二组随机数据及其运行结果如下：
第三组随机数据及其运行结果如下：
第四组随机数据及其运行结果如下：
第五组随机数据及其运行结果如下：
第六组正序数据及其运行结果如下：
第七组逆序数据及其运行结果如下：
【小结与讨论】
表中数据为关键字移动次数：
BubbleSort
insertSort
SelectSort
QSort
ShellSort
HeapSort
第一组
6974
2690
605
393
723
1082
第二组
7066
2473
586
382
742
1081
第三组
7072
2733
592
408
724
1075
第四组
7068
2587
583
368
788
1087
第五组
6963
2787
620
402
754
1085
第六组
9900
297
1136
第七组
4950
5148
2650
540
1012
下表中数据为关键字比较次数：
2504
638
785
749
2293
635
790
752
2550
600
796
2404
625
824
748
2607
621
804
745
99
480
811
672
662
有数据分析可知：
无论待排序列排序如何，BubbleSort与SelectSort两种算法的关键字比较次数均为4950，即n（n-1）/2次；
待排序列为随机序列时直接插入排序的关键字比较次数和关键字移动平均值约为n2/4,正序时比较次数为（n-1）,移动次数为0，逆序时为n（n-1）/2次；
整体看来六种排序中QSort、ShellSort、HeapSort三种排序比较和移动次数相对较少；
但BubbleSort、insertSort两种排序属于稳定性排序（每交换一次纪录，关键字就有三次移动纪录）。
在测试过程中，当连续选择一个操作时，发现有的排序方式的关键字移动次数会随之增加，例如BubbleSort，QSort，HeapSort；
仔细分析后得知，无论待排序列是否排好，它每次运行都会有关键字的移动；
每次运行程序，六种排序方式的关键字比较次数也会随着操作次数的增加而增加，原因与上一个问题先同。
【程序清单】
#include<
stdio.h>
string.h>
time.h>
#include<
stdlib.h>
math.h>
#defineMAXSIZE100
typedefintKeyType;
//定义关键字的整数类型
/**********************************************************************/
inti,j;
intN=L->
r[j]=L->
info++;
info+=2;
cmp++;
以下数据的排列顺序为BubbleSort排序后的排列顺序：
for（i=1;
=MAXSIZE;
printf（"
%d\t"
L->
r[i]）;
关键字移动次数为：
%d\n"
info）;
关键字比较次数为：
cmp）;
if（（L->
以下数据的排列顺序为insertSort排序后的排列顺序：
printf（"
inti,j,k;
k++）//在L.r[i..L.length]中选key最小者
if（i!
=j）
{//L.r[i]←→L.r[j];
与第i个记录交换
RedTypetemp;
temp=L->
r[i]=L->
r[j]=temp;
info+=3;
}
以下数据的排列顺序为SelectSort排序后的排列顺序：
intserchSort（Sqlist*L,intlow,inthigh）//查找排序单次排序
intpivotkey;
=pivotkey）
high--;
r[low]=L->
low++;
r[high]=L->
intpivotloc;
//将L.r[low..high]一分为二
QSort（L
升级会员 