排序算法课程设计

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

2、e <iostream.h>typedef int keytype;struct datatypekeytype key;/* int rand(void); void srand(unsigned int seed ); */#include<stdlib.h>#include<stdio.h>#include<time.h>#include<windows.h>void InsertSort (datatype a, int n)/用直接插入法对a0-an-1排序int i, j;datatype temp;for(i=0; i&

3、lt;n-1; i+)temp = ai+1;j = i;while(j > -1 && temp.key <= aj.key)aj+1 = aj;j-;aj+1 = 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();for(int i=0;i<10000;i+

4、)numi.key=rand(); int n=10000;InsertSort(num,n);for(int j=0;j<10000;j+) cout<<numj.key<<endl;t2=GetCurrentTime();cout<<"The t1 time is:"<<t1<<"The t2 time is:"<<t2<<" t2-t1:"<<t2-t1<<endl;getchar(); （2）希尔排序#includ

5、e <iostream.h>/* int rand(void); void srand(unsigned int seed ); */#include<stdlib.h>#include<stdio.h>#include<time.h>#include<windows.h>typedef int keytype;struct datatypekeytype key;void ShellSort (datatype a, int n, int d, int numOfD)/用希尔排序法对记录a0-an-1排序/各组内采用直接插入法排序i

6、nt i, j, k, m, span;datatype temp;for(m = 0; m < numOfD; m+)span = dm;for(k = 0; k < span; k+)for(i = k; i < n-span; i = i+span)temp = ai+span;j = i;while(j > -1 && temp.key <= aj.key)aj+span = aj;j = j-span;aj+span = temp;void main() /*srand(unsigned)time(NULL);/ 随机种子 */*time

7、_t t;srand(unsigned)time(&t);*/time_t t1,t2;srand(unsigned)GetCurrentTime();datatype num10000;t1=GetCurrentTime();for(int i=0;i<10000;i+)numi.key=rand(); int n=10000, d=1000,100,10,1,numOfd=4;ShellSort (num,n,d,numOfd); for(int j=0;j<10000;j+) cout<<numj.key<<endl;t2=GetCurrent

8、Time();cout<<"The t1 time is:"<<t1<<"The t2 time is:"<<t2<<" t2-t1:"<<t2-t1<<endl;getchar(); （3）直接选择排序#include <iostream.h>typedef int keytype;struct datatypekeytype key;/* int rand(void); void srand(unsigned int seed ); *

9、/#include<stdlib.h>#include<stdio.h>#include<time.h>#include<windows.h>void 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;vo

10、id 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;i<10000;i+)numi.key=rand(); int n=10000;SelectSort(num,n); for(int j=0;j<10000;j+) cout<<numj.key<<e

11、ndl;t2=GetCurrentTime();cout<<"The t1 time is:"<<t1<<"The t2 time is:"<<t2<<" t2-t1:"<<t2-t1<<endl;getchar(); （4）堆排序#include <iostream.h>typedef int keytype;struct datatypekeytype key;#include<stdlib.h>#include<st

12、dio.h>#include<time.h>#include<windows.h>void 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)/寻找左右孩子结点中的较大者,j为其下标if(j < n-1 && aj.key <

13、; aj+1.key) j+;if(temp.key > aj.key)/ai.key>aj.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);/初

14、始化创建最大堆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();f

15、or(int i=0;i<10000;i+)numi.key=rand(); int n=10000;HeapSort(num, n); for(int j=0;j<10000;j+) cout<<numj.key<<endl;t2=GetCurrentTime();cout<<"The t1 time is:"<<t1<<"The t2 time is:"<<t2<<" t2-t1:"<<t2-t1<<endl;g

16、etchar(); （5）冒泡排序 #include <iostream.h>typedef int keytype;struct datatypekeytype key;#include<stdlib.h>#include<stdio.h>#include<time.h>#include<windows.h>void BubbleSort(datatype a, int n)/用冒泡排序法对a0-an-1排序int i, j, flag=1;datatype temp;for(i = 1; i < n && f

17、lag = 1; i+)flag = 0;for(j = 0; j < n-i; j+)if(aj.key > 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();datatype num10000;t1=GetCurrentTime();for(int i=0;i<

18、;10000;i+)numi.key=rand(); int n=10000;BubbleSort(num, n); for(int j=0;j<10000;j+) cout<<numj.key<<endl;t2=GetCurrentTime();cout<<"The t1 time is:"<<t1<<"The t2 time is:"<<t2<<" t2-t1:"<<t2-t1<<endl;getchar(); （6）

19、快速排序#include <iostream.h>/* int rand(void); void srand(unsigned int seed ); */#include<stdlib.h>#include<stdio.h>#include<time.h>#include<windows.h>typedef int keytype;struct datatypekeytype key;void QuickSort(datatype a, int low, int high)/用递归方法对对象alow-ahigh进行快速排序int i

20、, 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 < temp.key) i+;if(i < j)aj = ai;j-;ai = temp;/对子对象数组进行递归快速排序if(low < i) QuickSort(a, low, i-1);if(i <

21、; 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;i<10000;i+)numi.key=rand(); int n=10000;QuickSort(num, 0, 9999); for(int j=0;j<

22、;10000;j+) cout<<numj.key<<endl;t2=GetCurrentTime();cout<<"The t1 time is:"<<t1<<"The t2 time is:"<<t2<<" t2-t1:"<<t2-t1<<endl;getchar(); （7）归并排序#include <iostream.h>/* int rand(void); void srand(unsigned int s

23、eed ); */#include<iostream.h>#include<stdlib.h>#include<stdio.h>#include<time.h>#include<windows.h>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

24、,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;/计算第二个有序子表上界/两个有序子表合并for(i = l1, j = l2; i <= u1 && j <= u2; m+)if(ai.key <= aj.key)swapm = ai;i+;elseswapm=aj;j+;/子表2已归并完，将子表1中剩余的对象顺序存放到数组swap中w

25、hile(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 = ai;void MergeSort(datatype a, int n)/用二路归并排序法对对象数组a0-an-1排序，swap用于临时存放对象int i, k = 1;/归并长度由1开始datatype *swap = new datatypen;/

26、动态数组申请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;srand(unsigned)time(&t);*/time_t t1,t2;srand(unsigned)GetCurrentTime();datatype num10000;t1=GetCurrentTime();for(int i=0;i<10000;i+)numi.key=rand(); int n=10000;MergeSort(num, n); for(int j=0;j<10000;j+) cout<<numj.key<<endl;t2=GetCurrentTime();cout<<"The t