资源描述：
《《综合排序正式论》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> 基本思想插入排序的思想就是读一个，排一个，将第１个数放入数组的第１个元素中，以后读入的数与已存入数组的数进行比较，确定它在从大到小的排列中应处的位置．将该位置以及以后的元素向后推移一个位置，将读入的新数填入空出的位置中．第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
