数据结构----各种排序算法的比较
一．实验目的
实现常用的排序算法，加深对这些算法的理解，以后可以将这些算法应用到实际问题的解决上。
二．实验题目
排序是在实际问题中经常用到的算法，快速、选择和插入三种排序算法是排序算法中最简单的也是最常用到的，实现这三种算法，在不同的数值序列上运行，然后比较三种方法的空间复杂度和时间复杂度，分析比较结果，得出选择这三种排序算法的一般原则。
三．实现提示
1．待排序列的数据结构描述：
#include<stdio.h> #include<stdlib.h> #include <time.h> //使用当前时钟做种子 #define MAXSIZE 10000 //一个用作示例的顺序表的最大长度 /*************************************数据结构的定义*************************************/ typedef int KeyType; //定义关键字类型为整数类型 typedef char InfoType; typedef struct { KeyType key; //关键字项 InfoType otherifo; //其他数据项 }RedType; //记录类型 typedef struct { RedType r[MAXSIZE+1]; //r[0]闲置或用作哨兵单元 int length; //顺序表的长度 }SqList; //顺序表类型 /****************************************功能函数*****************************************/ /* 快速排序. 思想：选定一个枢纽元素，对待排序序列进行分割， 分割之后的序列一个部分小于枢纽元素，一个部分大于枢纽元素，再 对这两个分割好的子序列进行上述的过程。 总结：平均效率O（nlogn），适用于排序大列表。 此算法的总时间取决于枢纽值的位置；选择第一个元素作为枢纽，可能 导致O（n2）的最糟用例效率。若数基本有序，效率反而最差。选项中间 值作为枢纽，效率是O（nlogn）。基于分治法。 */ void QuickSort(SqList &L,int l,int h) { if (l>=h) return ; int j ,i,key; i=l; j=h; key=L.r[i].key; while(i<j) { while(i<j&&L.r[j].key>key) j--; if (i<j) L.r[i++].key=L.r[j].key; while (i<j&&L.r[i].key<key) i++; if (i<j) L.r[j--].key=L.r[i].key; } L.r[i].key=key; if (l<i-1) QuickSort(L,l,i-1); if (i+1<h) QuickSort(L,i+1,h); } /* 选择排序。 思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序 放在已排好序的数列的最后，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。 */ void SelectSort(SqList &L) { int i,j,m,n=L.length+1 ; int t ;//临时变量 for(i=1;i<n;i++) { m=i ; for(j=i+1;j<n;j++) { if(L.r[j].key<L.r[m].key) m=j; } if(m!=i) { t=L.r[i].key; L.r[i].key=L.r[m].key; L.r[m].key=t ; } } } /* 插入排序。 思想：将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。 最佳效率O（n）；最糟效率O（n2）与冒泡、选择相同，适用于排序小列表 若列表基本有序，则插入排序比冒泡、选择更有效率。 */ void InsertSort(SqList &L) { // 对顺序表L作直接插入排序。 int i,j; for (i=2; i<=L.length; ++i) if (L.r[i].key<L.r[i-1].key) { // "<"时，需将L.r[i]插入有序子表 L.r[0] = L.r[i]; // 复制为哨兵 for (j=i-1; L.r[0].key<L.r[j].key; --j) L.r[j+1] = L.r[j]; // 记录后移 L.r[j+1] = L.r[0]; // 插入到正确位置 } } /* 产生10000个随即数。 产生1万个随机。数并进行排序。统计他所消耗的时间。 */ SqList random() { SqList s; s.length=10000; int i,j; srand((int)time(0)); for(i=0;i<10000;i++) { j=1+(int)(1000.0*rand()/(RAND_MAX+1.0)); s.r[i].key=j; } return s; } /***************************************计算时间的main函数*************************************/ int main() { SqList s1; s1.length=10000; clock_t start,end; //快速排序 s1 = random(); start = clock(); QuickSort(s1,1,s1.length); end = clock(); printf( "对1万个数进行快速排序的时间为%lf秒\n ", (double)(end-start)/CLOCKS_PER_SEC); //选择排序 s1 = random(); start = clock(); SelectSort(s1); end = clock(); printf("对1万个数进行选择排序的时间为%lf秒\n ", (double)(end-start)/CLOCKS_PER_SEC); //插入排序 s1 = random(); start = clock(); InsertSort(s1); end = clock(); printf("对1万个数进行插入排序的时间为%lf秒\n ", (double)(end-start)/CLOCKS_PER_SEC); system("PAUSE"); return 0; } 转载请注明出处.......