分治技术在排序算法中的应用

《分治技术在排序算法中的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、分治技术在排序算法中的应用【摘要】讲述了运用分治技术的思想实现排序算法中的归并排序、快速排序两种排序算法，然后对两种排序算法的效率进行了比较，得出了采用分治技术的排序算法是比较有效的算法。　　【关键词】分治技术;排序算法;归并排序;快速排序　　　　排序是计算机科学中经常遇到的工作，是程序设计中的一种重要运算，它的功能是将一个数据元素（或记录）的任意序列，重新排列成某个按关键字有序的序列。分治技术的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。如果在排序算法中巧妙得应用分治技术，可以使排序算法更具艺术

2、性。本文就排序算法中的归并排序和快速排序如何应用分治技术做简单的讲述。　　１．归并排序　　归并排序（Mergesort）是第一个计算机排序方法，它是由JohnvonNerman于1945年提出，是最能体现分治技术设计思路的算法之一。　　当待排元素N大于1时归并排序的步骤如下：　　⑴将待排序列二分为长度为N/2的两个子序列。　　⑵递归地对每一个子序列进行归并排序，直至N等于1。　　⑶归并两个排好的有序子序列。　　设一初始序列：49386597761327，对该序列实行归并排序过程如下：　　初始序列：[49][38][65][97][76][13][27]　　第一步：[3849][659

3、7][1376][27]　　第二步：[38496597][132776]　　第三步：[13273849657697]　　归并排序用代码描述如下：　　算法mergesort：　　template〈typenameT〉　　voidmergesort（Ta[]，intleft，intright）　　{　　T*b=neid=（left+right）/2；//取中点　　mergesort（a，left，mid）；　　mergesort（a，mid+1，right）；　　merge（a，b，left，mid，right）；//合并到数组b　　copy（a，left，right）；//复制回数组a

4、　　}　　}　　其中，算法Merge（）合并两个排好序的数组到一个新的数组中，用代码表示Merge（）如下：　　template〈typenameT〉　　voidmerge（Ta[]，Tb[]，int1，intm，intr）　　{　　inti=1，j=m+1,k=1；　　）＆＆（jm）　　{　　for(intq=j；q求解（常为递归）—>合并”的流程来进行设计的，是一个典型的分治算法。　　2.快速排序　　快速排序是由C.A.EHoare于1962年提出的，至今被认为是最好的排序算法。“计算机科学与工程（prtingScience＆Engineering）”杂志将快速排序算法列为20世

5、纪在科学和工程的开发与应用中最有影响的10个算法之一。它也是一种基于分治技术的排序算法，也是按“划分－>求解—>合并”的思路来设计的。不过快速排序中的划分不再是平衡的二爹妈，它是以待排序的任一元素（常为首元素，常称为“枢轴”）为界限，分成大于该元素的部分和小于该元素的部分，然后再递归地解决该两部分的一种高效算法。　　我们首先分析快速排序中的“划分”方法。划分的目的在于划分后使得一个元素处于一个正确的位置（该元素前面所有元素均小于后面所有元素）。要达到这个目的，方法是多样的，有的需要较多辅助空间，有的需要较少辅助空间。有的快一点，有的慢一点，这里给出一种所需辅助空间较小，而又较快的方法

6、：　　算法split：　　template　　intsplit(Ta[],intloplate　　voidqaort（Ta[]，intleft，intright）　　{　　if（left求解（常为递归）—>合并”的思路来设计的，只不过快速排序中对划分后的子序列是直接就地排序的，未引入辅助数组，因此合并的过程较为简单，只是栈中函数调用的简单返回，几乎不需要进行任何其它运算。　　综上，归并排序和快速排序都是分治技术在排序中的应用。但两者在设计过程中的侧重点不同，归并排序侧重于分治中的“合并”步骤；而快速排序则侧重于“划分”步骤。但两者都很好的体现了分治技术的思想。　　　　【