排序算法课程设计(共14页).doc

《排序算法课程设计(共14页).doc》由会员分享，可在线阅读，更多相关《排序算法课程设计(共14页).doc（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上 排序算法课程设计专 业 班 级 学 号 姓 名 指导老师 一：课程设计的目的1. 掌握各种排序的基本思想2. 掌握各种排序的算法实现3. 掌握各种排序的算法优劣分析花费的时间计算4. 掌握各种排序算法所适用的不同场合。二：课程设计的内容（1）冒泡、直插、选择、快速、希尔、归并、堆排序算法进行比较；（2）待排序的元素的关键字为整数。其中的数据用伪随机产生程序产生（如10000个,1000个），再使用各种算法对其进行排序，记录其排序时间，再汇总比较；（3）将每次测试所用的时间，用条形图进行表示，以便比较各种排序的优劣。三：课程设计的实现（1） 直接插入排序#includ

2、e typedef int keytype;struct datatypekeytype key;/* int rand(void); void srand(unsigned int seed ); */#include#include#include#includevoid InsertSort (datatype a, int n)/用直接插入法对a0-an-1排序int i, j;datatype temp;for(i=0; i -1 & temp.key = aj.key)aj+1 = aj;j-;aj+1 = temp;void main() /*srand(unsigned)tim

3、e(NULL);/ 随机种子 */*time_t t;srand(unsigned)time(&t);*/time_t t1,t2;srand(unsigned)GetCurrentTime();datatype num10000;t1=GetCurrentTime();for(int i=0;i10000;i+)numi.key=rand(); int n=10000;InsertSort(num,n);for(int j=0;j10000;j+) coutnumj.keyendl;t2=GetCurrentTime();coutThe t1 time is:t1The t2 time is

4、:t2 t2-t1:t2-t1endl;getchar(); （2）希尔排序#include /* int rand(void); void srand(unsigned int seed ); */#include#include#include#includetypedef int keytype;struct datatypekeytype key;void ShellSort (datatype a, int n, int d, int numOfD)/用希尔排序法对记录a0-an-1排序/各组内采用直接插入法排序int i, j, k, m, span;datatype temp;f

5、or(m = 0; m numOfD; m+)span = dm;for(k = 0; k span; k+)for(i = k; i -1 & temp.key = aj.key)aj+span = aj;j = j-span;aj+span = temp;void main() /*srand(unsigned)time(NULL);/ 随机种子 */*time_t t;srand(unsigned)time(&t);*/time_t t1,t2;srand(unsigned)GetCurrentTime();datatype num10000;t1=GetCurrentTime();fo

6、r(int i=0;i10000;i+)numi.key=rand(); int n=10000, d=1000,100,10,1,numOfd=4;ShellSort (num,n,d,numOfd); for(int j=0;j10000;j+) coutnumj.keyendl;t2=GetCurrentTime();coutThe t1 time is:t1The t2 time is:t2 t2-t1:t2-t1endl;getchar(); （3）直接选择排序#include typedef int keytype;struct datatypekeytype key;/* int

7、 rand(void); void srand(unsigned int seed ); */#include#include#include#includevoid SelectSort(datatype a, int n)/*用直接选择排序法对a0-an-1排序*/int i, j, s;datatype temp;for(i=0; i n-1; i+)s = i;for(j = i+1; j n; j+)if(aj.key as.key) s=j;if(s != i)temp = ai;ai = as;as = temp;void main() /*srand(unsigned)time

8、(NULL);/ 随机种子 */*time_t t;srand(unsigned)time(&t);*/time_t t1,t2;srand(unsigned)GetCurrentTime();datatype num10000;t1=GetCurrentTime();for(int i=0;i10000;i+)numi.key=rand(); int n=10000;SelectSort(num,n); for(int j=0;j10000;j+) coutnumj.keyendl;t2=GetCurrentTime();coutThe t1 time is:t1The t2 time is

