排序算法的比较 c++

《排序算法的比较 c++》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、排序算法的比较1课程设计名称排序算法的比较概述排序是计算机程序设计中的一种重要操作。它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。内部排序算法主要分为5大类，有十二个算法。插入排序类、交换排序类、选择排序类、归并排序类和基数排序类。算法主要包括：插入排序、折半插入排序、选择排序、冒泡排序、希尔排序、快速排序、堆排序、归并排序、基数排序等。2使用工具软件MicrosoftVisualC++6.03课程设计内容简介3.1课程设计内容掌握各种排序算法（直接插入排序、冒泡排序、快速排序、简单选择排序）的思路核比较他们之间的

2、优劣。3.2基本要求1.任意性：系统首先生成1000个随机整数，然后分别用不同的排序方法对其进行升序排序，给出每种方法的比较次数或所用时间2.友好性：界面要友好，输入有提示，尽量展示人性化3.可读性：源程序代码清晰、有层次4.健壮性：用户输入非法数据时，系统要及时给出警告信息3.3课程设计思想程序设计的总体思路：首先构建main()函数，根据题目的要求，再分别构建四个排序函数：冒泡排序函数（longBubblesort(longR[],longn)）、选择排序函数（longselectsort(longR[],longn)）、直接插入排序函数（lo

3、nginsertsort(longR[],longn)）和快速排序函数（voidQuickSort(longR[],longn)）。为了使程序具有可读性和层次感，建立一个导航函数（voidDaoHang()）和操作函数（voidoperate(longa[],longn)），其中，voidDaoHang()用来告知用户程序的操作流程，voidoperate(longa[],longn)用来接收用户不同的选择，从而调用其它函数。3.4程序分析3.4.1存储结构顺序存储结构（如图1）示意图a0a1a2a3a4图13.4.2关键算法分析关键算法1实现四种

4、算法的基本排序功能1．冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止。实现过程（如图2）。对于数组（2125491608）。初态：2125491608第一趟：2125160849第二趟：2116082549第三趟：1608212549第四趟：0816212549图22．选择排序：从待排序的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止。实现过程（如图3）。

5、对于数组（2125491608）。初态：2125491608第一趟：0825491621第二趟：0816492521第三趟：0816212549图33．直接插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。实现过程（如图4）。对于数组（2125491608）。初态：2125491608第一趟：2125491608第二趟：2125491608第三趟：2125491608第四趟：1621254908第五趟：0816212549图44．快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基

6、准，然后对两部分重复上述过程，直至整个序列排序完成。实现过程（如图5）对于数组（2125491608）。初态：R[0]=212125491608highlow第一趟：R[0]=210825491608highlowR[0]=210825491625highlowR[0]=210816491625highlowR[0]=210816491625lowhighR[0]=210816494925highlowR[0]=21low=high0816214925图5关键算法二获取当前系统时间，精确到毫秒，分别在代码运行前后调用记录前后时间，再相减即可得到代码

7、运行时间。//以冒泡排序为例start=(double)clock();//开始Bubblesort(R,n);end=(double)clock();//结束Time=(double)(end-start)/CLK_TCK;//相减，精确到毫秒关键算法三：实现手动与计算机随机双重输入。手动输入检查程序的正确性，计算机随即输入，可以比较各排序算法的性能。voidRand()//随机数函数voidHandInput()//手动输入函数关键算法四纠错功能。在用户输入非法数据时，给予警告，并要求用户重新输入，不必重启程序。3.4.3时间复杂度与空间复杂度

8、：理论分析可以得出各种排序算法的时间复杂度和空间复杂度，如下表所示（图6）：排序方法平均情况最好情况最坏情况辅助空间直接插