基于分治策略的排序方法的比较研究.pdfVIP

第7卷第3期 太原师范学院学报(自然科学版) V01．7No．3 Science 2008年9月JOURNALOFTAIYUANNORMALUNIVERSITY(NaturalEdition)Sept．2008 基于分治策略的排序方法的比较研究 于志奇李岸巍 (太原工业学院，山西太原030008) [摘要]讨论了运用分治策略的思想实现快速排序、归并排序和堆排序三种排序算法，从分、 解、合三方面剖析排序，从而得出分割方式是影响排序效率的关键，并将分治法扩展应用到更多排 序方法中． (关键词]分治策略；快速排序f归并排序；堆排序 [文章编号]1672—2027(2008)03—0029—04[中图分类号]TP301．6[文献标识码]A O 引言 排序(Sorting)是计算机程序设计中的一个重要操作，它的功能是将一个数据记录的任意序列，重新排 列成一个按关键字有序的序列[1]．计算机厂家们估计，把它们所有的顾客都考虑在内，在他们的计算机上，运 行的时间百分之二十五以上是花在排序上．有许多计算机装置，排序就用去计算机时间的一半以上[2]． 在程序设计时，衡量一个正确算法的好坏主要是看依据此算法编制的程序在计算机上的运行时问及需 要占用的存储空间[3]．人们在排序方法设计的实践中已经探索出了多种排序方法设计技术希望能够把时间 代价和空间代价降到最低，但就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自 的优缺点，适合不同的环境．我们熟知的排序方法有插入排序、冒泡排序、快速排序、归并排序、堆排序等。此 外，还有不断出现的例如基于估计相对位置的面积法排序“]、用P系统解决排序问题[5]排序算法． 每一种排序方法在排序的过程中都需要进行两个基本操作：1)比较两个关键字的大小；2)将记录从一个 位置移动到另一个位置．可以看出排序的效率取决于排序序列元素的多少和元素的排列情况，当排序序列小 于50时可直接采用直接插入排序或冒泡排序，当排序序列大于50小于100000时，我们可以使用本文讨论 的三种排序方法．它们均基于分治策略，将难以直接解决的大问题减小规模从而较易解决排序问题，同时可 以减少元素的移动次数． 分治策略(Divide—and—ConquerMethod)是：对于一个规模为，z的问题，若该问题可以容易地解决(比如 说规模靠为2)则直接解决，否则将其分解为矗个规模较小的子问题，这些子问题互相独立且与原问题形式相 同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解[6]． 如果原问题可分割成五个子问题，1五≤行，且这些子问题都可解，并可利用这些子问题的解求出原问 题的解，那么这种分治法就是可行的[7]． 分治策略在每一层递归上都有三个步骤： *分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题； *解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题； *合并：将各个子问题的解合并为原问题的解． 1基于分治策略的排序方法比较 1．1快速排序 快速排序(QuickSort)是一种最快的排序方法之一，又称为分区交换排序，是对冒泡排序的一种改 收稿日期：2008—07—14 作者篱介：于志奇(1982一)，男，山西孝义人．太原工业学院助教，太原理工大学在读硕士研究生，主要从事计算机应用技术研究 万方数据万方数据 30 太原师范学院学报(自然科学版) 第7卷 进[8]，是典型的基于递归与分治策略的排序方法[9]． 快速排序思想是由于原数据序列较长，很难直接排序，于是将序列分割成两个独立的子序列，其中一个 子序列的值整体小于另一个子序列的值．再对子序列进行如上方法分割，直至最后每个子序列内部有序，然 后合并每个子序列，则序列整体有序． 则分步处理： 1．1．1分割问题 选择支点(pivot)元素分解序列． 支点元素有多种选择方法，不同的选择方法会导致快速排序的不同性能．根据分治策略平衡子问题[8j的 思想，希望支点元素可以使data[10