1、排序算法课程设计排序算法课程设计专 业 班 级 学 号 姓 名 指导老师一：课程设计的目的1.掌握各种排序的基本思想2.掌握各种排序的算法实现3.掌握各种排序的算法优劣分析花费的时间计算4.掌握各种排序算法所适用的不同场合。二：课程设计的内容（1）冒泡、直插、选择、快速、希尔、归并、堆排序算法进行比较；（ 2）待排序的元素的关键字为整数。 其中的数据用伪随机产生程序产生 （如 10000 个,1000个），再使用各种算法对其进行排序，记录其排序时间，再汇总比较； （3）将每次测试所用的时间，用条形图进行表示，以便比较各种排序的优劣。三：课程设计的实现( 1) 直接插入排序#include ty
2、pedef int keytype;struct datatypekeytype key;/* int rand(void);void srand(unsigned int seed ); */ #include #include #include #include void 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
3、)time(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
4、 time is:t2 t2-t1:t2-t1endl; getchar();(2)希尔排序#include /* int rand(void);void srand(unsigned int seed );*/#include#include#include #include typedef int keytype;struct datatype keytype key;void ShellSort (datatype a, int n, int d, int numOfD) /用希尔排序法对记录 a0-an-1 排序 /各组内采用直接插入法排序int i, j, k, m, span;da
5、tatype temp;for(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=
6、GetCurrentTime();for(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 datatype
7、 keytype key;/* int rand(void);void srand(unsigned int seed );*/#include #include #include #include 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;voi
8、d 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;i10000;i+) numi.key=rand();int n=10000;SelectSort(num,n);for(int j=0;j10000;j+)coutnumj.keyendl;t2=GetCurrentTime();cout
9、The t1 time is:t1The t2 time is: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;/沿左
10、右孩子中值较大者重复向下筛选while(j n & flag != 1) /寻找左右孩子结点中的较大者 ,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, in
11、t n)int i;datatype temp;InitCreatHeap(a, n); / 初始化创建最大堆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)GetCurrentTi
12、me();datatype num10000;t1=GetCurrentTime();for(int i=0;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 datatype keytype k
13、ey;#include #include #include #include void BubbleSort(datatype 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(unsi
14、gned)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;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
15、)快速排序#include /* int rand(void);void srand(unsigned int seed );*/#include#include#include #include typedef 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(
16、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 high) QuickSort(a, j+1, high);void main()/*srand(unsigned)time(NULL);/ 随机种子 */*time_t t;srand(unsigned)time(&t);*/time_t t1,t2; sran
17、d(unsigned)GetCurrentTime();datatype num10000;t1=GetCurrentTime();for(int i=0;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);
18、void srand(unsigned int seed );*/#include#include#include#include#includetypedef 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)
19、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 中 while(i = u1)swapm = ai;m+;i+;/子表 1 已归并完，将子表 2 中剩余的对象顺序存放到数组 swap 中
20、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)用二路归并排序法对对象数组aO-an-1排序，swap用于临时存放对象 int i, k = 1; /归并长度由 1 开始datatype *swap = new datatypen; /动态数组申请while(k n)Merge(a, n, swap, k);/将记录从数组 swap 放回 a 中 for(i = O
21、; 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;t仁 GetCurre ntTime();for(int i=0;i10000;i+)nu mi.key=ra nd();int n=10000;MergeSort( num, n);for(i nt
22、 j=0;j10000;j+)cout nu mj.keye ndl;t2=GetCurre ntTime();coutThe t1 time is:t1The t2 time is:t2 t2-t1:t2-t1endl;getchar();四：课程设计的结果对10000个随机数排序所用时间排序算法一一一二二二四五平均直接插入453 n468P 484 :469485471.8希尔排序297297297297297297直接选择500 :484484484500490.4堆排序312296297297281296.6冒泡排序500500500500485497快速排序312281:296297
23、297296.6归并排序281282297281297287.6对1000个随机数排序所用时间排序算法一一一二 二三 三四五平均直接插入47 :47r 31314740.6希尔排序473131323234.6直接选择314747313137.4堆排序473231313134.4冒泡排序314747314640.4快速排序4631:31473137.2归并排序313132313231.4用图的形式表示如下:五：课程设计的结论在数据多的情况下，归并排序能够在最短的运行中完成排序，其次希尔排序, 堆排序，快速排序。而冒泡所需要的时间最长，在数据少的情况下归并排序依然 最快，可是没有那一种排序算法有明显的时间优势。通过理论计算与数据验证可得：各种排序方法性能比较排序方法最好时间平均时间最坏时间直接插入0( n)O(n2)2O(n2)希尔排序O(n1.3)直接选择O(n2)O(n2)O( n2)堆排序O(n Iog2 n)O(n Iog2 n)O(n Iog2 n)冒泡排序O(n)O(n2)O(n2)快速排序O(nl og2 n)O(n Iog2 n)O(n2)归并排序O(n Iog2 n)O(n Iog2 n)O(n Iog2 n)
