数据结构课程设计十种排序算法比较

2 结果分析

实验结果与我们对这十种种算法的性能理论分析基本吻合：插入排序与冒泡排序的时间复杂度为O(n*n)，而后三种排序算法的时间复杂度为O(nlogn)。实验结果还显示出虽然冒泡排序和插入排序的时间复杂度相同，但插入排序的性能仍然比

冒泡排序好，尤其在排序时间方面。

七、参考文献

[1] 王昆仑，李红. 数据结构与算法. 北京：中国铁道出版社，2006年5月。 [2] 王立柱，C语言与数据结构.北京：清华大学出版社，2003年6月第1版。

八、附录

以上是对本设计的实现功能和算法等的全面分析，以下是带注释的源代码算法#include #include #include #include #include #define N 100 int p,q;

int g=0;int h=0; //起泡排序

void gensort(int b[],int n) {

int i,j;int s=0,t=0; for(i=0;i

for(j=i+1;j

if(b[i]>b[j]) {

int temp=b[i]; b[i]=b[j]; b[j]=temp; s+=3; }}}

cout<<\移动次数=\比较次数=\}

//插入排序

typedef int KeyType;

struct rec

{

KeyType key; };

typedef rec sqlist[N];

void insertsort(sqlist b,int n) {

int i,j;int s=0,t=0; for(i=2;i

b[0].key=b[i].key; s++; j=i-1; t++;

while(b[0].key

b[j+1]=b[j]; j--; s++; t++; }

b[j+1]=b[0]; s++; }

cout<<\移动次数=\比较次数=\}

//折半插入排序

void so(sqlist num,int n) { int s=0;

int low,high,m;//分别指向低、高、中的位置

int i,j,k=0,t;//i,j循环 k交换次数 t哨兵

for(i=1;i

t=num[i].key ;

low=0;high=i-1;

while(low<=high)

{

m=(low+high)/2;

if(t

else low=m+1; }

for(j=i-1;j>=high+1;j--) {

num[j+1].key=num[j].key; s++; }

num[high+1].key=t; }

cout<<\移动次数=\比较次数=\ }

//希尔排序

void shellsort(sqlist b,int n) {

int i,j,gap; rec x;

int s=0,t=0; gap=n/2; while(gap>0) {

for(i=gap+1;i

j=i-gap;