9、:t2 t2-t1:t2-t1endl;getchar(); （4）堆排序#include typedef int keytype;struct datatypekeytype key;#include#include#include#includevoid CreatHeap (datatype a, int n, int h)int i, j, flag;datatype temp;i = h; / i为要建堆的二叉树根结点下标j = 2*i+1;/ j为i的左孩子结点的下标temp = ai;flag = 0;/沿左右孩子中值较大者重复向下筛选while(j n & flag != 1)

10、/寻找左右孩子结点中的较大者,j为其下标if(j n-1 & aj.key aj.key)/ai.keyaj.keyflag=1;/标记结束筛选条件else/否则把aj上移ai = aj;i = j;j = 2*i+1;ai = temp;/把最初的ai赋予最后的ajvoid InitCreatHeap(datatype a, int n)int i;for(i = (n-1)/2; i = 0; i-)CreatHeap(a, n, i);void HeapSort(datatype a, int n)int i;datatype temp; InitCreatHeap(a, n);/初始化

11、创建最大堆for(i = n-1; i 0; i-)/当前最大堆个数每次递减1/把堆顶a0元素和当前最大堆的最后一个元素交换temp = a0;a0 = ai;ai = temp;CreatHeap(a, i, 0);/调整根结点满足最大堆void main() /*srand(unsigned)time(NULL);/ 随机种子 */*time_t t;srand(unsigned)time(&t);*/time_t t1,t2;srand(unsigned)GetCurrentTime();datatype num10000;t1=GetCurrentTime();for(int i=0;

12、i10000;i+)numi.key=rand(); int n=10000;HeapSort(num, n); for(int j=0;j10000;j+) coutnumj.keyendl;t2=GetCurrentTime();coutThe t1 time is:t1The t2 time is:t2 t2-t1:t2-t1endl;getchar(); （5）冒泡排序 #include typedef int keytype;struct datatypekeytype key;#include#include#include#includevoid BubbleSort(datat

13、ype a, int n)/用冒泡排序法对a0-an-1排序int i, j, flag=1;datatype temp;for(i = 1; i n & flag = 1; i+)flag = 0;for(j = 0; j aj+1.key)flag = 1;temp = aj;aj = aj+1;aj+1 = temp;void main() /*srand(unsigned)time(NULL);/ 随机种子 */*time_t t;srand(unsigned)time(&t);*/time_t t1,t2;srand(unsigned)GetCurrentTime();datatyp

14、e num10000;t1=GetCurrentTime();for(int i=0;i10000;i+)numi.key=rand(); int n=10000;BubbleSort(num, n); for(int j=0;j10000;j+) coutnumj.keyendl;t2=GetCurrentTime();coutThe t1 time is:t1The t2 time is:t2 t2-t1:t2-t1endl;getchar(); （6）快速排序#include /* int rand(void); void srand(unsigned int seed ); */#in

15、clude#include#include#includetypedef int keytype;struct datatypekeytype key;void QuickSort(datatype a, int low, int high)/用递归方法对对象alow-ahigh进行快速排序int i, j;datatype temp;i = low;j = high;temp = alow;while(i j)/在数组的右端扫描while(i j & temp.key = aj.key) j-;if(i j)ai = aj;i+;/在数组的左端扫描while(i j & ai.key tem

16、p.key) i+;if(i j)aj = ai;j-;ai = temp;/对子对象数组进行递归快速排序if(low i) QuickSort(a, low, i-1);if(i high) QuickSort(a, j+1, high);void main() /*srand(unsigned)time(NULL);/ 随机种子 */*time_t t;srand(unsigned)time(&t);*/time_t t1,t2;srand(unsigned)GetCurrentTime();datatype num10000;t1=GetCurrentTime();for(int i=0

17、;i10000;i+)numi.key=rand(); int n=10000;QuickSort(num, 0, 9999); for(int j=0;j10000;j+) coutnumj.keyendl;t2=GetCurrentTime();coutThe t1 time is:t1The t2 time is:t2 t2-t1:t2-t1endl;getchar(); （7）归并排序#include /* int rand(void); void srand(unsigned int seed ); */#include#include#include#include#include

