分治技术在排序算法中的应用
上传人:cunz****g666
文档编号:144645790
上传时间:2022-08-27
格式:DOC
页数:2
大小:14.50KB
收藏
版权申诉
举报
下载
第1页 / 共2页
第2页 / 共2页
资源描述:
《分治技术在排序算法中的应用》由会员分享,可在线阅读,更多相关《分治技术在排序算法中的应用(2页珍藏版)》请在装配图网上搜索。
分治技术在排序算法中的应用【摘 要】讲述了运用分治技术的思想实现排序算法中的归并排 序、快速排序两种排序算法,然后对两种排序算法的效率进行了比 较,得出了采用分治技术的排序算法是比较有效的算法。【关键词】分治技术 ;排序算法 ; 归并排序 ;快速排序 排序是计算机科学中经常遇到的工作,是程序设计中的一种重要 运算,它的功能是将一个数据元素(或记录)的任意序列,重新排 列成某个按关键字有序的序列。分治技术的基本思想是将一个规模 为 n 的问题分解为 k 个规模较小的子问题,这些子问题相互独立且 与原问题性质相同。求出子问题的解,就可得到原问题的解。如果 在排序算法中巧妙得应用分治技术,可以使排序算法更具艺术性。 本文就排序算法中的归并排序和快速排序如何应用分治技术做简 单的讲述。1.归并排序归并排序( mergesort )是第一个计算机排序方法, 它是由 john vonnerman于1945年提出,是最能体现分治技术设计思路的算法之一。当待排元素 n 大于 1 时归并排序的步骤如下: 将待排序列二分为长度为 n/2 的两个子序列。 递归地对每一个子序列进行归并排序,直至 n 等于 1。 归并两个排好的有序子序列。设一初始序列: 49 38 65 97 76 13 27 ,对该序列实行归并排序 过程如下:
展开阅读全文
- 温馨提示:
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。