资源描述:
《《综合排序正式论》word版》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、目 录一、问题描述32.1基本要求:32.2.算法思想:32.3.模块划分:52.4.数据结构:202.5.源程序:212.6.测试情况:32三、小结39四、参考文献40一、问题描述用C语言编程解决插入、冒泡,快速排序,简单选择,堆排序以及分析各种算法的时间复杂度和空间复杂度,比较各种排序在不同场合的适用程度,分析各种排序算法的实用性。内容简介2.1基本要求:(1)设计一个的菜单将在实现的功能显示出来,并有选择提示;(2)分别实现直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序,堆排序算法;(3)通过多种测试数据,对各种排序算
2、法的时间复杂度和空间复杂度进行比较2.2.算法思想:2.2.1简单选择排序 <1> 基本思想每一趟在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列的第i个关键字。2.2.2直接插入排序 <1> 基本思想插入排序的思想就是读一个,排一个,将第1个数放入数组的第1个元素中,以后读入的数与已存入数组的数进行比较,确定它在从大到小的排列中应处的位置.将该位置以及以后的元素向后推移一个位置,将读入的新数填入空出的位置中.第38页共38页2.2.3折半插入排序<1>基本思想从第二个数开始逐个置入监视哨,使用low,high标签进行
3、折半判断比较大小,并确认插入位置,该位置到最后一个数全部后移一位,最后腾出该位置,把监视哨里面的数置入该位置。后面的数以此类推进行排序,直到最后一个数比较完毕。2.2.4希尔排序<1> 基本思想希尔排序法是1959年由D.L.Shell提出来的,又称减少增量的排序。下表是以八个元素排序示范的例子.在该例中,开始时相隔4个成分,分别按组进行排序,这时每组2个成分,共4组;然后相隔2个成分,在按组排序......最后,对所有相邻成分进行排序.2.2.5冒泡排序 <1> 基本思想 依次比较相邻的两个数,把大的放前面,小的放后面.即首先比较第1个数和第2个
4、数,大数放前,小数放后.然后比较第2个数和第3个数......直到比较最后两个数.第一趟结束,最小的一定沉到最后.重复上过程,仍从第1个数开始,到最后第2个数.然后...... 由于在排序过程中总是大数往前,小数往后,相当气泡上升,所以叫冒泡排序.2.2.6快速排序<1> 基本思想 快速排序的基本思想是基于分治策略的。对于输入的子序列L[p..r],如果规模足够小则直接进行排序,否则分三步处理: 分解(Divide):将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r],使L[p..q]中任一元素的值不大于L[q+1.
5、.r]中任一元素的值。 递归求解(Conquer):通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。合并(Merge):由于对分解出的两个子序列的排序是就地进行的,所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序。2.2.7堆排序 <1>基本思想堆排序,顾名思义,就是基于堆。因此先来介绍一下堆的概念。堆分为最大堆和最小堆,其实就是完全二叉树。大顶堆要求节点的元素都要大于其孩子,小顶第38页共38页堆要求节点元素都小于其左右孩子,两者对左右孩子的大小关系不做任何要求。有
6、了上面的定义,我们可以得知,处于大顶堆的根节点的元素一定是这个堆中的最大值。其实我们的堆排序算法就是抓住了堆的这一特点,每次都取堆顶的元素,将其放在序列最后面,然后将剩余的元素重新调整为最大堆,依次类推,最终得到排序的序列。或者说,堆排序将所有的待排序数据分为两部分,无序区和有序区。无序区也就是前面的最大堆数据,有序区是每次将堆顶元素放到最后排列而成的序列。每一次堆排序过程都是有序区元素个数增加,无序区元素个数减少的过程。当无序区元素个数为1时,堆排序就完成了。本质上讲,堆排序是一种选择排序,每次都选择堆中最大的元素进行排序。只不过堆排序选择元素的
7、方法更为先进,时间复杂度更低,效率更高。2.3.模块划分:2.3.1主函数的算法功能描述开始输入数据个数lengthcreate(),visit()输入select第38页共38页7select654321078select_sort(L);Zhijie(L);ShellSort(L,dlta,4);Maopao(L);QuickSort(L);print(num);HeapSort()QuickSort(L);select_sort(L);Maopao(L);ShellSort()Zhijie(L)Exit(0)BinsertSort()输入y/
8、nny结束2.3.2退出函数:exit();功能描述:根据提示输入0,则退出系统2.3.3选择排序算法功能描述函数:sel