18、typedef int keytype;struct datatypekeytype key;void Merge(datatype a, int n, datatype swap, int k)/对有序表a0-an-1进行一次二路归并排序，每个有序子表的长度为k/一次二路归并排序后新的有序子表存于swap中int m = 0, u1,l2,i,j,u2;int l1 = 0;/给出第一个有序子表下界while(l1+k = n-1)l2 = l1 + k;/计算第二个有序子表下界u1 = l2 - 1;/计算第一个有序子表上界u2 = (l2+k-1 = n-1)? l2+k-1: n-1;

19、/计算第二个有序子表上界/两个有序子表合并for(i = l1, j = l2; i = u1 & j = u2; m+)if(ai.key = aj.key)swapm = ai;i+;elseswapm=aj;j+;/子表2已归并完，将子表1中剩余的对象顺序存放到数组swap中while(i = u1)swapm = ai;m+;i+;/子表1已归并完，将子表2中剩余的对象顺序存放到数组swap中while(j = u2)swapm = aj;m+;j+;l1 = u2 + 1;/将原始数组中不足二组的对象顺序存放到数组swap中for(i = l1; i n; i+, m+) swapm

20、 = ai;void MergeSort(datatype a, int n)/用二路归并排序法对对象数组a0-an-1排序，swap用于临时存放对象int i, k = 1;/归并长度由1开始datatype *swap = new datatypen;/动态数组申请while(k n)Merge(a, n, swap, k); /将记录从数组swap放回a中for(i = 0; i n; i+) ai = swapi;/归并长度加倍k = 2 * k;delete swap;void main() /*srand(unsigned)time(NULL);/ 随机种子 */*time_t t

21、;srand(unsigned)time(&t);*/time_t t1,t2;srand(unsigned)GetCurrentTime();datatype num10000;t1=GetCurrentTime();for(int i=0;i10000;i+)numi.key=rand(); int n=10000;MergeSort(num, n); for(int j=0;j10000;j+) coutnumj.keyendl;t2=GetCurrentTime();coutThe t1 time is:t1The t2 time is:t2 t2-t1:t2-t1endl;getch

22、ar(); 四：课程设计的结果对10000个随机数排序所用时间排序算法一 二 三 四 五 平均直接插入 453 468 484 469 485 471.8希尔排序297 297 297 297 297 297直接选择500 484 484 484 500 490.4堆排序 312 296 297 297 281 296.6冒泡排序 500 500 500 500 485 497快速排序 312 281 296 297 297 296.6归并排序 281 282 297 281 297 287.6对1000个随机数排序所用时间排序算法 一 二 三 四 五 平均直接插入 47 47 31 31 4

23、740.6希尔排序 47 31 31 32 3234.6直接选择 31 47 47 31 3137.4 堆排序 47 32 31 31 3134.4冒泡排序 31 47 47 31 4640.4快速排序 46 31 31 47 3137.2归并排序 31 31 32 31 3231.4用图的形式表示如下：五：课程设计的结论在数据多的情况下，归并排序能够在最短的运行中完成排序，其次希尔排序，堆排序，快速排序。而冒泡所需要的时间最长，在数据少的情况下归并排序依然最快，可是没有那一种排序算法有明显的时间优势。通过理论计算与数据验证可得：各种排序方法性能比较排序方法最好时间平均时间最坏时间直接插入O(n)O(n2)O(n2)希尔排序O(n1.3)直接选择O(n2)O(n2)O(n2)堆排序O(nlog2n)O(nlog2n)O(nlog2n)冒泡排序O(n)O(n2)O(n2)快速排序O(nlog2n)O(nlog2n)O(n2)归并排序O(nlog2n)O(nlog2n)O(nlog2n)专心-专注-专业