排序算法比较-C++.doc

排序算法的比较
1课程设计名称排序算法的比较
概述
排序是计算机程序设计中的一种重要操作。它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列。内部排序算法主要分为5 大类,有十二个算法。插入排序类、交换排序类、选择排序类、归并排序类和基数排序类。算法主要包括:插入排序、折半插入排序、选择排序、冒泡排序、希尔排序、快速排序、堆排序、归并排序、基数排序等。
2使用工具软件
Microsoft Visual C++
3 课程设计内容简介

掌握各种排序算法(直接插入排序、冒泡排序、快速排序、简单选择排序)的思路核比较他们之间的优劣
。
基本要求
:系统首先生成1000个随机整数,然后分别用不同的排序方法对其进行升序排序,给出每种方法的比较次数或所用时间
:界面要友好,输入有提示,尽量展示人性化
:源程序代码清晰、有层次
:用户输入非法数据时,系统要及时给出警告信息
课程设计思想
程序设计的总体思路:首先构建main()函数,根据题目的要求,再分别构建四个排序函数:冒泡排序函数(long Bubblesort(long R[], long n))、选择排序函数(long selectsort(long R[],long n))、直接插入排序函数(long insertsort(long R[], long n))和快速排序函数(void QuickSort(long R[],long n))。为了使程序具有可读性和层次感,建立一个导航函数(void DaoHang())和操作函数(void operate(long a[], long n)),其中,void DaoHang()用来告知用户程序的操作流程,void operate(long a[], long n)用来接收用户不同的选择,从而调用其它函数。
程序分析
存储结构
顺序存储结构(如图1)
示意图
a0
a1
a2
a3
a4
图1
关键算法分析
关键算法1
实现四种算法的基本排序功能
:两两比较相邻记录的关键码,如果反序则交换,直到没有反序记录为止。
实现过程(如图2)。
对于数组(21 25 49 16 08)。
初态:
21
25
49
16
08
第一趟:
21
25
16
08
49
第二趟:
21
16
08
25
49
第三趟:
16
08
21
25
49
第四趟:
08
16
21
25
49
图2
:从待排序的记录序列中选择关键码最小(或最大)的记录并将它与序列中的第一个记录交换位置;然后从不包括第一个位置上的记录序列中选择关键码最小(或最大)的记录并将它与序列中的第二个记录交换位置;如此重复,直到序列中只剩下一个记录为止。
实现过程(如图3)。
对于数组(21 25 49 16 08)。
初态:
21
25
49
16
08
第一趟:
08
25
49
16
21
第二趟:
08
16
49
25
21
第三趟:
08
16
21
25
49
图3
:依次将待排序的序列中的每一个记录插入到先前排序好的序列中,直到全部记录排序完毕。
实现过程(如图4)。
对于数组(21 25 49 16 08)。
初态:
21
25
49
16
08
第一趟:
21
25
49
16
08
第二趟:
21
25
49
16
08
第三趟:
21
25
49
16
08
第四趟:
16
21
25
49
08
第五趟:
08
16
21
25
49
图4
:首先选择一个基准,将记录分割为两部分,左支小于或等于基准,右支则大于基准,然后对两部分重复上述过程,直至整个序列排序完成。
实现过程(如图5)
对于数组(21 25 49 16 08)。
初态:
R[0]=21
21
25
49
16
08
high
low
第一趟:
R[0]=21
08
25
49
16
08
high
low
R[0]=21
08
25
49
16
25
high
low
R[0]=21
08
16
49
16
25
high
low
R[0]=21
08
16
49
16
25
low
high
R[0]=21
08
16
49
49
2