数据结构各种排序算法性能比拼Word文档格式.docx
《数据结构各种排序算法性能比拼Word文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构各种排序算法性能比拼Word文档格式.docx（14页珍藏版）》请在冰点文库上搜索。
2、Shell排序
Shell排序又称缩小增量排序,Shell排序法是以创建者DonaldShell的名字命名的.Shell排序法是对相邻指定距离（称为间隔）的元素进行比较,已知到使用当前间隔进行比较的元素都按顺序排序为止.Shell把间隔缩小一半,然后继续处理,当间隔最终变为1,并且不再出现变化时,Shell排序也就完成了其处理过程.先取一个整数d1<
n,把全部记录分成d1个组，所有距离为d1倍数的记录放在一组中，先在各组内排序；
然后去d2<
d1重复上诉分组和排序工作；
直至所取的增量dt=1（dt<
dt-l<
…<
d2<
d1），即所有记录放在同一组中进行直接插入，直到dt=1，即所有记录放在一组中为止.
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；
当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。
所以，希尔排序的时间复杂度会比o（n2）好一些。
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
所以希尔排序是不稳定的，其时间复杂度为o（n2）。
3、直接选择排序
待排序的一组数据元素中，选出最小的一个数据元素与第一个位置的数据元素交换；
然后在剩下的数据元素当中再找最小的与第二个位置的数据元素交换，循环到只剩下最后一个数据元素为止，依次类推直到所有记录。
第一趟第n个记录中找出关键码最小的记录与第n个记录交换；
第二趟，从第二个记录开始的，2-1个记录中再选出关键码最小的记录与第二个记录交换；
如此，第i趟，则从第i个记录开始的n-i+l个记录中选出关键码最小的记录与第i个记录交换，直到所有记录排好序。
该算法运行时间与元素的初始排列无关。
不论初始排列如何，该算法都必须执行n-1趟，每趟执行n-i-1次关键字的比较，这样总的比较次数为：
所以，简单选择排序的最好、最坏和平均情况的时间复杂度都为O（n2）。
4、冒泡排序
在每一趟冒泡排序中，依次比较相邻的两个关键字大小，若为反序咋交换。
经过一趟起泡后，关键词大的必须移到最后。
按照这种方式进行第一趟在序列（I[0]~I[n-1]）中从前往后进行两个相邻元素的比较，若后者小，则交换，比较n-1次；
第一趟排序结束，最大元素被交换到I[n-1]中，下一趟只需在子序列（I[0]~I[n-2]）中进行；
如果在某一趟排序中未交换元素，则不再进行下一趟排序。
将被排序的记录数组J[1..n]垂直排列，每个记录J[i]看作是重量为J[i].key的气泡。
根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：
凡扫描到违反本原则的轻气泡，就使其向上"
飘浮"
。
如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止，最后可完成。
当原始数据正向有序时，冒泡排序出现最好情况。
此时，只需进行一趟排序，作n-1次关键字比较，因此最好情况下的时间复杂度是O（n）。
当原始数据反向有序时，冒泡排序出现最坏情况。
此时，需进行n-1趟排序，第i趟作（n-i）次关键字间的比较，并且需执行（n-i）次元素交换，所以，比较次数为：
因此,最坏情况下的时间复杂度为O（n2）。
五、快速排序
首先我们选择一个中间值middle（程序中我们可使用数组中间值），把比中问值小的放在其左边，比中问值大的放在其右边。
由于这个排序算法较复杂，我们先给出其进行一次排序的程序框架。
在待排序的个记录中任意取一个记录（通常取第一个记录）为区分标准，把所有小于该排序的记录移到左边，把所有大于该排序码的记录移到右边，中级放所选记录，为一趟快速排序。
然后对前后两个子序列分别重新上述过程，直到所有记录都排好序。
对任意给定的序列中某个元素，经过一趟排序后，将原序列分割成两个子序列（Rp（0）,Rp
（1）,…,Rp（s-1））和（Rp（s+1）,Rp（s+2）,…,Rp（n-1）），其中前一个子序列中的所有元素的关键词均小于或等于该元素的关键词值Kp（s），后一个子序列中元素的关键词均大于或等于Kp（s）。
称该元素Rp（s）为分割元素，子序列（Rp（0）,Rp
（1）,…,Rp（s-1））为其低端序列，（Rp（0）,Rp
（1）,…,Rp（s-1））为其高端序列。
很明显，以后只需对低端和高端序列分别进行快速排序，直到子序列为空或只有一个元素时结束，最后得到有序序列。
总之，每趟使表的第一个元素放在适当位置，将表两分，再对子表进行同样的递归划分，直至划分的子表长度为1。
如果每一次分划操作后，左、右两个子序列的长度基本相等，则快速排序的效率最高，其最好情况时间复杂度为O（nlog2n）；
反之，如果每次分划操作所产生的两个子序列，其中之一为空序列，此时，快速排序效率最低，其最坏情况时间复杂度为O（n2）。
如果选择左边第一个元素为主元，则快速排序的最坏情况发生在原始序列正向有序或反向有序时。
快速排序的平均情况时间复杂度为O（nlog2n）。
六、堆排序
1.原理
堆排序思想很简单，就是每次把关键词调整为堆，取出堆顶元素与堆中最后一个元素交换，同时令堆得大小减一，把剩余的一些元素重新调整为堆，重复此过程，直到堆中只剩一个元素,n个关键字序列kl,k2，…，kn称为堆，当且仅当该序列满足如下性质（简称为堆性质）:
（l）ki<
=k2i且ki<
=k2i+1或
（2）ki>
=k2i且ki>
=k2i+1。
若将此序列所存储的向量R[1…n]看作是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树:
树中非叶结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。
根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者的堆称为小根堆。
根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大根堆。
堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。
堆排序的最坏时间复杂度为O（nlogn）。
堆排序的平均性能较接近于最坏性能。
由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
堆排序是不稳定的，算法时间复杂度O（nlogn）。
程序运行结果以及结果分析
一、下图是对随机生成的10000个数进行排序，可以看出快速排序法耗时最少而直接插入排序耗时最多，堆排序和快速排序差不多。
二、下图是对20000个随机数进行的排序，可以看出得出了和上述一样的结果。
对程序结果的评价
经过比较我们发现，当规模不断增加时，各种算法之间的差别是很大的。
这七种算法中，快速排序耗时是最少的。
也是最快的一种排序方法。
堆排序和快速排序差不多，属于同一个数量级。
直接选择排序是耗时最多的。
通过这次作业我学到了很多东西：
①巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。
②通过自己编写的程序对各种排序性能的比较让我更深入理解了他们的应用。
参考文献
[1]严蔚敏，吴伟民，《数据结构（C语言版）》，清华大学出版社2007
附录
#include<
stdlib.h>
stdio.h>
time.h>
#defineSWAP（x,y）{intt;
t=x;
x=y;
y=t;
}
#defineN30000
voidnixu（inta[],intb[]）//反序
{
inti;
for（i=0;
i<
N;
i++）
{
b[N-1-i]=a[i];
}
voidpopo（inta[],intlen）/*冒泡排序*/
intlength=len;
inti=0;
intj=0;
for（;
len;
for（;
j<
length;
j++）
{
if（a[j]>
a[j+1]）
{
inttemp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
length--;
j=0;
voidselect（intarray[],intn）//选择排序
inti,j,t,k;
n-1;
k=i;
for（j=i+1;
n;
if（array[j]<
array[k]）k=j;
//k存放一轮中的最小数的下标;
t=array[i];
array[i]=array[k];
array[k]=t;
}
voidSwap（int*a,int*b）
inttemp;
temp=*a;
*a=*b;
*b=temp;
voidInsertSort（intdata[],intlength）//直接插入排序
inti=0;
intj=0;
for（i=1;
i<
length;
++i）
for（j=i;
j>
0;
--j）
if（data[j]<
data[j-1]）
Swap（&
data[j],&
data[j-1]）;
else
break;
voidquickSort（inta[],intleft,intright）/*快速排序*/
{
inti,j,temp;
i=left;
j=right;
temp=a[left];
if（left>
right）
return;
while（i!
=j）/*找到最终位置*/
{
while（a[j]>
=temp&
&
j>
i）
j--;
if（j>
a[i++]=a[j];
while（a[i]<
i++;
a[j--]=a[i];
}
a[i]=temp;
quickSort（a,left,i-1）;
/*递归左边*/
quickSort（a,i+1,right）;
/*递归右边*/
//归并排序
//归并排序合并数组函数的具体实现
voidmerge（inta[],intlow,intmiddle,inthigh）
inth,i,j,k;
intb[N];
h=low;
i=low;
j=middle+1;
while（h<
=middle&
=high）
if（a[h]<
=a[j]）
b[i]=a[h];
h++;
else
b[i]=a[j];
j++;
if（h>
middle）
for（k=j;
k<
=high;
k++）
b[i]=a[k];
for（k=h;
=middle;
for（k=low;
a[k]=b[k];
//归并排序函数的具体实现
voidmergesort（inta[],intlow,inthigh）
intmiddle;
if（low<
high）
middle=（low+high）/2;
mergesort（a,low,middle）;
mergesort（a,middle+1,high）;
merge（a,low,middle,high）;
voidswapa（inta[],inti,intj）//希尔排序
intt=a[i];
a[i]=a[j];
a[j]=t;
voidselsort（inta[],intn,intincr）
inti,j;
for（i=incr;
i<
n;
i+=incr）
for（j=i;
（j>
=incr）
&
（a[j]<
a[j-incr]）;
j-=incr）
swapa（a,j,j-incr）;
voidshellsort（inta[],intn）
for（i=n/2;
i>
2;
i/=2）
for（j=0;
j<
i;
j++）
selsort（&
a[j],n-j,i）;
selsort（a,n,1）;
voidshift（inta[],inti,intm）//堆排序
intk,t;
t=a[i];
k=2*i+1;
while（k<
m）
if（（k<
m-1）&
（a[k]<
a[k+1]））k++;
if（t<
a[k]）{a[i]=a[k];
i=k;
k=2*i+1;
elsebreak;
a[i]=t;
voidheap（inta[],intn）//a为排序数组，n为数组大小（编号0-n-1）
inti,k;
for（i=n/2-1;
i>
=0;
i--）
shift（a,i,n）;
for（i=n-1;
=1;
i--）
k=a[0];
a[0]=a[i];
a[i]=k;
shift（a,0,i）;
intmain（）
{intseries[N]={0};
intseries_0[N];
intseries_a[N];
intseries_b[N];
intseries_c[N];
intseries_d[N];
intseries_e[N];
intseries_f[N];
intseries_g[N];
inti,num;
srand（time（NULL））;
series[i]=rand（）%N;
series_0[i]=series[i];
for（num=0;
num<
2;
num++）
if（num>
0）
nixu（series_0,series）;
printf（"
待排数据：
\n"
）;
%d"
series[i]）;
putchar（N）;
series_a[i]=series[i];
series_b[i]=series[i];
series_c[i]=series[i];
series_d[i]=series[i];
series_e[i]=series[i];
series_f[i]=series[i];
series_g[i]=series[i];
clock_tbegin1,end1;
/*计算冒泡排序时间*/
doublecost1;
begin1=clock（）;
popo（series_a,N-1）;
end1=clock（）;
cost1=（double）（end1-begin1）/CLOCKS_PER_SEC;
冒泡排序耗时:
%lfseconds\n"
cost1）;
clock_tbegin2,end2;
/*计算选择排序时间*/
doublecost2;
begin2=clock（）;
select（series_b,N）;
end2=clock（）;
cost2=（double）（end2-begin2）/CLOCKS_PER_SEC;
选择排序耗时:
cost2）;
clock_tbegin3,end3;
/*计算直接插入排序时间*/
doublecost3;
begin3=clock（）;
InsertSort（series_c,N）;
end3=clock（）;
cost3=（double）（end3-begin3）/CLOCKS_PER_SEC;
直接插入排序耗时:
cost3）;
clock_tbegin4,end4;
/*计算快速排序时间*/
doublecost4;
begin4=clock（）;
quickSort（series_d,0,N-1）;
end4=clock（）;
cost4=（double）（end4-begin4）/CLOCKS_PER_SEC;
快速排序耗时:
cost4）;
clock_tbegin5,end5;
/*计算归并排序时间*/
doublecost5;
begin5=clock（）;
mergesort（series_e,0,N-1）;
end5=clock（）;
cost5=（double）（end5-begin5）/CLOCKS_PER_SEC;
归并排序耗时:
cost5）;
clock_tbegin6,end6;
/*计算希尔排序时间*/
doublecost6;
begin6=clock（）;
shellsort（series_f,N）;
end6=clock（）;
cost6=（double）（end6-begin6）/CLOCKS_PER_SEC;
希尔排序耗时:
cost6）;
clock_tbegin7,end7;
/*计算堆排序时间*/
doublecost7;
begin7=clock（）;
heap（series_g,N）;
end7=clock（）;
cost7=（double）（end7-begin7）/CLOCKS_PER_SEC;
堆排序耗时:
cost7）;
升级会员 